Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
Эксперименты были проведены повторно. При этом времена выполнения умножались на коэффициент 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 и т.д.
Из приведенного примера видно, что О-нотация подчиняется очень простым арифметическим правилам. Давайте предположим, что есть алгоритм, который выполняет несколько различных задач. Первая задача сама по себе принадлежит к классу О(n), вторая - к классу O(n(^2^)), а третья - к классу O(log(n)). Необходимо определить быстродействие алгоритма в целом. Ответом будет O(n(^2^)), поскольку к этому классу принадлежит доминантная часть алгоритма.
В этом и заключается первое замечание, касающееся выводов, следующих из О-нотации. Значения О большого являются репрезентативными для больших значений n. Для маленьких значений О-нотация не имеет смысла, а на общий результат оказывают влияние другие члены нотации. Например, предположим, что проводилось тестирование двух алгоритмов. На основе статистических данных были выведены следующие зависимости:
Быстродействие первого алгоритма = k1 * (n + 100000)
Быстродействие второго алгоритма = k2* n(^2^)
Пусть константы kl и k2 сравнимы по величине. Какой алгоритм лучше использовать? Если следовать О-нотации, то предпочтительнее будет первый алгоритм, поскольку он принадлежит к классу О(n). Тем не менее, если известно, что значение n в реальных условиях не будет превышать 100, более эффективным окажется второй алгоритм.
Таким образом, алгоритм нужно выбирать и с учетом его назначения - не только на основании О-нотации, но принимая во внимание время выполнения при средних значениях количества элементов (или, если угодно, условий использования), на которых алгоритм будет применяться. Следовательно, выбор алгоритма должен осуществляться только на основе измерения профилировщиком времени выполнения вашего приложения для ваших данных. Не полагайтесь ни на какие книги (в том числе и на эту), верьте только измеренному времени.
Лучший, средний и худший случаи
Помимо всего прочего, необходимо рассмотреть еще один вопрос. О-нотация относится к среднему случаю. Вернемся к нашим экспериментам, связанным с поиском элемента в массиве. Если бы фамилия "Smith" всегда была первым элементом в массиве, последовательный поиск был бы быстрее бинарного, - искомый элемент был бы обнаружен при первом же выполнении цикла. Такая ситуация известна под названием лучший случай. Для нашего примера в О-нотации ее можно представить как O(1) (т.е. выполнение алгоритма занимает одно и то же время независимо от количества элементов в массиве).