вторник, 20 сентября 2011 г.

K-ая порядковая статистика за O(N) в среднем случае

Потратил значительное время на поиск красивой реализации данного алгоритма. Как и следовало ожидать она лежала прямо под носом

  1. int partition(vector<int> &mas, int l, int r) {
  2.   if (l!=r)
  3.     swap(mas[l + rand() % (r - l)], mas[r]);
  4.   int x = mas[r];
  5.   int i = l-1;
  6.   for (int j = l; j <= r; j++) {
  7.     if (mas[j] <= x)
  8.       swap(mas[++i],mas[j]);
  9.   }
  10.   return i;
  11. }
  12. int nth(vector<int> mas, int n) {
  13.   int l = 0, r = mas.size() - 1;
  14.   for(;;) {
  15.     int pos = partition(mas,l,r);
  16.     if (pos < n)
  17.       l = pos + 1;
  18.     else if (pos > n)
  19.       r = pos - 1;
  20.     else return mas[n];
  21.   }
  22. }
* This source code was highlighted with Source Code Highlighter.

Немного проанализируем представленный код.
Функция nth принимает на вход массив и номер порядковой статистики, которую нужно найти. После выполнения функция возвращает значение порядковой статистики.
Но куда большее значение имеет функция partition. Суть ее заключается в том, что она выбирает произвольный элемент массива mas, индекс которого находится в интервале [l,r] и ставит его на “свое место”, т.е. на то место, на котором находился элемент, если бы массив был упорядочен.
В строке 3 как раз и происходит выбор этого произвольного элемента. После чего выбранный элемент меняется местами с последним элементом рассматриваемого интервала.
Если в качестве произвольного элемента брать всегда последний элемент или какой-нибудь фиксированный, то при желании можно легко подобрать тест, на котором представленная реализация будет иметь квадратичную сложность. Кстати если исходный массив будет упорядочен и в реализации функции partition будут отсутствовать 2 и 3 строки, то в каждой итерации функции nth на “свое место” будет становится только последний элемент и это будет повторяться SIZE раз, где SIZE – размерность массива.
На произвольном массиве данная реализация работает в среднем за O(N). Реализацию данного алгоритма при которой он будет работать за O(N) на любом массиве мы рассмотрим позже.

Обратите внимание, что в приведенной реализации массив передается по значению. Это следует делать, если мы незаинтересованы в частичном упорядочивании массива. В противном случае массив следует передавать по ссылке.

P.S: Если исходный массив будет состоять из одинаковых элементов, то приведенный алгоритм будет работать за O(N*N).

3 комментария: