O-синтаксис или как оценить сложность алгоритма

Как оценить скорость и сложность  алгоритма? Принято брать за основную метрику оценки зависимость между необходимым количеством шагов алгоритма до достижения результата и размером данных, над которым этот алгоритм работает. Рассмотрим на простом примере. Сравним алгоритмы линейного и двоичного поиска. Пусть размер массива равен 100. Тогда нетрудно догадаться, что для поиска элемента линейным алгоритмом понадобится 50 шагов в худшем случае. При работе же двоичного поиска максимальное количество шагов будет равно 7.

Пусть теперь размер массива 10 000. Линейный поиск справится за 5000 шагов, потому что ему необходимо будет проверить каждый элемент в массиве, двоичного поиска выполнит задачу максимум за 14 шагов. Согласитесь, выигрыш в скорости восхищает.

Вернемся немного в начало и подумаем. Почему мы оцениваем алгоритмы по размеру задачи? На самом деле это самая объективная оценка в общем случае. Например, разница между линейным и двоичным поисками на размере массива 10 будет минимальной. 5 против 4. Выше мы показали как меняется это соотношение с ростом размера массива.

O-синтаксис

О – синтаксис или (Order of) это оценка сложности алгоритма. Именно оценка, т.е. это не показатель точной скорости выполнения к примеру. О – синтаксис не учитывает скорость микропроцессора, компилятора и остальных факторов, которые  оказывают влияние на скорость.

Примеры:

 Линейный поиск в упорядоченном массиве  О(N)
Двоичный поиск в упорядоченном массиве  О(logN)
 Вставка в неупорядоченный массив  О(1)
 Сортировка “Пузырьком”  О(N^2)

Если переводите на слова, то О(1) – отлично,  О(logN) – хорошо, О(N) – удовлетворительно,  О(N^2) – плохо.

Оставить комментарий:

Ваш email не будет опубликован.