Определение.
Медианой множества А = {a1 ,…, aN } называется элемент с индексом (N+1)/2 в отсортированном по возрастанию множестве А.
Определение. k-той порядковой статистикой множества из N вещественных чисел A={A1,…, AN} называется k-тое число в упорядоченном множестве A. Легко увидеть, что [(N+1)/2]-ая порядковая статистика является медианой множества. В свою очередь, если бы мы могли эффективно искать медиану множества, то это дало бы хорошую модификацию алгоритма QuickSort.
Из предыдущей
главы следует, что верхней оценкой
времени поиска k-той порядковой статистикой является O(N log2 N). Оказывается, что
эту оценку можно улучшить.
Для поиска
порядковых статистик можно, практически один в один, применять алгоритм QuickSort с
единственной модификацией: после каждого деления массива на две части мы можем
точно сказать, в какой из них лежит искомая k-тая порядковая
статистика, поэтому другую половину можно далее не рассматривать.
QFindStatP (A,p,q,k)
Если
q-p < 1 то return Ap
Вечный
цикл
i=p; j=q;
Поменять местами Ap и случайно
выбранный элемент Al
, где p £ l £ q
x=Ai
Пока
A i < x : i + +;
Пока A j > x : j - -;
Если i < j то
поменять местами A i и A j ;
иначе
{Если k £ j
то return QFindStatP
(A, p, j, k)
иначе return QFindStatP (A, j+1, q,
k)
}
i + +; j - -;
Конец
вечного цикла
Теорема. Время работы алгоритма QFindStatP равно O(N 2), где N – количество элементов в обрабатываемом массиве.
Доказательство.
После каждого разбиения массива на две части длина самой большой из двух
образовавшихся половин оказывается меньше либо равной длине разбиваемого
массива –1. Поэтому на каждой ветви алгоритма будет не более N узлов (разбиений
массива). На каждом уровне дерева разбиений присутствуют не более N элементов, по
которым производится поиск, поэтому суммарное время работы на одном уровне
дерева равно O( N ). Итого, суммарное
время работы алгоритма равно O( N ) * N = O( N 2).
Данная оценка достижима на массиве {1, …, N-1,N} при поиске, например, N-ой порядковой статистики и при том, что в качестве псевдомедианы каждый раз будет выбираться первый элемент в подмассиве.
Теорема.
Среднее время работы алгоритма QFindStatP равно Q(N), где N –
количество элементов в обрабатываемом массиве. Под средним временем
подразумевается среднее время по всем перестановкам любого массива, состоящего
из различных элементов входных данных длины N.
Доказательство. Выпишем рекуррентное соотношение на среднее время работы алгоритма
T(N) £ [ T( N-1 ) + Si=2i£N MAX(T( i-1 ), T( N-i+1 )) ]/N +
O(N) =
=
[ T( N -1) + Si=1i<N MAX(T( i ), T( N-i )) ]/N + O(N) £
£
[ T( N -1) + 2Si=N/2i<N T( i ) ]/N + O(N) £
£
[ 2 Si= N/2i<N T( i ) ]/N + O(N)
Предположим, для i<N верно:
T( i )<a i + c для некоторых a>0, c>0 ,
тогда задача сводится к нахождению таких a>0, c>0 , что для них всегда бы выполнялось соотношение
[ 2 Si= N/2i<N T( i ) ]/N + O(N) < a N + c
Итак
T(N) £
[ 2 Si= N/2i<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).
¢
Очень часто
встречаются задачи, когда требуется искать порядковую статистику большого
множества целых чисел, значения которых ограничены некоторой небольшой
константой. Классическим примером таких задач является поиск порядковой
статистики для некоторого подмножества пикселов серого изображения (=значения
пикселов от 0 до 255). Данная задача может быть решена по аналогии с алгоритмом
сортировки подсчетом.
Итак, пусть есть
массив целых чисел {Ai} (i=0,…,N-1), 0£ Ai<M. Требуется
вычислить порядковую статистику с номером q. Для работы алгоритма требуется дополнительный
массив целых чисел B длины M. Алгоритм
аналогичен сортировке подсчетом:
QFindStatD (A,N, q, B,M)
Для
всех i от 0 до M-1 с шагом 1 выполнить: B[i]=0
Для всех i от 0 до N-1 с шагом 1 выполнить: B[A[i]] ++
Для всех i от 0 до M-1 с шагом 1 выполнить: ЕСЛИ q<B[i] то ВЕРНУТЬ i ИНАЧЕ q-=B[i]
Теорема. O(N+M) является верхней оценкой времени работы алгоритма QFindStatD для случая 0£ Ai<M, где N – количество элементов в обрабатываемом массиве. Для случая M=O(N) верхней оценкой времени работы алгоритма является O(N).
Обычно под серым
изображением имеется в виду массив целых чисел Ai,j размером Nx×Ny со значениями 0£ Ai£255. Требуется для всех
I,J найти порядковую
статистику с номером q для множества пикселов с индексами I-M £ i £ I+M, J-M £ j £ J+M.
Если
воспользоваться предыдущим алгоритмом поиска порядковой статистики, то мы
получим верхнюю оценку времени работы алгоритма = O(Nx×Ny×M2), что будет
ощутимо медленно работать в случае изображения среднего размера (1000×1000)
и средних значений M (например, M больше 100). Оказывается, данную задачу можно решить существенно более
быстро. При этом окажется, что среднее время подсчета медианы будет по порядку
меньше количества элементов последовательности, по которой считается медиана
(!).
Для решения данной
задачи модифицируем алгоритм QFindStatD следующим образом.
Будем перебирать индексы пикселов, в окрестности которых считается медиана, по
строкам.
Для I=0 медиана будет считаться с помощью алгоритма QFindStatD.
Далее в цикле по I при расчете
медианы для окрестности пиксела I,J отметим, что в рассматриваемое множество
пикселов будут добавляться точки с i=I+M (кроме M последних
столбцов) и удаляться точки с i=I-M (кроме M первых столбцов).
Тогда, если мы будем хранить в процессе вычислений массив B из алгоритма QFindStatD, то для каждого I,J его модификация потребует всего лишь O(M) операций. Здесь, конечно, следует отметить, что в оценку времени работы алгоритма войдет количество градаций яркости изображения (у нас = 256), но для больших M (у нас больше 100) это замечание несущественно.
Таким образом, мы получили алгоритм решения данной задачи с верхней оценку времени работы = O(Nx×Ny×M), т.е. среднее время вычисления порядковой статистики в данном случае для каждой области равно квадратному корню от количества точек в рассматриваемой области.
Зададимся
целью написать алгоритм нахождения k-ой порядковой статистики, требующий Q(N) операций в худшем
случае. Это было бы возможным, если бы в алгоритме QFindStatP на каждом этапе разбиения множества на две
части мы бы получали части размером не менее sL, где L – длина
разбиваемой части множества, s<1. Для этой цели мы построим алгоритм QFindStat5, который перед
разбиением множества на две части разбивает его на пятерки последовательных
элементов, в каждой пятерке ищет медиану и на полученном множестве медиан
пятерок чисел запускает самого себя для поиска медианы полученного множества.
Полученную медиану медиан x алгоритм использует для разбиения множества на
две части, состоящих, соответственно, из элементов
меньше или равных x, и из элементов
больше или равных x. Далее, в
зависимости от k, следует применить
QFindStat5
к
одной из полученных половин множества.
Итак, для поиска k-ой статистики
массива A, состоящего из N элементов, следующий алгоритм надо вызывать в виде QFindStat5(A,1,N,k)
QFindStat5(A,I,M,k)
Если
M -I+1 £
5 то найти k-ую статистику с номером x любым методом; return x
Разбить
массив A[I… M] на пятерки элементов и
отсортировать
элементы внутри пятерок
x= QFindStat5 (A’,1,[(( M -I+1)+4)/5], ([((M -I+1)+4)/5]+1)/2), где A’ – массив медиан
пятерок
Выполнить
один шаг QuickSortP
для псевдомедианы x
=> массив разбит на куски [I,L] и [L+1, M]
Если k £ L то return QFindStat5 (A,I,L,k)
иначе return QFindStat5 (A,L+1, M,k)
Теорема.
Время работы алгоритма QFindStat5 равно Q(N), где N – количество
элементов в обрабатываемом массиве (N=M-I+1).
Доказательство. В массиве медиан пятерок [(N+4)/5] элементов. Нахождение медианы x этого множества гарантирует, что в каждой пятерке справа от x , включая пятерку с x (см. рисунок ниже), и кроме последней пятерки, 3 элемента больше или равны x (на рисунке эти элементы выделены серой областью). Количество всех указанных пятерок не менее [([(N+4)/5]+1)/2], последняя пятерка может быть не полной и в ней, в худшем случае, может быть всего один элемент больше или равный x. Если теперь исключить из описанного множества x, то получается, что мы имеем 3[([(N+4)/5]+1)/2] - 3 элементов больше или равных x. Легко показать, что такое же количество элементов меньше или равны x. Т.о. после выполнения одного шага QuickSortP останется не более N - 3[([(N+4)/5]+1)/2] + 3 £ N – 3N/10 + 3 = 7N/10 + 3 элементов.
Оценим время выполнения алгоритма QFindStat5 : T(N). Оно складывается из времени поиска медианы медиан пятерок элементов (T([(N+4)/5])), времени поиска медианы в отрезанном куске множества длиной не более 7N/10 + 3 (T(7N/10 + 3)) и всего остального (O(N)).
T(N) £ T(N/5+1) + T(7N/10 + 3) + O(N)
Теперь, если предположить, что T(i) £ c i, для i<N, то получим
T(N) £ с(N/5+1) + с(7N/10 + 3) + O(N) £ с( 9N/10 + 4 ) + O(N) =
= сN + (O(N) – c(N/10 - 4))
Выбрав достаточно большое c получим, что для N>40
O(N) – c(N/10 - 4) £
0
Далее, выбрав еще большее c можно получить, что для N£40
T(N) £
сN
Т.о. мы получим,
что T(N) £
сN для любого N.
¢