Принципы анализа алгоритмов

Анализ алгоритмов

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

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

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

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

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

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

Первый шаг при анализе алгоритма состоит в определении абстрактных операций, на которых основан алгоритм, чтобы отделить анализ от реализации. Например, мы отделяем подсчет, сколько раз одна из реализаций алгоритма объединение-поиск запускает фрагмент кода $$i = a[i]$$, от выяснения, сколько наносекунд требуется для выполнения этого фрагмента кода на данном компьютере. Для определения реального времени выполнения программы на конкретном компьютере требуются оба этих элемента. Первый из них определяется свойствами алгоритма, а второй - свойствами компьютера. Такое разделение зачастую позволяет сравнивать алгоритмы таким способом, который не зависит от определенной реализации или от определенного типа компьютера.

Количество используемых абстрактных операций может оказаться очень большим, однако производительность алгоритма, как правило, зависит от нескольких величин, причем наиболее важные для анализа величины обычно определить несложно. Один из способов их определения заключается в использовании механизма профилирования (подсчитывает количество выполнений каждой инструкции, доступен во многих реализациях С++) для нахождения наиболее часто исполняемых частей программы по результатам нескольких пробных запусков. Или же, как алгоритмы объединение-поиск из раздела 1.3 , наша реализация может быть построена лишь на нескольких абстрактных операциях. В любом случае, анализ сводится к определению частоты исполнения нескольких фундаментальных операций. Принцип нашей работы заключается в том, чтобы отыскать приблизительные оценки этих величин, зная, что для важных программ при необходимости можно будет произвести полный анализ. Более того, как будет показано далее, часто можно достаточно точно предсказать результаты на основе приближенных аналитических результатов в сочетании с эмпирическим изучением.

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

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

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

Упражнения

Возрастание функций

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

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

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

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

Огромная разница между такими числами, как $$10^4$$ и $$10^8$$, становится более очевидной, если взять соответствующее количество секунд и перевести в привычные единицы измерения. Мы можем позволить программе выполняться 2,8 часа, но вряд ли мы будем созерцать программу, выполнение которой займет 3,1 года. Поскольку $$2^10$$ примерно равно $$10^3$$, этой таблицей можно воспользоваться и для перевода степеней 2. Например, $$2^{32}$$ секунд - это примерно 124 года.

При анализе алгоритмов возникает еще несколько функций. Например, алгоритм с $$N^2$$ входными данными, имеющий время выполнения $$N^3$$, можно рассматривать, как $$N^{3/2}$$ алгоритм. Кроме того, некоторые алгоритмы разбиваются на подзадачи в два этапа и имеют время выполнения, пропорциональное $$Nlog^2$$. Из таблица 2.1 видно, что обе эти функции гораздо ближе к $$NlogN$$, чем $$N^2$$.

Логарифмическая функция играет особую роль в разработке и анализе алгоритмов, поэтому ее стоит рассмотреть подробнее. Поскольку мы часто имеем дело с аналитическими результатами, которые различаются на постоянный множитель, мы используем запись "log N" без указания основания. Изменение основания логарифма меняет значение логарифма лишь на постоянный множитель, однако в определенных контекстах возникают особые значения основания логарифма.

В математике настолько важным является натуральный логарифм (основание e = 2,71828...), что распространено следующее сокращение: $$$\log{_{e}N}\equiv\ln{N}$$$. В вычислительной технике очень важен двоичный логарифм (основание равно 2), поэтому часто используется сокращение $$$\log{_{2}N}\equiv\lg{N}$$$.

Наименьшее целое число, большее $$lgN$$, равно количеству битов, необходимых для представления $$N$$ в двоичном формате; точно так же наименьшее целое, большее $$$\log{_{10}N}$$$, - это количество цифр, необходимое для представления $$N$$ в десятичном формате.

Оператор С++

          for (lgN = 0; N > 0; lgN++, N /= 2) ;
      

дает простой способ подсчета наименьшего целого, большего $$lgN$$. Вот аналогичный метод для вычисления этой функции:

        for (lgN = 0, t = 1; t < N; lgN++, t += t) ;
      

В нем подчеркивается, что $$${2^{n}}\leq{N}<{2^{n+1}}$$$, когда $$n$$ - это наименьшее целое, большее $$lgN$$.

Иногда бывает нужно вычислить логарифм логарифма, обычно для больших чисел. Например, $$ lglg2^{256} = lg 256 = 8 $$. Как видно из данного примера, обычно для практических целей выражение $$loglog N$$ можно считать константой, поскольку оно мало даже для очень больших $$N$$.

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

$$e = 2,71828...$$

$$$\gamma = 0,57721...$$$

$$$\phi=(1+\sqrt{5})/2=1,61803...$$$

$$ln2 = 0,693147...$$

$$ lge = 1/ln 2 = 1,44269...$$

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

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

$$$\lfloor{x}\rfloor$$$: наибольшее целое, меньшее или равное x

$$$\lceil{x}\rceil$$$: наименьшее целое, большее или равное х.

Например, $$$\lfloor{\pi}\rfloor$$$и $$$\lceil{e}\rceil$$$оба равны 3, а $$$\lceil{x}\rceil$$$ - это количество битов, необходимое для двоичного представления числа $$N$$. Другое важное применение этих функций возникает в том случае, когда необходимо поделить множество $$N$$ объектов пополам. Этого нельзя сделать точно, если $$N$$ является нечетным, поэтому для точности мы можем создать одно подмножество, содержащее $$$\lfloor{N/2}\rfloor$$$объектов, а второе - $$$\lceil{N/2}\rceil$$$объектов. Если $$N$$ четно, тогда размеры обоих поднаборов равны ( $$$\lfloor{N/2}\rfloor$$$= $$$\lceil{N/2}\rceil$$$); если же $$N$$ нечетно, то их размер отличается на единицу ($$$\lfloor{N/2}\rfloor + 1$$$ = $$$\lceil{N/2}\rceil$$$). В С++ можно напрямую подсчитать значения этих функций при выполнении операций над целыми числами (например, если $N\geq0$N, тогда $$ N/2$$ равно $$$\lfloor{\pi}\rfloor$$$ а $$N-(N/2)$$ равно $$$\lceil{x}\rceil$$$), а при операциях над числами с плавающей точкой можно воспользоваться функциями floor и ceil из заголовочного файла math.h.

При анализе алгоритмов часто возникает дискретизированная версия функции натурального логарифма, называемая гармоническими числами. N-е гармоническое число определяется выражением

$$$H_{N}=1+\dfrac{1}{2}+\dfrac{1}{3}+...+\dfrac{1}{N}$$$

Натуральный логарифм $$ln N$$ - это значение площади под кривой $$1/х$$ между 1 и $$N$$ ; гармоническое число H_N - это площадь под ступенчатой функцией, которую можно определить, вычисляя значения функции $$1/х$$ для целых чисел от 1 до $$N$$. Эта зависимость показана на рис 2.2.

Гармонические числа представляют собой приближенные значения площади под кривой 1/х. Постоянная y учитывает разницу между H_N и $$$\ln{N}=\int_{1}^{N}{dx/x}$$$

Формула

$$ $H_{N}\approx \ln{N}+\gamma +1/(12N)$$$ где $$$\gamma = 0,57721... $$$ (эта константа называется постоянной Эйлера), дает отличное приближение для H_N. В отличие от $$$\lceil{lgN}\rceil$$$и $$$\lfloor{lgN}\rfloor$$$ для вычисления H_N лучше воспользоваться библиотечной функцией log, а не подсчитывать его непосредственно из определения.

Последовательность чисел

