Кроме того, необходимо изучать данные и моделировать их ввод, который ожидает алгоритм. Чаще всего мы будем рассматривать один из двух подходов к анализу: или мы будем предполагать, что ввод является случайным, и изучать среднюю производительность программы, или же мы будем рассматривать произвольный ввод и изучать низкую производительность программы. Процесс описания случайного ввода для многих алгоритмов достаточно сложен, но для других алгоритмов он может быть прямолинейным и вести к аналитическим результатам, дающим полезную информацию. Средней может быть математическая функция, не зависящая от данных, для которых используется программа, а наихудшей - странная конструкция, которая никогда не встречается на практике, но в большинстве случаев эти виды анализа предоставляют полезную информацию о производительности. Например, мы можем сравнить аналитические и эмпирические результаты (см. раздел 2.1). Если они совпадут, мы повысим нашу уверенность в обоих вариантах; если они не совпадут, мы сможем узнать больше об алгоритме и модели, изучив несоответствия.

В следующих трех разделах мы кратко рассмотрим математические инструменты, которыми будем пользоваться в течение всей книги. Этот материал находится за пределами нашей первоначальной узкой задачи, поэтому читатели, хорошо знакомые с математической основой, или же те, кто не собирается подробно проверять наши математические выражения, связанные с производительностью алгоритмов, могут перейти сразу к разделу 2.6 и вернуться к этому материалу там, где это указано в книге позже. Математические основы, в общем-то, не сложны для понимания и настолько близки к коренным вопросам разработки алгоритма, что их не стоит игнорировать тем, кто стремится эффективно использовать компьютер.

Вначале, в разделе 2.3, рассматриваются математические функции, которые потребуются для описания характеристик производительности алгоритмов. Затем, в разделе 2.4, рассматривается 0-нотация (0-notation) и выражение пропорционально (is proportional to), которое позволяет опустить детали при математическом анализе. Далее, в разделе 2.5, изучается понятие рекуррентных соотношений (recurrence relations), основного аналитического инструмента, используемого для отражения характеристик производительности алгоритма в математических выражениях. Следуя этому обзору, в разделе 2.6 приводятся примеры, в которых все эти инструменты применяются для анализа некоторых алгоритмов.

Упражнения

2.3 Найти выражение вида cq + c\N + cjN + сзЛ, которое точно описывает время выполнения программы из упражнения 2.2. Сравнить время, задаваемое этим выражением, с реальным при Л = 10, 100 и 1000.

2.4 Найти выражение, которое точно описывает время выполнения профаммы 1.1 в величинах М и N.

23 Рост функций

Большинство алгоритмов имеют главный параметр N, который значительно влияет на время их выполнения. Параметр 7V может быть степенью полинома, размером файла при сортировке или поиске, количеством символов в строке или некоторой

другой абстрактной мерой размера рассматриваемой задачи: чаще всего, он прямо пропорционален величине обрабатываемого набора данных. Когда таких параметров существует более одного (например. Ми Лв алгоритмах union-fmd, которые обсуждались в разделе 1.3), мы часто сводим анализ к одному параметру, задавая его как функцию других, или рассматривая одновременно только один параметр (считая остальные постоянными), и, таким образом, ограничивая себя рассмотрением только одного параметра N без потерь общности. Нашей целью является выражение ресурсных требований программ (как правило, времени выполнения) в зависимости от N с использованием математических формул, которые максимально просты и справедливы для больших значений параметров. Алгоритмы в этой книге обычно имеют время выполнения, пропорциональное одной из следующих функций:

1 Большинство инструкций большинства программ запускается один или

несколько раз. Если все инструкции программы обладают таким свойством, мы говорим, что время выполнения программы постоянно.

log N Когда время выполнения программы является логарифмическим, программа становится медленнее с ростом N. Такое время выполнения обычно присуще программам, которые сводят большую задачу к набору меньших задач, уменьшая на каждом шаге размер задачи на некоторый постоянный фактор. В интересующей нас области мы будем рассматривать время выполнения, являющееся небольшой константой. Основание логарифма изменяет константу, но не намного: когда N - тысяча, logA равно 3, если основание равно 10, или порядка 10, если основание равно 2; когда равно миллиону, значения logA только удвоятся. При удвоении logTV растет на постоянную величину, а удваивается лишь тогда, когда 7V достигает N,

