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

О 1 1 2 3 5 8 13 21 34 55 89 144 233 377...

определенная формулой

Fn = Fn-i + Fn-2 , где 7V> 2, а Л, = О и /i = 1

известна, как числа Фибоначчи. Эти числа имеют множество интересных свойств. Например, отношение двух последовательных чисел приближенно равно золотому сечению (golden ratio) ф = (1+л/5 ) / 2 1.61803... . Более подробный анализ показывает, что

Fff равно значению выражения I, округленному до ближайшего целого числа.

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

\sN\N\gN-N\ge + \g4b

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

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

Упражнения

> 2.5 Для каких значений Л справедливо 10Л IgA > 27V ?

О 2.6 Для каких значений iV выражение N имеет значение в пределах от N(\Nf/ 2 до 2mgN)7

2.7 Для каких значений Л справедливо 2NHn - N < N\$N + ION ?

о 2.8 Для какого наименьшего значения Л справедливо logic logioA > 8?

о 2.9 Докажите, что \ \gNJ + 1 - это количество бит, необходимое для представления числа Л в двоичной форме.

2.10 Добавьте в табл. 2.2 колонки для N(lgN) и N.

2.11 Добавьте в табл. 2.2 строки для и Ю инструкций в секунду.

2.12 Нацишоте на С++ функцию, которая подсчитывает Н, используя функцию log из стандартной математической библиотеки.

2.13 Напишите эффективную функцию на С++, подсчитывающую fig Ig ЛП. Не используйте библиотечную функцию.

2.14 Сколько цифр в десятичном представлении числа 1 миллион факториал?

2.15 Сколько бит в двоичном представлении числа lg(A!)?

2.16 Сколько бит в двоичном представлении Hl 2.11 Приведите простое выражение для Llg/>..

о 2.18 Приведите наименьшие значения N, для которых [Яд?] = /, где 1 </< 10.

2.19 Приведите наибольшее значение N, для которого можно решить задачу, требующую выполнения f(N) инструкций, на машине с быстродействием 10 операций в Секунду для следующих функций f(N): N, N , 2 N Н, N IgiV Ig lgj¥ и

2.4 0-нотация

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

Определение 2.1 Говорят, что функция g(N) является 0(f(N)), если существуют такие постоянные Со и No, что g(N) < Cof (N) для всех N > Nq.

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

Чтобы ограничить ошибку, возникающую при отбрасывании малых слагаемых в математических формулах.

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

Чтобы классифицировать алгоритмы согласно верхней границе их общего времени выполнения.

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

Постоянные Со и Ло, не выраженные явно в 0-нотации, часто скрывают практически важные подробности реализации. Очевидно, что выражение алгоритм имеет время выполнения 0{f{N)) ничего не говорит о времени выполнения при N, меньшем Ло, а Со может иметь большое значение, необходимое, чтобы обойти случай нежелательной низкой производительности. Нам хотелось бы использовать алгоритм, время выполнения которого составляет N наносекунд, а не log столетий, но мы не можем сделать такого выбора на основе 0-нотации.

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

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

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

{N+ 0{\)){N+ O(logA) + 0(1)),

то мы получим шесть слагаемых

+ 0{N) + 0(7Vlog yV) + 0(log + 0{N) + 0(1).

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

+ 0(N log N).

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

В качестве более важного примера предположим (после некоторого математического анализа), что определенный алгоритм имеет внутренний цикл, итерируемый в среднем ЛЯдг раз, внешнюю секцию, итерируемую N раз, и некоторый код инициализации, исполняемый единожды. Далее предположим, что мы определили (после тщательного исследования реализации), что каждая итерация внутреннего цикла требует flo наносекунд, внешняя секция - й] наносекунд, а код инициализации - Аг наносекунд. Тогда среднее время выполнения программы (в наносекундах) равно

laN Hn+ aiN+ aj.

Поэтому для времени выполнения справедлива следующая формула: 2aoNHi+ 0{N).

Более простая формула важна, поскольку из нее следует, что при больших N нет необходимости искать значения величин а\ и й2 для аппроксимации времени выполнения. В общем случае, в точном математическом выражении для времени выполнения может содержаться множество других слагаемых, ряд из которых трудно анализировать. 0-нотация обеспечивает способ получения приближенного ответа для больших N без привлечения слагаемых подобного рода.

Продолжая данный пример, можно воспользоваться 0-нотацией, чтобы выразить время выполнения с помощью известной функции, InN. Благодаря 0-нотации, приближенное выражение из табл. 2.3 можно записать как Яд = InTV + 0(1). Таким образом, aoNlnN + 0(N) - это асимптотическое выражение для общего времени выполнения алгоритма. То есть, при больших N оно будет близко к легко вычисляемому выражению 2aoN\nN. Постоянный множитель зависит от времени, которое требуется для выполнения инструкций внутреннего цикла.

Более того, нам не нужно знать значения ао, чтобы предсказать, что время выполнения для ввода размером 2N будет вдвое больше, чем для ввода размером N, для больших N, поскольку