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

Эксперименты были проведены повторно. При этом времена выполнения умножались на коэффициент 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, можно сделать вывод о том, что бинарный поиск всегда быстрее, чем последовательный. Тем не менее, немного ниже будут приведены несколько замечаний, касающихся выводов, сделанных из О-нотации.

О-нотация проста и удобна. Предположим, что экспериментальным путем было определено, что алгоритм X принадлежит к классу O(n(^2^) + n). Другими словами, его быстродействие пропорционально n(^2^) + n. Под словом "пропорционально" понимается, что можно найти такую константу к, для которой

Быстродействие = к * (n(^2^) + n)

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

Если величина n при тестировании алгоритма X достаточно велика, можно сказать, что влияние члена поглощается членом "n(^2^). Другими словами, при больших значениях n алгоритм O(n(^2^)+n) эквивалентен алгоритму O(n(^2^)). То же можно сказать и для n более высоких степеней. Так, для достаточно больших n влияние члена n(^2^) будет поглощено влиянием члена n(^3^). В свою очередь, влияние члена log(n) будет поглощаться влиянием члена n и т.д.