N Когда время выполнения программы является линейным, это обычно зна-

чит, что каждый входной элемент подвергается небольшой обработке. Когда равно миллиону, такого же и время выполнения. Когда 7V удваивается, то же происходит и со временем выполнения. Эта ситуация оптимальна для алгоритма, который должен обработать N вводов (или произвести выводов).

AlogA Время выполнения, пропорциональное NlogN, возникает тогда, когда алгоритм решает задачу, разбивая ее на меньшие подзадачи, решая их независимо и затем объединяя решения. Из-за отсутствия подходящего прилагательного { линерифмический ?) мы просто говорим, что время выполнения такого алгоритма равно N logVV. Когда N равно 1 миллион, AlogTV около 20 миллионов. Когда удваивается, тогда время выполнения более чем удваивается.

Л Когда время выполнения алгоритма является квадратичным, он полезен

для практического использования для относительно небольших задач. Квадратичное время выполнения обычно появляется в алгоритмах, которые обрабатывают все пары элементов данных (возможно, в цикле двойного уровня вложенности). Когда N равно 1 тысяче, время выполнения равно 1 миллиону. Когда 7V удваивается, время выполнения увеличивается вчетверо.

Л Похожий алгоритм, который обрабатывает тройки элементов данных

(возможно, в цикле тройного уровня вложенности), имеет кубическое время выполнения и практически применим лишь для малых задач. Когда N равно 100, время выполнения равно 1 миллиону. Когда Л/ удваивается, время выполнения увеличивается в восемь раз.

Лишь несколько алгоритмов с экспоненциальным временем выполнения имеет практическое применение, хотя такие алгоритмы возникают естественным образом при попытках прямого решения задачи. Когда Л/ равно 20, время выполнения равно 1 миллиону. Когда jV удваивается, время выполнения учетверяется!

Время выполнения определенной программы, скорее всего, будет некоторой константой, умноженной на один из этих элементов {главный член) плюс меньшие слагаемые. Значения постоянного коэффициента и остальных слагаемых зависят от результатов анализа и деталей реализации. В грубом приближении коэффициент при главном члене связан с количеством инструкций во внутреннем цикле: на любом уровне разработки алгоритма разумно сократить количество таких инструкций. Для больших Л/ доминирует эффект главного члена, для малых N ллvi для тщательно разработанных алгоритмов вклад дают и другие слагаемые, поэтому сравнение алгоритмов становится более сложным. В большинстве случаев мы будем называть время выполнения программ просто линейным , Л logTV , кубическим и т.д. Обоснование этого подробно приводится в разделе 2.4.

В итоге, чтобы уменьшить общее время выполнения программы, мы минимизируем количество инструкций во внутреннем цикле. Каждую инструкцию необходимо подвергнуть исследованию: является ли она необходимой? Существует ли более эффективный способ выполнить такую же задачу? Некоторые программисты считают, что автоматические инструменты, содержащиеся в современных компиляторах, могут создавать наилучший машинный код; другие утверждают, что наилучшим способом является написание внутренних циклов вручную на машинном языке, или ассемблере. Обычно мы будем останавливаться, доходя до рассмотрения оптимизации на таком уровне, хотя иногда будем указывать, сколько машинных инструкций требуется для выполнения определенных операций. Это потребуется для того, чтобы понять, почему на практике одни алгоритмы могут оказаться быстрее других.

Для малых задач в том, каким методом мы воспользуемся, практически нет различий - быстрый современный компьютер все равно выполнит задачу мгновенно. Но по мере роста задачи, числа, с которыми мы имеем дело, становятся огромными, как продемонстрировано в табл. 2.1. Когда количество исполняемых инструкций в медленном алгоритме становится по-настоящему большим, время, необходимое для их выполнения, становится недостижимым даже для самых быстрых компьютеров. На рис. 2.1 приведен перевод большого количества секунд в дни, месяцы, годы и т.д.; в табл. 2.2 показаны примеры того, как быстрые алгоритмы имеют больше возможностей помочь решить задачу, не вовлекая огромные времена выполнения, нежели даже самые быстрые компьютеры.