Анализ алгоритмов типа «разделяй и властвуй»

Как оценить время работы рекурсивного алгоритма? При подсчёте мы должны учесть время, затрачиваемое на рекурсивные вызовы, так что получа­ется некоторое рекуррентное соотношение (recurrence equation). Далее следует оценить время работы, исходя из этого соотношения.

Вот примерно как это делается. Предположим, что алгоритм разбивает за­дачу размера n на a подзадач, каждая из которых имеет в b раз меньший размер. Будем считать, что разбиение требует времени D(n), а соединение полученных решений — времени C(n). Тогда получаем соотношение для времени работы T(n) на задачах размера n (в худшем случае): T(n)=aT(n/b)+D(n)+C(n). Это соотношение выполнено для достаточно больших n, когда задачу имеет смысл разбивать на подзадачи. Для малых п, когда такое разбиение невозможно или не нужно, применяется какой-то прямой метод решения задачи. Поскольку n огра­ничено, время работы тоже не превосходит некоторой константы.

Анализ сортировки слиянием

Для простоты будем предполагать, что размер массива есть степень двойки. Тогда на каждом шаге сортируемый участок делится на две равные половины. Разбиение на части (вычисление границы) требует времени 0(1), а слияние — времени 0(n). Получаем соотношение

O(1), если n=1,

T(n)=

2T(n/2)+O(n), если n>1.

Докажем, что Т(n) = O(nlog n), где через log мы обозначаем двоичный логарифм (основание логарифмов, впрочем, не играет роли, так как приводит лишь к изменению константы). Поэтому для больших n сортировка слиянием эффективнее сортировки вставками, требующей времени 0(n²).

Найдем верхнюю оценку для функции T(n)=2T(n/2)+n. Можно предположить, что T(n)= O(nlog n), т.е., что T(n)≤cnlogn для подходящего с>0. Докажем по индукции. Пусть эта оценка верна для [п/2˩, т.е. T([п/2˩)≤c[п/2˩log([п/2˩). Подставив ее в соотношение, получим

T(n)≤2(c[п/2˩log([п/2˩))+n≤cnlog(n/2)+n=cnlog(n)-cnlog(2)+n=cnlog(n)-cn+n≤cnlog(n).

Последний переход законен при c≥1.

Остается проверить базис индукции, т.е. доказать оценку для начального значения n. Поскольку [п/2˩≥2 при n>3, подберем c так, чтобы оценка T(n)≤cnlog(n) быда верна при n=2 и n=3.

Для проверки времени исполнения функций сортировки можно использовать функцию clock() c библиотеки #include <time.h>:

clock_t t0,tk;

t0=clock();

Merge_Sort(A,1,n);

t1=clock();

cout<<”t=”<<(t1-t0)/CLOCKS_PER_SEC<<endl;

7