$$ 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 ...$$ определяемая формулой $$$F_{N}=F_{N-1}+F_{N-2}$$$ где $$$N\geq2$$$ а $$F_0 = 0$$ и $$F_1 = 1$$ известна как числа Фибоначчи и имеет множество интересных свойств. Например, отношение двух последовательных чисел приближенно равно золотому сечению (golden ratio) $$$\phi=(1+\sqrt{5}/2 \approx 1,61803...$$$ Более подробный анализ показывает, что $$F_N$$ равно значению выражения $$$\phi^{N}/\sqrt{5}$$$ округленному до ближайшего целого числа.

При анализе алгоритмов часто встречается также функция факториал $$N!$$. Как и экспоненциальная функция, факториал возникает при лобовом решении задач и растет слишком быстро, чтобы такие решения представляли практический интерес. Он также возникает при анализе алгоритмов, поскольку представляет собой количество способов упорядочения $$N$$ объектов.

Для аппроксимации $$N!$$ используется формула Стирлинга:

$$ ${\lg{N}!}\approx{N\lg{N}}-N\lg{e}+\lg{\sqrt{2\pi N}}$$$.

Например, из формулы Стирлинга следует, что количество битов в представлении числа $$N!$$ примерно равно $$NlgN$$.

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

Например, классическое биномиальное распределение и распределение Пуассона играют важную роль при разработке и анализе некоторых фундаментальных поисковых алгоритмов, которые будут рассмотрены в и . Функции, не приведенные здесь, обсуждаются по мере их появления.

Упражнения

$$$\triangleright$$$ 2.5. Для каких значений $$N$$ справедливо $$ 10NlgN> 2N^2 $$ ?

$$$\triangleright$$$ 2.6. Для каких значений $$N$$ выражение $$N^{3/2}$$ имеет значение в пределах от $$ N(lgN)^2/2 $$ до $$ 2N(lgN)^2 $$ ?

О-нотация

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

О-нотация используется по трем различным причинам:

Третье назначение О-нотации рассматривается в разделе 2.7, а здесь мы обсудим два других.

Постоянные $$с_0$$ и $$N_0$$, не выраженные явно в О-нотации, часто скрывают практически важные подробности реализации. Очевидно, что выражение "алгоритм имеет время выполнения $$O(f (N))$$ " ничего не говорит о времени выполнения при $$N$$, меньшем $$N_0$$, а $$с_0$$ может иметь большое значение, необходимое для работы в наихудшем случае. Понятно, что лучше иметь алгоритм, время выполнения которого составляет $$N^2$$ наносекунд, а не $$log N$$ столетий, но мы не можем сделать такой выбор на основе О-нотации.

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

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

$$(N + O (1))(N + O (log N) + O (1))$$, то мы получим шесть слагаемых

$$ N^2 + O (N) + O (N log N) + O (log N) + O (N) + O (1) $$.

Однако можно отбросить все О-слагаемые, кроме наибольшего из них, и тогда останется приближенное выражение

$$ N^2 + O (N log N) $$.

То есть при больших $$N$$ хорошей аппроксимацией этого выражения является N^2. Эти действия интуитивно ясны, но О-нотация позволяет выразить их с математической точностью. Формула с одним О-слагаемым называется асимптотическим выражением (asymptotic expression).

В качестве более конкретного примера предположим, что (после некоторого математического анализа) мы выяснили, что определенный алгоритм имеет внутренний цикл, выполняемый в среднем $$ NH_N $$ раз, внешний раздел, выполняемый $$N$$ раз, и некоторый код инициализации, исполняемый однократно. Далее предположим, что (после тщательного исследования реализации) мы определили, что каждая итерация внутреннего цикла требует $$а_0$$ наносекунд, внешний раздел - $$а_1$$ наносекунд, а код инициализации - $$а_2$$ наносекунд. Тогда среднее время выполнения программы (в наносекундах) равно $$ 2а_0 N H_N + a_1 + а_2 $$.

Поэтому для времени выполнения справедлива следующая формула: $$ 2а_0 NH_N + O(N) $$.

Эта более простая формула важна, поскольку из нее следует, что для аппроксимации времени выполнения при больших $$N$$ нет необходимости искать значения величин $$ а_1$$ и $$а_$$2 . В общем случае, в точном математическом выражении для времени выполнения может содержаться множество других слагаемых, ряд которых трудно анализировать. О-нотация обеспечивает способ получения приближенного ответа для больших $$N$$, не заботясь о подобных слагаемых.

Далее, О-нотация позволяет в данном примере выразить время выполнения через более знакомую функцию $$lnN$$. С помощью таблица 2.3 полученное выражение можно приближенно записать как $$ H_N = lnN + O(1) $$. Таким образом, асимптотическое выражение для общего времени выполнения алгоритма имеет вид $$ 2a_0lnN + O(N) $$. То есть при больших $$N$$ оно будет близко к легко вычисляемому выражению $$ 2a_0lnN $$. Постоянный множитель $$а0$$ зависит от времени выполнения инструкций внутреннего цикла.

Более того, нам не нужно знать значения $$a0$$, чтобы предсказать, что при больших $$N$$ время выполнения для входных данных размером $$2N$$ будет вдвое больше, чем для входных данных размером $$N$$, поскольку $$$\dfrac{2a_{0}(2N)\ln{#2N#}+O(2N)}{2a_{0}N\ln{N}+O(N)}=\dfrac{2\ln{(2N)}+O(1)}{\ln{N}+O(1)}=2+O\left(\dfrac{1}{\log{N}}\right)$.$$

Таким образом, асимптотическая формула позволяет нам делать точные прогнозы, не вдаваясь в подробности реализации или анализа. Отметьте, что такое предсказание не было бы возможным, если бы О-аппроксимация была задана только для главного члена.

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

Когда функция $$f (N)$$ асимптотически велика по сравнению с другой функцией $$g (N)$$ (т.е. $$$g(N)/f(N)\rightarrow0$$$ при $$$N\rightarrow\infty$$$), иногда в данной книге мы будем использовать термин (конечно, неточный) порядка $$f(N)$$, что означает $$f (N) + O(g(N))$$. Потеря математической точности компенсируется большей наглядностью, так как нас больше интересует производительность алгоритмов, а не математические детали. В таких случаях мы можем быть уверены в том, что при больших (а, может, даже и всех) значениях $$N$$ исследуемая величина будет близка к $$f(N)$$. Например, даже если мы знаем, что некоторая величина равна $$N (N - 1) / 2$$, ее можно рассматривать как $$ N^2/ 2 $$. Такой способ выражения результатов более понятен, чем подробный и точный результат, и, к примеру, при $$N= 1000$$ отличается от правильного значения всего лишь на 0,1%. Потеря точности в данном случае намного меньше, чем при распространенном использовании $$O(f (N))$$. При описании производительности алгоритмов мы будем по возможности стараться быть и точными, и краткими.

В похожем ключе мы иногда говорим, что время выполнения алгоритма пропорционально $$f (N)$$, т.е. можно доказать, что оно равно с $$f (N) + g(N), где g(N)$$ асимптотически мало по сравнению с $$f (N)$$. При таком подходе можно предсказать время выполнения для $$2N$$, если оно известно для $$N$$, как в рассмотренном выше примере. На рис. 2.3 рис 2.3 приводятся значения множителей для таких прогнозов поведения функций, которые часто возникают при анализе алгоритмов. В сочетании с эмпирическим изучением (см. раздел 2.1) данный подход освобождает от определения постоянных величин, зависящих от реализации. Или же, применяя его в обратном направлении, зачастую мы можем выдвинуть гипотезу о функциональной зависимости времени выполнения программы, изучив, как меняется время выполнения при удвоении $$N$$.

Различия между О-оценками пропорционально (is proportional to) и порядка (about) проиллюстрированы на рис 2.4 и рис 2.5. О-нотация используется, прежде всего, для исследования фундаментального асимптотического поведения алгоритма; пропорционально требуется при экстраполяции производительности на основе эмпирического изучения, а порядка - при сравнении производительности или при предсказании абсолютной производительности.

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

На этой схематической диаграмме осциллирующая кривая представляет собой функцию $$g(N)$$, которую мы пытаемся аппроксимировать; плавная черная кривая представляет собой другую функцию, $$f(N)$$, которая используется для аппроксимации, а плавная серая кривая является функцией $$cf(N)$$ с некоторой неопределенной постоянной $$c$$. Вертикальная прямая задает значение $$N0$$, указывающее, что аппроксимация справедлива для $$ N > N_0 $$. Когда мы говорим, что $$g(N) = O(f(N))$$, мы лишь ожидаем, что значение функции $$g(N)$$ находится ниже некоторой кривой, имеющей форму функции $$f(N)$$, и правее некоторой вертикальной прямой. Поведение функции $$f(N)$$ может быть любым (например, она не обязательно должна быть непрерывной).

Когда говорят, что функция $$g(N)$$ пропорциональна функции $$f(N)$$ (верхний график), то подразумевают, что она растет как $$f(N)$$, но, возможно, смещена относительно последней на неизвестный коэффициент. Если задано некоторое значение $$g(N)$$, можно предсказать поведение функции при больших $$N$$. Когда говорят, что $$g(N)$$ порядка $$f(N)$$ (нижний график), то подразумевают, что функцию $$f$$ можно использовать для достаточно точной оценки значений функции g.

Упражнения

$$$\triangleright$$$ 2.20. Докажите, что О(1) - то же самое, что и О(2).

2.21. Докажите, что в выражениях с О-нотацией можно выполнить любое из перечисленных преобразований:

$$ \begin{align*} f(N)\rightarrow O(f(N))\\ cO(f(N))\rightarrow O(f(N))\\ O(cf(N))\rightarrow O(f(N))\\ f(N)-g(N)=O(h(N))\rightarrow f(N)=g(N)+O(h(N))\\ O(f(N))O(g(N))\rightarrow O(f(N)g(N))\\ O(f(N))+O(g(N))\rightarrow O(g(N))\\ \end{align*} $$

Простейшие рекурсии

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

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

Для заданного двоичного представления числа $$N$$ (в центре) отбрасывание правого бита дает $$$\lfloor N/2\rfloor$$$. То есть количество битов в двоичном представлении числа $$N$$ на единицу больше, чем в представлении числа $$$\lfloor N/2\rfloor$$$. Поэтому количество битов в двоичном представлении числа - $$$N\lfloor N/2\rfloor+1$$$ - является решением формулы 2.2 в случае интерпретации N/2 как $$$\lfloor N/2\rfloor$$$.

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

Упражнения

Примеры анализа алгоритмов

Вооружившись инструментами, о которых было рассказано в трех предыдущих разделах, мы рассмотрим анализ последовательного поиска и бинарного поиска - двух основных алгоритмов для определения того, входит ли некоторая последовательность объектов в заданное множество объектов. Наша цель - показать, как можно сравнивать алгоритмы, а не подробно описать сами алгоритмы. Для простоты предположим, что все рассматриваемые объекты являются целыми числами. Более общие приложения будут подробно рассмотрены в лекциях 12 - 16 . Простые версии алгоритмов, которые мы сейчас рассмотрим, не только демонстрируют многие аспекты задачи их разработки и анализа, но и имеют практическую ценность.

Например, представим себе компанию, обрабатывающую кредитные карточки и имеющую $$N$$ рискованных или украденных кредитных карточек. При этом компании необходимо проверять, нет ли среди $$M$$ транзакций какого-либо из этих $$N$$ плохих номеров. Для большей конкретности будем считать $$N$$ большим (скажем, порядка $$10^3$$ - $$10^6$$), а $$M$$ - огромным (порядка $$10^6$$ - $$10^9$$). Цель анализа заключается в приблизительной оценке времен выполнения алгоритмов, когда параметры принимают значения из указанного диапазона.

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

Для анализа алгоритма прежде всего отметим, что время выполнения зависит от того, находится ли требуемый объект в массиве. Если поиск не является успешным, мы можем определить это, только проверив все $$N$$ объектов, но успешный поиск может завершиться на первом, втором или любом другом объекте.

Поэтому время выполнения зависит от данных. Если бы все поиски выполнялись для чисел, которые находятся в первой позиции, то алгоритм был бы быстрым; если бы они выполнялись для чисел, находящихся в последней позиции, тогда алгоритм был бы медленным. В разделе 2.7 мы обсудим разницу между возможностью гарантировать производительность и предсказать производительность. В данном случае лучшее, что мы можем гарантировать - это что будет просмотрено не более $$N$$ чисел.

Однако чтобы сделать прогноз, необходимо какое-то предположение о данных. В данном случае предположим, что все числа выбраны случайным образом.

Программа 2.1. Последовательный поиск

Данная функция проверяет, находится ли число v среди элементов массива a[l] , a[l+1], ..., a[r], путем последовательного сравнения с каждым элементом, начиная с начала. Если по достижении последнего элемента нужное значение не найдено, функция возвращает значение -1. Иначе она возвращает индекс элемента массива, содержащего искомое число.

int search(int a[], int v, int l, int r) {
  for (int i = l; i <= r; i++)
    if (v == a[i]) return i;
  return -1;
}
      

Из этого предположения следует, например, что предметом поиска с одинаковой вероятностью может оказаться каждое число в таблице. После некоторых размышлений мы приходим к выводу, что именно это свойство поиска является наиболее важным, потому что среди случайно выбранных чисел вряд ли найдется нужное нам (см. упражнение 2.48). В некоторых приложениях количество транзакций с успешным поиском может быть высоким, а в других - низким. Чтобы не запутывать модель свойствами приложения, мы разобьем задачу на два случая (успешный и неудачный поиск) и проанализируем их независимо. Данный пример иллюстрирует, что важным моментом эффективного анализа является разработка разумной модели приложения. Наши аналитические результаты будут зависеть от доли успешных поисков; более того, они обеспечат нас информацией, необходимой для выбора различных алгоритмов для разных приложений на основании этого параметра.

Из леммы 2.1 следует, что время выполнения программы 2.1 пропорционально $$N$$, если средняя стоимость сравнения двух чисел постоянна. Значит, к примеру, можно ожидать, что если удвоить количество объектов, то и время, необходимое для поиска, также удвоится.

Последовательный поиск в случае неудачи можно ускорить, если упорядочить числа в таблице. Сортировка чисел в таблице является предметом рассмотрения глав 6-11. Несколько алгоритмов, которые мы рассмотрим, выполняют эту задачу за время, пропорциональное $$N logN$$, которое незначительно по сравнению со стоимостью поиска при очень больших M. В упорядоченной таблице можно прервать поиск сразу по достижении числа, большего, чем искомое. Такое изменение уменьшает стоимость последовательного поиска до N/ 2 чисел, которые необходимо в среднем проверить при неудачном поиске, что совпадает с затратами для успешного поиска.

Другой способ выразить результат леммы 2.2 - это сказать, что время выполнения последовательного поиска пропорционально $$MN$$ для $$M$$ транзакций и в среднем, и в худшем случае. Если удвоить или количество транзакций, или количество объектов в таблице, то время выполнения удвоится; если мы удвоим обе величины одновременно, то время выполнения увеличится в 4 раза. Этот результат говорит о том, что данный метод не годится для очень больших таблиц. Если для проверки одного числа требуется c микросекунд, а $$ M= 10^9 $$ и $$ N= 10^6 $$, то время выполнения для всех транзакций будет равно, по крайней мере, $$ (с / 2)10^9 $$ секунд, или, согласно рис 2.1, около 16c лет, что недопустимо.

Программа 2.2. Бинарный поиск

Эта программа делает то же самое, что и программа 2.1, но гораздо эффективнее.

int search(int a[], int v, int l, int r) {
  while (r >= l) {
    int m = (l+r)/2;
    if ( v == a[ m] ) return m;
    if (v < a[m]) r = m-1; else l = m+1;
  }
  return -1;
}
      

Программа 2.2 представляет собой классическое решение задачи поиска методом, гораздо более эффективным, чем последовательный поиск. Он основан на идее, что если числа в таблице упорядочены, то после сравнения искомого значения с числом из середины таблицы мы можем отбросить половину из них. Если они равны, значит, поиск завершен успешно, если искомое число меньше, то мы применим этот же метод к левой части таблицы, а если больше - то к правой. На рис 2.7 представлен пример выполнения этого метода на множестве чисел.

Чтобы проверить, содержится ли число 5025 в таблице, приведенной в левой колонке, мы сначала сравниваем его с 6504, из чего следует, что дальше необходимо рассматривать первую половину массива. Затем производится сравнение с числом 4548 (середина первой половины), что приводит нас ко второй половине первой половины. Мы продолжаем этот процесс, постоянно работая с подмассивом, в котором может содержаться искомое число, если оно есть в таблице. В заключение мы получаем подмассив с одним элементом, не равным 5025, из чего следует, что 5025 в таблице не содержится.

Лемма 2.3 позволяет решить очень большую задачу поиска в 1 миллионе чисел при помощи 20 сравнений на транзакцию, то есть быстрее, чем требуется для чтения или записи числа на большинстве современных компьютеров. Задача поиска настолько важна, что было разработано несколько еще более быстрых методов, чем приведенный здесь (см. лекции 12 - 16).

В формулировках лемм 2.1 и 2.2 используются операции, наиболее часто выполняемые над данными. Как отмечено в комментарии, следующем за леммой 2.1, мы предполагаем, что каждая операция должна занимать постоянное время, тогда можно заключить, что время выполнения бинарного поиска пропорционально lgN, в отличие от $$N$$ для последовательного поиска. При удвоении $$N$$ время бинарного поиска несколько увеличивается, но не удваивается, как это имеет место для последовательного поиска. С ростом $$N$$ разница между двумя методами становится огромной.

Аналитическое доказательство лемм 2.1 и 2.2 можно проверить, написав программу и протестировав алгоритм. Например, в и 11. Кроме того, использование библиотечных и внешних функций и другие детали создания программ из отдельных компонентов, включая и функцию sort, объясняются в . Так что пока мы просто подчеркнем, что проведение эмпирического тестирования - это неотъемлемая часть оценки эффективности алгоритма.

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

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

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

Упражнения

Приведенные ниже относительные времена выполнения подтверждают наши аналитические результаты: в случае $$M$$ поисков в таблице из $$N$$ объектов время последовательного поиска пропорционально MN, а время бинарного поиска - $$M lgN$$. При удвоении $$N$$ время последовательного поиска также удваивается, а время бинарного поиска ненамного увеличивается. Последовательный поиск неприменим для очень больших $$M$$ и $$N$$, а бинарный поиск выполняется достаточно быстро даже для огромных таблиц.

Обозначения:

S последовательный поиск (программа 2.1)

B бинарный поиск (программа 2.2)

Гарантии, предсказания и ограничения

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

Изучение производительности алгоритмов в худшем случае привлекательно тем, что оно позволяет гарантированно сказать что-либо о времени выполнения программ. Мы говорим, что количество выполнений определенных абстрактных операций меньше, чем определенная функция от объема входных данных, независимо от значений этих данных. Например, лемма 2.3 представляет собой пример такой гарантии для бинарного поиска, а лемма 1.3 - для взвешенного быстрого объединения. Если гарантированное время мало, как в случае с бинарным поиском, то это хорошо: значит, удалось устранить ситуации, когда программа работает медленно. Поэтому программы с хорошими характеристиками в худшем случае являются основной целью разработки алгоритмов.

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

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

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

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

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

Анализ производительности в худшем случае с использованием О-нотации освобождает аналитика от необходимости включать в рассмотрение характеристики конкретной машины. Выражение "время выполнения алгоритма равно Of(N))" не зависит от входных данных, полезно для распределения алгоритмов по категориям вне зависимости от входных данных и деталей реализации и таким образом отделяет анализ алгоритма от любой конкретной его реализации. В анализе мы, как правило, отбрасываем постоянные множители. В большинстве случаев, если нужно знать, чему пропорционально время выполнения алгоритма - $$N$$ или $$ logN$$ - не имеет значения, где будет выполняться алгоритм: на небольшом компьютере или на суперкомпьютере. Не имеет значения даже то, хорошо или плохо реализован внутренний цикл алгоритма.

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

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

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

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

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

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

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

Упражнение

2.51. Известно, что временная сложность одной задачи равна N*log N, а другой - N3. Что следует из данного утверждения об относительной производительности алгоритмов, которые решают эти задачи?

Ссылки к части I

Существует множество начальных учебников по программированию. Стандартный справочник по языку C++ - книга Страуструпа (Stroustup), а наилучшим источником конкретных сведений о C с примерами программ, многие из которых верны и для C++ и написаны в том же духе, что и программы в этой книге, является книга Кернигана и Ричи (Kernigan, Ritchie).

Несколько вариантов алгоритмов для задачи объединение-поиск из собраны и объяснены в статье Ван Левена и Тарьяна (van Leewen, Tarjan).

В книгах Бентли (Bentley) описаны в том же стиле, что и изложенный здесь материал, несколько подробных примеров использования различных подходов при разработке и реализации алгоритмов для решения различных интересных задач.

Классический справочник по анализу алгоритмов на основе измерений асимптотической производительности в худшем случае - это книга Ахо, Хопкрофта и Ульмана (Aho, Hopcroft, Ullman). Книги Кнута (Knuth) содержат более полный анализ средней производительности и являются заслуживающим доверия описанием конкретных свойств многих алгоритмов. Более современные работы - книги Гонне, Баеса-Ятеса (Gonnet, Baeza-Yates) и Кормена, Лейзерсона, Ривеста (Cormen, Leiserson, Rivest). Обе они содержат обширные списки ссылок на исследовательскую литературу.

Книга Грэма, Кнута, Паташника (Graham, Knuth, Patashnik) рассказывает о разделах математики, которые обычно встречаются при анализе алгоритмов; этот же материал разбросан и в упомянутых ранее книгах Кнута. Книга Седжвика и Флажоле (Sedgewick and Flajolet) представляет собой исчерпывающее введение в предмет.

1. A.V Aho, J.E. Hopcroft, and J.D. Ullman, The Design and Analysis of Algorithms, Addison-Wesley, Reading, MA, 1975.

2. J.L. Bentley, Programming Pearls, Addison-Wesley, Reading, MA, 1985; More Programming Pearls, Addison-Wesley, Reading, MA, 1988.

3. R. Baeza-Yates and G.H. Gonnet, Handbook of Algorithms and Data Stru^ures, second edition, Addison-Wesley, Reading,MA, 1984.

4. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн, Алгоритмы: построение и анализ, 2-е издание, ИД "Вильямс", 2009 г.

5. R.L. Graham, D.E. Knuth, and O. Patashnik, Con^ete Mathemattes, Addison-Wesley, Reading, MA, 1988.

6. Брайан У. Керниган, Деннис М. Ритчи, Язык программирования C (Си), 2-е издание, ИД "Вильямс", 2008 г.

7. Д.Э. Кнут, Искусство программирования, том 1: Основные алгоритмы, 3-е издание, ИД "Вильямс", 2008 г.; Д.Э. Кнут, Искусство программирования, том 2: Получисленные алгоритмы, 3-е издание, ИД "Вильямс", 2008 г.; Д.Э. Кнут, Искусство программирования, том 3. Сортировка и поиск, 2-е издание, ИД "Вильямс", 2008 г.

8. R. Sedgewick and P. Flajolet, An Introdu^on to the Analysis of Algorithms, Addison-Wesley, Reading, MA, 1996.

9. B. Stroustrup, The C+ + Programming Language, third edition, Addison-Wesley, Reading MA, 1997.

10. J. van Leeuwen and R.E. Tarjan, "Worst-case analysis of set-union algorithms", Journal of the ACM, 1984.