Алгоритмы сортировки данных известного статистического распределения?

звучит, как вы, возможно, захотите, чтобы прочитать Самосовершенствующиеся Алгоритмы: они достигают возможного оптимального ожидаемого времени произвольные распределений входных данных.

мы даем такие самосовершенствующиеся алгоритмы для двух задач: (i) сортировка a последовательность чисел и (ii) вычисление триангуляция Делоне плоского объекта множество точек. Оба алгоритма достигают оптимальная ожидаемая предельная сложность. Алгоритмы начинаются с обучения фаза, во время которой они собирают информация о входе распределение, за которым следует стационарное режим, в котором алгоритмы оседают к их оптимизированным воплощениям.

Если вы уже знаете, что ваше входное распределение примерно гауссово, то, возможно, другой подход был бы более эффективным с точки зрения сложности пространства, но с точки зрения ожидаемого времени выполнения это довольно замечательный результат.

зная исходные данные, можно построить хорошую хэш-функцию. Хорошо зная распределение, хэш-функция может оказаться идеальной хэш-функцией или близкой к идеальной для многих входных векторов.

такая функция разделит вход размером n на n ячеек, так что самый маленький элемент будет отображаться в 1-й ячейке, а самый большой элемент будет отображаться в последнюю ячейку. Когда хэш идеален - мы бы достигли сортировки, просто вставляя все элементы в бункеры.

вставка всех элементов в хэш-таблицу, а затем их извлечение по порядку будет O (n), когда хэш-функция совершенна(предполагая, что стоимость вычисления хэш-функции равна O(1), а операции подчеркивания хэш-структуры данных-O (1)).

Я бы использовал массив куч Фибоначчи для реализации хэш-таблицы.

для входного вектора, для которого хэш-функция не будет идеальной (но все же близкой к идеальной), она все равно будет намного лучше, чем O(nlogn). Когда это идеально-это было бы O(n). Я не уверен, как рассчитать среднюю сложность, но если бы пришлось, я бы поставил на O(nloglogn).

алгоритмы сортировки можно разделить на две категории, сортировка на основе сравнения и не-сравнения на основе сортировки. Для сравнения-на основе сортировки время сортировки в лучшем случае производительность Ω (nlogn), а в худшем случае время сортировки может увеличиться до O(n2 ). За последние годы, были предложены некоторые улучшенные алгоритмы ускорьте сортировку на основе сравнения, например advanced быстрая сортировка по характеристикам распределения данных . Тем не менее, средняя время сортировки для этих алгоритмы-это просто Ω (nlog2n), и только в лучшем случае может ли он достичь O (n). Отличается от сортировки на основе сравнения, сортировка без сравнения, например сортировка по количеству, сортировка ковша и сортировка корня зависит главным образом от ключа и расчет адреса. Когда значения ключей конечная в диапазоне от 1 до m, вычислительная сложность сортировки без сравнения заключается в следующем O (m+n). В частности, когда m=O (n), время сортировки может достигать O (n). Однако, когда m=n2, n3,...., этот верхний границы линейного времени сортировки не может быть получена. Среди не-сравнения на основе сортировки, ведро сортировки распределяет группу записей с аналогичными ключами по соответствующий "ведро", то другой алгоритм сортировки применяется к записям в каждом ведре. С ведрами сортировка, разбиение записей на m ведер меньше отнимает много времени, в то время как только несколько записей будет содержится в каждом ведре так, что " очистка сортировки" алгоритм может быть применен очень быстро. Следовательно, сортировать ведра имеет потенциал для асимптотического сохранения время сортировки по сравнению с алгоритмами Ω (nlogn). Очевидно, как равномерно распределить все записи в ведра играют важную роль в сортировке ведер. Следовательно, вам нужен метод для построения хэш-функции согласно распределению данных, которое использовано к равномерно распределите n записей в n сегментов на основе ключ каждой записи. Следовательно, время сортировки предложенный алгоритм сортировки ковша достигнет O(n) под любым обстоятельство.

проверьте эту бумагу:http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5170434&tag=1

сортировка ведра даст вам алгоритм линейной сортировки по времени, если вы можете вычислить CDF каждой точки в O (1) времени.

алгоритм, который вы также можете посмотреть в другом месте, выглядит следующим образом:

a = array(0, n - 1, [])          // create an empty list for each bucket
for x in input:
  a[floor(n * cdf(x))].append(x) // O(1) time for each x
input.clear()
for i in {0,...,n - 1}:
  // this sorting step costs O(|a[i]|^2) time for each bucket
  // but most buckets are small and the cost is O(1) per bucket in expectation
  insertion_sort(a[i])
  input.concatenate(a[i])

время выполнения равно O(n) в ожидании, потому что в ожидании есть O(n) пар (x, y) такие, что x и y попадают в один и тот же ковш, а время выполнения сортировки вставки точно равно O(N + # пар в том же ковше). Анализ похож на этот из FKS статическое идеальное хэширование.

EDIT: если вы не знаете распределение, но вы знаете, из какого семейства оно, вы можете просто оценить распределение в O(n), в Гауссовом случае, вычисляя среднее и дисперсию, а затем использовать тот же алгоритм (кстати, вычисление cdf в этом случае нетривиально).

вы можете использовать эту информацию в quicksort, чтобы выбрать значение pivot. Я думаю, что это улучшит вероятность того, что алгоритм будет держаться подальше от сложности наихудшего случая O(N**2).

Я думаю сортировка цикла попадает в эту категорию. Вы используете его, когда знаете точное положение, в котором вы хотите, чтобы каждый элемент оказался.

Cyclesort имеет некоторые хорошие свойства - для некоторых ограниченных типов данных он может выполнять стабильную сортировку на месте в линейном времени, гарантируя, что каждый элемент будет перемещен не более одного раза.