Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi

Эксперименты по оценке быстродействия алгоритмов проводились различными способами. Сначала для обоих алгоритмов было определено время, необходимое для поиска фамилии "Smith" в массивах из 100, 1000, 10000 и 100000 элементов, которые содержали искомый элемент. В следующей серии экспериментов осуществлялся поиск того же элемента в массивах того же размера, но при отсутствии в них искомого элемента. Результаты экспериментов приведены в таблице 1.1.

Таблица 1.1. Времена выполнения последовательного и бинарного поиска

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

Результаты выполнения бинарного поиска проанализировать сложнее. Может даже показаться, что из-за очень быстрого выполнения алгоритма при определении времени мы столкнулись с проблемой потери точности. Очевидно, что зависимость между количеством элементов в массиве и временем выполнения алгоритма не является линейной. Но по приведенным данным трудно определить тип зависимости.

Эксперименты были проведены повторно. При этом времена выполнения умножались на коэффициент 100.

Таблица 1.2. Повторное тестирование бинарного поиска

Эти данные более достоверны. Из них видно, что десятикратное увеличение количества элементов в массиве приводит к увеличению времени выполнения на определенную постоянную величину (примерно на 0.5). Это логарифмическая зависимость, т.е. время бинарного поиска пропорционально логарифму количества элементов в массиве.

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

Что мы узнали из результатов проведенных экспериментов? Во-первых, теперь мы знаем, что единственным методом определения быстродействия алгоритма является оценка времени его выполнения.

----

В общем случае, единственным методом определения быстродействия отдельной части кода является оценка времени ее выполнения. Это справедливо как в отношении широко известных алгоритмов, так и в отношении алгоритмов, разработанных лично вами. Не нужно предполагать, просто измерьте время выполнения.

----

Во-вторых, мы определили, что по своей природе последовательный поиск является линейным, а бинарный поиск - логарифмическим. Если быть поближе к математике, то можно взять эти статистические результаты и теоретически доказать их справедливость. Тем не менее, в этой книге мы не будет перегружать текст математическими выкладками. Можно найти немало книг, в которых приведены эти выкладки (см., например, тома "Фундаментальные алгоритмы на С++" и "Фундаментальные алгоритмы на С" Роберта Седжвика, вышедшие в свет в издательстве "Диасофт").

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

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

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