Введение в сложность алгоритмов

Программы состоят из алгоритмов. Алгоритмы бывают разные, ну хорошие или плохие если говорить абстрактно. Что такое хороший алгоритм? Очевидно тот, который выполняет задачу потребляя меньше ресурсов (а следовательно плохой тот который выполняет ту же задачу потребляя больше ресурсов).

Какие ресурсы есть в компьютере? Два основных это процессорное время и память. Затронем первую величину (время), как наиболее важный параметр в большинстве случаев.

Итак, хороший алгоритм - быстрый алгоритм.
От чего же зависит скорость работы отдельно взятого алгоритма?
Очевидно от количества его действий, чем больше действий, тем больше время работы.

Что подразумевается под действиями? Да в общем то все, будь это арифметические действия над числами или операции сравнения или присвоения, любое действие требует времени на свое выполнение.

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

Например нам надо найти какое то значение в одномерном массиве.
Мы пишем цикл, который пробежит по массиву и вернет нам номер элемента в массиве, которому соответствует искомое значение.

Очевидно, что чем меньше массив, тем быстрее будет работать алгоритм. То есть цикл из 100 итераций явно будет быстрее, чем цикл из 1 000 итераций, это интуитивно понятно.

Если это не много формализовать, то получиться 100*K и 1000*K, где K это некое статичное (всегда одинаковое) время выполнения операции сравнения элементов в массиве.
Если еще больше формализовать, то получается N*K, где N это размерность массива.
Получаем линейную зависимость времени работы алгоритма от его размера.

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

Нам нужен формальный способ описания времени работы алгоритма, с помощью которого можно понимать и сравнивать порядки времени выполнения того или иного алгоритма, а не опираться на интуицию.

    Асимптотические обозначения сложности алгоримов:
  • O - о большое = Наибольшее время выполнения алгоритма
  • Ω - омега большое = наименьшее время выполнения алгоритма
  • Θ - тета = когда наибольшее время и наименьшее имеют один порядок

Важным является тот момент, что при асимптотическом подходе измерения алгоритмов входящие данные (N) всегда стремятся к бесконечности.
В следствии чего важным становится только порядок возрастания функции в зависимости от входящих данных , проще говоря из алгоритма надо взять наиболее ресурсоемкую операцию.
Например у нас есть алгоритм С*N^2+K, при достаточно больших входящих данных, C и K уже не будут играть роли, так как N в квадрате будет доминировать.

Так как у нас алгоритм линейный, можно откинуть K, и сказать, что наихудшее время выполнения алгоритма будет O(n) читается, как "О большая от N", а наилучшее время Ω(1).

То что данные стремятся к бесконечности это довольно важный момент, потому что иногда на малом количестве данных выгоднее (например в виду простоты реализации) использовать более ресурсоемкий алгоритм, так как разницы во времени практически не будет. В качестве примера сортировка массива пузырьком (O(n^2) и пирамидальная сортировка Θ(n log n).


comments powered by Disqus