Порядковые статистики.

Алгоритмы   27 марта 2012  Автор статьи:  

k-ой порядковой статистикой массива называется значение, которое будет стоять на k-ом месте после сортировки.

Тривиальный алгоритм, основанный на сортировке и выводе k-го элемента работает за O(nlog(n)). Однако существует метод, использующий модифицированный qsort, чтобы найти k-ую порядковую статистку в среднем за O(n).
Алгоритм нахождения k-го элемента состоит в выборе опорного элемента х и разделении массива на три части аналогично функции qsort. Далее, в зависимости от того, в каком из блоков находится k-ый элемент, нужно продолжать поиск именно на этом блоке, игнорируя остальные. Заметим, что если k-ый попал в блок элементов, равных х, то уже можно завершить выполнение алгоритма и в качестве ответа вывести х.
В среднем, на i-ом по глубине вызове функции нахождения порядковой статистики, проверяется в среднем \frac{n}{2^i} элементов, где n — размерность исходного массива. А так как \sum_{i=0}^{\infty}\frac{n}{2^i}=2n, то количество действий в среднем в алгоритме не превосходит 2n. Следовательно, в среднем алгоритм работает за O(n).

Научиться программировать

  • на Delphi

  • на Java

  • на C++