Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Оценки времени работы алгоритма.

Читайте также:
  1. A) средний прирост за единицу времени
  2. A) число погибших особей, появившихся за единицу времени
  3. D8.22 Формула оценки топливной эффективности
  4. Fidelio Front Office - система автоматизации работы службы приема и размещения гостей.
  5. Figure 6. Ежедневная оценка числа сотрудников в зависимости от времени обработки запросов и количества инцидентов
  6. FILTER – задает один из трех режимов работы ручкам FREQ и RESON
  7. Galileo project: карьерные траектории и миграции ученых Раннего Нового Времени.

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

Теорема. Время работы алгоритма QuickSort равно O(N 2), где N – количество элементов в сортируемом массиве.

Доказательство. После каждого разбиения массива на две части длина самой большой из двух образовавшихся половин оказывается меньше либо равной длине разбиваемого массива –1. Поэтому на каждой ветви алгоритма будет не более N узлов (разбиений массива). На каждом уровне дерева разбиений присутствуют не более N сортируемых элементов, поэтому время, затрачиваемое на слияние их подмножеств равно O(N). Итого, суммарное время работы алгоритма равно O(N) * N = O(N 2).

Данная оценка достижима на массиве {N,N-1,…,1}.

¢

 

Оказывается, что число ``неприятных’’ случаев, т.е. таких расположений массивов чисел, при которых время работы алгоритма QuickSort велико, оказывается, относительно, небольшим. Вообще, верна теорема

 

Теорема. Среднее время работы алгоритма QuickSort равно Q(N log2 N), где N – количество элементов в сортируемом массиве. Под средним временем подразумевается среднее время по всем перестановкам любого массива входных данных длины N, состоящего из различных элементов.

 

Данная теорема объясняет, в каком смысле данный алгоритм является оптимальным. В то же время, в реальной жизни, часто поток входных данных не является случайным, поэтому в качестве медианы следует брать случайно выбранный элемент. Для этого внесем в алгоритм QuickSort следующее дополнение. Перед присваиванием x=Ai поменяем местами i -ый элемент массива со случайно выбранным элементом среди элементов с индексами от p до q. Назовем получившийся алгоритм QuickSortP. Приведенная теорема верна также и для алгоритма QuickSortP. Докажем ее именно для последнего алгоритма. Будем, кроме того, предполагать, что все элементы входной последовательности различны, или, что то же самое, на входе подается последовательность различных элементов из множества {1,…,N}.

В рассматриваемом случае если x=1, то перед входом в рекурсию алгоритма QuickSort множество разобьется на части размером 1 и N-1. В любом другом случае, как отмечалось выше в доказательстве Замечания 3, элемент x останется в правой половине массива и размер левой половины массива, поэтому, будет равен x-1.

Выпишем рекуррентное соотношение на среднее время работы алгоритма

T(N) = [ (T(1) +T(N-1)) + Si=2i£N (T(i-1) +T(N-i+1))]/N + Q(N) =

= [ (T(1) +T(N-1)) + Si=1i<N (T(i) +T(N-i))]/N + Q(N) =

= [ (T(1) +T(N-1) ]/N + [ Si=1i<N (T(i) +T(N-i))]/N + Q(N) =

= [ Si=1i<N (T(i) +T(N-i))]/N + Q(N)

Предположим, для i<N верно:

T(i)<a i log i +c для некоторых a>0, c>0,

тогда задача сводится к нахождению таких a>0, c>0, что для них всегда бы выполнялось соотношение

 

[ Si=1i<N (T(i) +T(N-i))]/N + Q(N) < a N log N +c

Итак

[ Si=1i<N (T(i) +T(N-i))]/N < [ Si=1i<N (a i log i +c + a (N-i) log (N-i) +c))]/N =

= [ Si=1i<N (a i log i +c))]2/N < a [ Si=1i<N i log i ]2/N +2 c

 

Оценим сумму из соотношения:

 

Si=1i<N i log i = Si=1i<N i log N + Si=1i<N i log (i/N) = N 2 log N / 2 - Si=1i<N i log (N/i) £ N 2 log N / 2 - Si=1i<N/4 i log (N/i) £ N 2 log N / 2 - Si=1i<N/4 i 2 £ N 2 log N / 2 - N 2/ 8

Т.о. имеем

 

[ Si=1i<N (T(i) +T(N-i))]/N + Q(N) < a (N log N - N / 4) + 2 c + Q(N) =

= a N log N + c + (Q(N) + c – a N / 4)

Осталось взять такое большое a, что (Q(N) + c – a N / 4)<0, после чего мы получаем требуемое соотношение.

¢

 


К сожалению, обе приведенные реализации алгоритма QuickSort не являются жизнеспособными. Это связано с тем, что в обоих алгоритмах максимально возможная глубина рекурсии равна N. В этом случае требуется порядка O(N) байт дополнительной памяти, что не фатально, но проблема в том, что эта память будет выделяться в стеке задачи, а стек задачи всегда имеет маленький (относительно) размер. Поэтому, например, в Microsoft Visual Studio мы может ожидать ситуации stack overflow при размерах целочисленного массива порядка 100000 (размер стека здесь по умолчанию равен 1M).

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

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

 
 


Дата добавления: 2015-10-30; просмотров: 180 | Нарушение авторских прав


Читайте в этой же книге: Алгоритмы и алгоритмические языки | Представление чисел в ЭВМ | Нижние и верхние оценки. | Постановка задачи | Сортировка пузырьком. | Сортировка слиянием с рекурсией. | Сортировка слиянием без рекурсии. | Сортировки и связанные с ними задачи. | SortB (A, N, M, B) | То return QFindStatP (A, p, j, k,N ) |
<== предыдущая страница | следующая страница ==>
Доказательство корректности работы алгоритма.| Некоторые задачи, сводящиеся к сортировке.

mybiblioteka.su - 2015-2024 год. (0.008 сек.)