То return QFindStatP (A, p, j, k,N )

иначе return QFindStatP (A, j+1, q, k,N)

}

i + +; j - -;

Конец вечного цикла

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

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

Данная оценка достижима на массиве {1, …, N-1,N} при поиске, например, N -ой порядковой статистики и при том, что в качестве псевдомедианы каждый раз будет выбираться первый элемент в подмассиве.

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

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

T(N) £ [ T(N-1) + S_i=2^i£N MAX(T(i-1), T(N-i+1)) ]/N + O(N) =

= [ T(N -1) + S_i=1^i<N MAX(T(i), T(N-i)) ]/N + O(N) £

£ [ T(N -1) + 2S_i=N/2^i<N T(i) ]/N + O(N) £

£ [ 2 S_{i= N/2}^i<N T(i) ]/N + O(N)

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

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

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

[ 2 S_{i= N/2}^i<N T(i) ]/N + O(N) < a N + c

Итак

T(N) £ [ 2 S_{i= N/2}^i<N T(i) ]/N + O(N) £ a 3/4 * N + c + O(N)

Осталось взять такое большое a, что a 3/4 * N + O(N) < a N, после чего мы получаем T(N) = O(N). Осталось заметить, что первое же разбиение массива на две части (а в лучшем случае оно же будет и последним) требует времени Q(N), из чего мы получаем, что T(N) =Q(N).

¢

Поиск порядковой статистики за время Q(N) в худшем случае

Зададимся целью написать алгоритм нахождения k -ой порядковой статистики, требующий Q(N) операций в худшем случае. Это было бы возможным, если бы в алгоритме QFindStatP на каждом этапе разбиения множества на две части мы бы получали части размером не менее sL, где L – длина разбиваемой части множества, s<1. Для этой цели мы построим алгоритм QFindStat5, который перед разбиением множества на две части разбивает его на пятерки последовательных элементов, в каждой пятерке ищет медиану и на полученном множестве медиан пятерок чисел запускает самого себя для поиска медианы полученного множества. Полученную медиану медиан x алгоритм использует для разбиения множества на две части, состоящих, соответственно, из элементов меньше или равных x, и из элементов больше или равных x. Далее, в зависимости от k, следует применить QFindStat5 к одной из полученных половин множества.

---

Дата добавления: 2015-10-30