О-нотация

Лекция 4. Проектирование алгоритмов

Алгоритм используется при написании любой программы и представляет собой пошаговую инструкцию выполнения вычислений или процесса. Очень часто решение той или иной задачи может быть реализовано с использованием различных алгоритмов. Например, простая задача нахождения по некоторому полю определенной записи в массиве записей может быть решена методом последовательного поиска, т.е. последовательным считыванием элементов массива, пока не будет найдена нужная запись или достигнут конец массива. Но можно применить и другие алгоритмы, например бинарного поиска. Если массив отсортирован по заданному полю, то поиск в этом случае осуществляется так: берем средний элемент массива, если это нужная запись, то поиск завершается, если нет, то определяем, находится ли нужный элемент в первой или второй половине и повторяем операции, т.е. снова берем средний элемент в выбранной половине и так далее.

Основными критериями для выбора алгоритма являются его сложность, т.е. количество различных операций, выполняемых в процессе обработки, и эффективность, определяемая объемом памяти, необходимой для размещения данных, и его быстродействием. Быстродействие оценивается скоростью выполнения кода, а единственным методом оценки времени работы алгоритма является измерение времени его выполнения. Время выполнения кода в свою очередь отличается в зависимости от условий прохождения алгоритма и исходных данных. Традиционно для оценки времени работы кода используются профилировщики. Для приведенной выше задачи поиска записи в массиве алгоритм последовательного поиска более прост, а алгоритм бинарного поиска более быстр.

Для выражения характеристик быстродействия в вычислительной технике используется О-нотация (big-Oh notation).

В этой нотации используется специальная математическая функция от n, т.е. количества элементов, которой пропорционально быстродействие алгоритма. Таким образом, мы говорим, что алгоритм принадлежит к классу O(f(n)), где f(n) некоторая функция от n. Приведенное обозначение читается как «О большое от F(n)» или, менее строго, «пропорционально f(n)».

Так последовательный поиск принадлежит классу О(n), а бинарный – к классу O(log(n)), откуда собственно и можно сделать вывод, что бинарный поиск всегда быстрее, т.к. log(n)<n.

О-нотация характеризует лишь среднюю скорость выполнения алгоритма, так как время его выполнения зависит от исходных данных и условий. Например, если искомый элемент в массиве стоит первым, то очевидно, что последовательный поиск даст результат на первой же итерации, и время выполнения этого алгоритма окажется много меньше, чем алгоритма бинарного поиска. Поэтому О-нотация, являясь ценным средством оценки быстродействия алгоритмов, в общем случае имеет смысл только для больших значений n.