РИСУНОК 2.1 ПЕРЕВОД СЕКУНД

Огромная разница между такими числами, как 10 и 10 становится более очевидной, когда мы рассмотрим их как количество секунд и переведем в привычные единицы измерения. Мы можем позволить программе выполняться 2.8 часа, но вряд ли мы сможем созерцать программу, выполнение которой займет 3.1 года. Поскольку 2° примерно равно 10, этой таблицей можно воспользоваться и для перевода степеней 2. Например, 2 секунд это примерно 124 года.

Таблица 2.1 Значения часто встречающихся функций

В этой таблице показаны относительные величины некоторых функций, которые будут часто встречаться нам при анализе алгоритмов. Очевидно, доминирующей является квадратичная функция, особенно для больших значений Л/, а значения между меньшими функциями оказываются не такими, как можно было ожидать для малых N. Например, Л/ больше, чем N\qN для огромных значений Л/, однако для небольших N наблюдается обратная ситуация. Точное время выполнения алгоритма должно включать в себя линейную комбинацию этих функций. Мы можем легко отделить быстрые алгоритмы от медленных из-за огромной разницы между, например, 1дЛ/ и N или Л/ и N, но различие между двумя быстрыми алгоритмами может потребовать тщательного изучения.

Таблица 2.2 Время для решения гигантских задач

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

Распечатано программой РтеРмШ - Купить w

При анализе алгоритмов возникает еще несколько функций. Например, алгоритм с вводами, имеющий время выполнения можно рассматривать, как N алгоритм. Кроме того, некоторые алгоритмы, разбиваемые на две подзадачи, имеют время выполнения, пропорциональное N\oN. Из табл. 2.1 очевидно, что обе эти функции ближе к N\o%N, чем 7V.

Логарифмическая функция играет специальную роль в разработке и анализе алгоритмов, поэтому ее стоит рассмотреть подробнее. Поскольку мы часто имеем дело с аналитическими результатами, в которых опущен постоянный множитель, мы используем запись log TV , опуская основание. Изменение основания логарифма меняет значение логарифма лищь на постоянный множитель, однако, в определенном контексте возникают специальные значения основания логарифма. В математике настолько важным является натуральный логарифм (основание е = 2.71828...), что распространено следующее сокращение: logW = In Ж В вычислительной технике очень важен двоичный логарифм (основание равно 2), поэтому используется сокращение log2 Ig N.

Наименьщее целое число, большее IgTV, равно количеству бит, необходимых для представления N в двоичном формате; точно так же наименьшее целое, большее logioTV, - это количество цифр, необходимое для представления Мъ десятичном формате. Оператор С++

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

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

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

В нем утверждается, что 2 < N < 2 , когда я - это наименьшее целое, большее IgW.

Иногда мы итерируем логарифм: мы делаем это для больших чисел. Например, ig Ig 2 = Ig 256 = 8. Как иллюстрирует данный пример, обычно мы можем считать выражение log log TV константой для практических целей, поскольку оно мало даже для очень больших N.

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

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

х] : наибольшее целое, меньшее или равное х х \: наименьщее целое, большее или равное х.

Например, LnJ и [е] оба равны 3, а rig(A+l)l - это количество бит, необходимое для двоичного представления числа TV. Другое важное применение этих функций возникает в том случае, когда необходимо поделить набор из TV объектов надвое. Этого

нельзя сделать точно, если является нечетным, поэтому для точности мы можем создать один поднабор, содержащий lN/2J объектов, а второй, - I N/2 I объектов. Если N четно, тогда размеры обоих поднаборов равны (IN/2J = [N/2 ); если же N нечетно, тогда их размер отличается на единицу (LA72J + 1 = Глу21). В С++ можно напрямую подсчитать значения этих функций при выполнении операций над целыми числами (например, если N>0, тогда N/2 равно In/2J, а N - (N/2) равно ГЛ721), а при операциях над числами с плавающей точкой можно воспользоваться функциями floor и ceil из заголовочного файла math.h.

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

I I г

РИСУНОК 2.2 ГАРМОНИЧЕСКИЕ ЧИСЛА

Гармонические числа представляют собой приближенные значения элементов площади nodi кривой 1/х. Постоянная у показывает разницу между и n

,11 1

= ! + - + - + ... +

2 Ъ N

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

Я; = 1пЛ + у+ 1 /(12Л)

где у = 0.57721... (эта константа называется постоянной Эйлера), дает отличное приближение для Hn- В отличие от flgA и LlgAJ, для вычисления Hfj лучше воспользоваться библиотечной функцией log, а не подсчитывать его непосредственно из определения.

Таблица 2.3 Специальные функции и поаоянные

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