Наиболее часто встречающиеся асимптотические оценки

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

Таблица1.1

Типичные временные оценки сложности

Оценка	Пояснение и примеры типичных задач	Время работы при n=10	Время работы при n=100
Θ(1)	Время выполнения алгоритма не зависит от объёма входных данных	100 нс	100 нс
Θ(log n)	Логарифмическое время. Например, двоичный поиск, поиск в сбалансированном дереве и др.	332 нс	664 нс
Θ(n)	Линейное время. Например, каждый элемент массива обрабатывается постоянное число раз.	1 мкс	10 мкс
Θ(n∙log n)	Обычно характерно для программ, использующих стратегию ”разделяй и властвуй”, например, алгоритмы быстрой сортировки или сортировка слиянием	3,32 мкс	66,44 мкс
Θ(nk)	Полиномиальная сложность. Большое число разнообразных алгоритмов.	10 мкс (для k=2)	1 с (для k=2)
Θ(kn)	Экспоненциальная сложность. Характерна для переборных алгоритмов.	102 мкс (для k=2)	4,2·1015 лет (для k=2)
Θ(n!)	Факториальная сложность. Также может встретиться в переборных алгоритмах.	0,363 с	1,08·10146 лет

 

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

Анализ рекурсивных алгоритмов

Рекурсия и итерация

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

Рекурсия широко применяется в математике. В качестве примера дадим рекурсивное определение суммы первых n натуральных чисел. Сумма первых n натуральных чисел равна сумме первых (n – 1) натуральных чисел плюс n, а сумма первого числа равна 1. Или: S_n = S_n-1 + n; S₁ = 1.

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

int sum(int n)

{ if (n==1) sum=1; else sum=sum(n-1)+n;

}

Обратим внимание на следующие обстоятельства.

Рекурсивная функция содержит всегда, по крайней мере, одну терминальную ветвь и условие окончания (if (n==1) sum=1).

При выполнении рекурсивной ветви (else sum=sum(n-1)+n) процесс выполнения функции приостанавливается, но его переменные не удаляются из стека. Происходит новый вызов функции, переменные которой также помещаются в стек и т.д. Так образуется последовательность прерванных процессов, из которых выполняется всегда последний, а по окончании его работы продолжает выполняться предыдущий процесс. Целиком весь процесс считается выполненным, когда стек опустеет, или, другими словами, все прерванные процессы выполнятся.

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

Пример анализа рекурсивного алгоритма

В качестве более интересного примера применения рекурсии рассмотрим следующую задачу. Требуется возвести число a в степень b (a и b – натуральные). Если решать данную задачу «в лоб», то нам потребуется выполнить b умножений: a^b=a·a·a…·a (b раз). Однако,

Например, можно вычислять a^b, используя следующие соображения: - итого всего 4 операции умножения, а не 7.

Несложно написать рекурсивную функцию, выполняющую вычисления по данной формуле:

unsigned int pow(unsigned int a, unsigned int b)

{ if (b==1) return a; //терминальная ветвь

else

if (b % 2 == 0)

{ unsigned int p = pow(a,b/2);

return p*p;

}

else return pow(a,b-1)*a;

}

Оценим время выполнения данного алгоритма в худшем случае.

При выполнении функции pow число b, передаваемое при рекурсивном вызове, либо делится на 2 (если оно чётное), либо уменьшается на 1 (если оно нечётное) и тем самым становится чётным. Отсюда можно сделать вывод, что после двух последовательных рекурсивных вызовов число b уменьшится не менее чем в два раза. Рекурсия остановится, когда b станет равным 1. Таким образом, если k-общее число вызовов, то получается следующее соотношение:

,

откуда k=2log₂b. Поскольку другие операции внутри рекурсивной функции выполняются за константное время, то, пренебрегая мультипликативной константой 2 и основанием логарифма, получим точную асимптотическую оценку T(b)= Θ (logb), где b — степень (целое число), в которую возводится целое число a.

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

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

Несложно показать, что аналогичная оценка выполняется и для памяти: M(b)=Θ(logb) – при каждом рекурсивном вызове в стек помещается некоторое постоянное число байт – локальные переменные и параметры функции.

1.7. Первые примеры

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