Алгоритмы: объяснение сложности и оптимизации

Question

Я пытаюсь найти источник или два в Интернете, которые объясняют это в простых терминах.Кроме того, может ли это понятие использоваться на практике для улучшения алгоритма?Если так, то как?Ниже приводится краткое объяснение, которое я получил от контакта.

Я не знаю, где можно найти простое объяснение.Но я пытаюсь объяснить тебе.Сложность алгоритма - это термин, который объясняет зависимость между входной информацией и ресурсами, необходимыми для ее обработки.Например, если вам нужно найти max в массиве, вы должны перечислить все элементы и сравнить их с вашей переменной (например, max).Предположим, что в массиве N элементов.Итак, сложность этого алгоритма O (N), потому что мы перечисляем все элементы за один раз.Если мы перечислим все элементы 2 раза, сложность будет O (N * N).Бинарный поиск имеет сложность O (log2 (N)), потому что его область поиска уменьшается вдвое за каждый шаг.Кроме того, вы можете выяснить пространственную сложность вашего алгоритма - зависимость между пространством, требуемым программой, и количеством входных данных.

Answer 1

Сложно сказать все о сложности, но я думаю, что в вики есть хорошее объяснение, а для запуска хорошо, см .:

1. Big O нотация длявведение в этот аспект (также вы можете посмотреть на нотации тета и омега).
2. Анализ алгоритма , чтобы узнать больше о сложности.
3. И Вычислительная сложность, которая является большой теорией в области компьютерных наук.

и об оптимизации вы можете посмотреть в Интернете и вики, чтобы найти ее, но с пятью строками ваши друзья дают хороший пример для ознакомления, ноэто не одна ночная попытка понять их использование, расчеты и тысячи теорий.

В целом вы можете быть знакомы с ними по мере необходимости, читая вики, читайте книги по продвинутому уровню, такие как Гари и Джонсон или читайте Сложность вычислений, современный подход , ноне ожидайте, что вы знаете все о них после этого.Также вы можете увидеть заметки этой лекции: http://www.cs.rutgers.edu/~allender/lecture.notes/.

Answer 2

В любом случае, понимать структуры данных, алгоритмы и big-O.
Разработайте код тщательно и хорошо, сделав его максимально простым.

Но этого недостаточно.

Ключом к оптимизации является умение найти проблем, после написания кода .

Вот пример.

Answer 3

Also, can this notion be used in a practical fashion to improve an algorithm? If so, how?

Он используется не столько для улучшения алгоритма, сколько для оценки производительности алгоритмов и выбора алгоритма, который вы решите использовать.Для любой данной проблемы вы действительно хотите избегать алгоритмов, которые имеют O (N!) Или O (N ^ x), так как они резко замедляются при увеличении размера N (вашего ввода).То, что вы хотите, это O (N) или O (log (N)) или, что еще лучше, O (1).

O (1) - это постоянное время, что означает, что для выполнения алгоритма требуется то же количество времени, что и длямиллион входов, как это делается для одного.O (N), конечно, линейный, что означает, что время, необходимое для выполнения алгоритма, увеличивается пропорционально его вводу.

Есть даже некоторые проблемы, когда любой алгоритм, разработанный для их решения, в конечном итоге становится O (N!).В принципе, быстрый алгоритм не может быть разработан для полного решения проблемы (этот класс проблем известен как NP-полный).Как только вы поймете, что имеете дело с такой проблемой, вы можете немного ослабить свои требования и решить проблему не лучшим образом, «обманывая».Эти читы не обязательно находят оптимальное решение, но вместо этого соглашаются на достаточно хорошее.Мои любимые читы - это генетические / эволюционные алгоритмы и радужные таблицы.

Еще один пример того, как понимание сложности алгоритмов меняет ваши взгляды на программирование, - это микрооптимизации.Вернее, не делать этого.Вы часто видите, как новички задают такие вопросы, как is ++x faster than x++.Опытным программистам, в основном, все равно, и они обычно отвечают: the first rule of optimization is: don't.

Более полезный ответ должен состоять в том, что изменение x++ на ++x никак не повлияет на сложность вашего алгоритма.Сложность вашего алгоритма оказывает гораздо большее влияние на скорость вашего кода, чем любая форма микрооптимизации.Например, для вас гораздо более продуктивно смотреть на ваш код и сокращать количество глубоко вложенных циклов, чем беспокоиться о том, как ваш компилятор превращает ваш код в сборку.

Еще один пример - какВ программировании игр ускорение кода противоречит интуитивно понятному принципу: добавление еще большего количества кода вместо сокращения кода.Добавленный код представлен в виде фильтров (в основном, если ... другие операторы), которые решают, какой бит данных нуждается в дальнейшей обработке, а какой можно отбросить.С точки зрения микрооптимизатора, добавление кода означает больше инструкций для процессора.Но на самом деле эти фильтры уменьшают проблемное пространство, отбрасывая данные и, следовательно, работают быстрее в целом.

Answer 4

Можно посмотреть Структура и интерпретация компьютерных программ . Это хороший курс MIT.

Answer 5

Читатель курса, используемый на вводных уроках программирования в Стэнфорде, имеет большую главу об алгоритмическом анализе легендарного преподавателя CS Эрика Робертса. Весь текст находится в сети по этой ссылке , и, возможно, стоит ознакомиться с главой 8.

Answer 6

Как подсказал твой друг, это не простая тема. Но стоит потратить некоторое время на обучение. Проверьте эту книгу , обычно используемую в качестве учебника в курсах CS по алгоритмам.