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

Однако при анализе низкой производительности существуют и некоторые трудности. Для определенных алгоритмов может существовать весомая разница между временем, необходимым для решения задачи в случае худших входных данных, и временем, необходимым в случае данных, которые встречаются на практике. Например, быстрое объединение в случае низкой производительности требует времени выполнения, пропорционального N, и пропорционального лишь logA для обычных данных. Часто не удается доказать, что существуют входные данные, для которых время выполнения алгоритма достигает определенного предельного значения; можно лишь доказать, что время выполнения будет ниже этого предела. Более того, для некоторых задач алгоритмы с хорошими показателями низкой производительности гораздо сложнее, чем другие алгоритмы для этих задач. Иногда возникает ситуация, когда алгоритм с хорошими характеристиками низкой производительности при работе с практическими данными оказывается медленнее, чем более простые алгоритмы, или же при незначительной разнице в скорости он требует дополнительных усилий для достижения хороших характеристик низкой производительности. Для многих приложений другие соображения - переносимость и надежность - являются более важными, чем гарантии, даваемые в случае низкой производительности. Например, как было показано в главе 1, взвешенное быстрое объединение со сжатием пути обеспечивает лучшие гарантии производительности, чем взвешенное быстрое объединение, но для типичных данных, встречающихся на практике, алгоритмы имеют почти одинаковое время выполнения.

Изучение средней производительности алгоритмов более существенно, поскольку оно позволяет делать предположения о времени выполнения программ. В простейшем случае можно точно охарактеризовать входные данные алгоритма, например, алгоритм сортировки может выполняться над массивом из Л случайных целых чисел или геометрический алгоритм может обрабатывать набор из N случайных точек на плоскости с координатами между О и 1. Затем мы можем подсчитать, сколько раз в среднем выполняется каждая инструкция, и вычислить среднее время выполнения программы, умножив частоту выполнения каждой инструкции на время ее выполнения и суммируя по всем инструкциям.

Однако и в анализе средней производительности существуют трудности. Во-первых, входная модель может неточно характеризовать входные данные, встречающиеся на практике, или же естественная модель входных данных может вообще не существовать. Мало кто будет возражать против использования таких моделей входных данных, как случайно упорядоченный файл , для алгоритма сортировки или случайный набор точек для геометрического алгоритма, и для таких моделей можно получить математические результаты, которые будут точными предположениями о производительности программ в реальных приложениях. Но как можно характеризовать входные данные для программы, которая обрабатывает текст на английском языке? Даже для алгоритмов сортировки в определенных приложениях рассматриваются другие модели кроме модели случайно упорядоченных данных. Во-вторых, анализ может требовать глубоких математических доказательств. Например, анализ случая средней производительности для алгоритмов union-find достаточно сложен. Хотя вы-

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

Во многих случаях на первое возражение можно ответить превращением случайности в достоинство. Например, если мы случайным образом взболтаем массив до сортировки, тогда допущение о том, что элементы массива находятся в случайном порядке, будет выполнено. Для таких алгоритмов, называемых рандомизированными алгоритмами, анализ средней производительности приводит к ожидаемому времени выполнения в строгом вероятностном смысле. Более того, часто можно доказать, что вероятность того, что такой алгоритм будет медленным, пренебрежимо мала. Примеры таких алгоритмов включают в себя быструю сортировку (см. главу 9), рандомизированные BST (см. главу 13) и хеширование (см. главу 14).

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

Анализ низкой производительности с использованием 0-нотации освобождает аналитика от необходимости включать в рассмотрение характеристики определенной машины. Выражение время выполнения алгоритма равно 0(f{N)) не зависит от входных данных и полезно для распределения алгоритмов по категориям в независимости от входных данных и деталей реализации, и таким образом отделяет анализ алгоритма от какой-либо определенной его реализации. В анализе мы, как правило, отбрасываем постоянные множители. В большинстве случаев, если мы хотим знать, чему пропорционально время выполнения алгоритма, - N или logV, - не имеет значения, где будет выполняться алгоритм - на небольшом компьютере или на суперкомпьютере; более того, не имеет значения даже то, хорошо или плохо реализован внутренний цикл алгоритма.

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

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

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

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

Верхняя и нижняя границы совпадают также и для алгоритмов union-find, использующих указатели. В 1975 г. Тарьян (Tarjan) показал, что алгоритм взвешенного быстрого объединения со сжатием пути требует следования по менее, чем 0{\g*V) указателям в случае низкой производительности, и что любой алгоритм с указателями должен следовать более, чем по постоянному числу указателей в случае низкой производительности для некоторых входных данных. Другими словами, нет смысла в поиске какого-либо нового улучшения, которое гарантировало бы решение задачи линейным числом операций i = a[i]. На практике эта разница очень мала, поскольку lg*f очень мало, тем не менее, нахождение простого линейного алгоритма для этой задачи было темой исследования в течение долгого времени, и найденная Та-рьяном нижняя граница направила усилия исследователей на другие задачи. Более того, история показывает, что нельзя обойти функции наподобие сложной функции log*, поскольку они присущи этой задаче.

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

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