Изменения

Перейти к: навигация, поиск

Обсуждение:PSRS-сортировка

40 байт добавлено, 17:09, 3 июня 2014
Вставка в список
===Вставка в список ===
При этой сортировке мы используем односвязной список вместо упорядоченной части массива. Теперь на не потребуется времени на сдвиг, а понадобиться всего лишь изменить родстве6ые родственные связи. Что касается константы <tex>C</tex>, то При этом время выполнения сокращается в четыре раза : <tex>C \cdot N \cdot (N/4+2) \approx N^2/4</tex>, следовательно <tex>C=1/4</tex>. 
=== Сортировка с вычислением адреса ===
Сортировку с вычисление адревса выгодно использовать когда ключи распределены равномерно и не скапливаются хаотично в отдельных диапазонах значений. Вместо левой отсортированной части массива мы будем использовать <tex> M </tex> односвязных списков, в каждом из которых будут храниться значения из определённого диапазона. С каждым списком работаем как при простых выставках в список. Вероятность того что элемент попадёт в какой-либо список <tex>1/M</tex>, следовательно для каждого элемента происходит примерно <tex> \frac {N} {4 \cdot M} </tex> сравнений, следовательно общее количество сравнений <tex> \frac {N^2} {4 \cdot M} </tex>, а при <tex>M</tex> порядка <tex>N</tex> асимптотическая сложность уменьшается до <tex>O(N)</tex>. Рассмотрим на примере.
77
правок

Навигация