Сложность и время работы сортировки Шелла

[lega4]

Возникла такая задача: написать сортировку Шелла, построить график времени работы от кол-ва элементов, найти ее теоретическую формулу для времени работы, и доказать, что практический результат совпал с теоретическим.

Я написал эту сортировку, используя последовательность смещений, сгенерированной по формуле Седжвика (A033622, но сейчас в английской Вики и в статейке Вайса глянул - там какая-то немного другая формула.. Но в своей программе я использовал эту, из Кнута или со странички OEIS).
Мысль раз - найти формулу в Кнуте. Нашел (стр. 107): $0,43N^\frac{7}{6}+18,5N$. Построил, домножил на некую константу, построил отношение практических результатов к теоретическим (Если формула ассимптотически верна, то отношение будет равно единице, плюс минус небольшая погрешность). Получился довольно-таки монотонно возрастающий график, что не есть хорошо. Кликабельная картинка под спойлером.

(Оффтоп)

Посоветовали построить отношение к логарифмической функции (NlogN). Построил $N*lnN$, аналогично.

(Оффтоп)

Решил поискать формулу поточнее, нашел статейку, на которую ссылается Кнут (http://comjnl.oxfordjournals.org/conten ... 8.abstract). Там формула сильно точнее $0,42663452N^\frac{7}{6}+18,49281148N-61,5728N^\frac{5}{6}+72,69723933N^\frac{2}{3}+105,37474N^\frac{1}{2}$$-372,755N^\frac{1}{3}+483,29055$. Построил. Заметно лучше предыдущих, но, все-таки, небольшое увеличение есть.

(Оффтоп)

Внимание, вопрос. Если даже формула M.A. Weiss, судя по моим графикам, капельку неточна, то какую же формулу брать в качестве теоретической?
P.S. Приведены скриншоты графиков, построенных по 25603 точкам, от нуля с шагом 150 элементов (Т.е. до 3840300 элементов включительно).

[ASP]

Формулы оценивают число "операций", а не время работы. Наверное имеет смысл вместо физического времени считать число сравнений и присваиваний. Кроме того, скорость работы может зависеть от входных данных: случайные, с повторами/без повторов, частично отсортированные, в обратном порядке итд. При выводе формулы наверняка делались какие-то предположения о характере распределения данных. Для эксперимента вместо случайных данных лучше брать случайную перестановку неповторяющихся данных, чтобы исключить зависимость от повторов. Например, алгоритм Шелла потратит меньше операций на сортировку миллиона случайных байтов, чем на сортировку миллиона 32-х битных случайных чисел, поскольку среди 8-ми битных данных будет больше повторов.

[lega4]

ASP по Шеллу с использованием этих смещений я нашел только такую формулу. Да, она вроде оценивает число обменов, но другой я просто не нашел...
И ассимптотика времени работы, как мне кажется, от входных данных не зависит (В разумных пределах - не будет такого, что каждый раз подсовывается специально сделанный массив. Входные данные псевдослучайны).

[ASP]

Цитата:

И ассимптотика времени работы, как мне кажется, от входных данных не зависит

Это зависит от алгоритма сортировки. У сортировки вставками, которая лежит в основе метода Шелла, сложность $O(N^2)$ на случайных данных и $O(N)$ на отсортированных или повторяющихся. Попробуйте ради интереса ограничить диапазон случайных чисел - например вместо 16-ти битных использовать 4-х битные, - время работы должно существенно уменьшиться.
Кстати, в сети доступна интересная статья: Ciura, "Best Increments for the Average Case of Shellsort". Там правда нет асимптотических формул, но зато приведены экспериментальные данные, с которыми можно сравнить результаты. Обратите внимание, что автор измеряет число операций, а не время работы, а в качестве входных данных берет случайные перестановки, а не случайные числа.

[lega4]

Ну мне все-таки интересно именно время работы. Неужели для данных смещений такой формулы не опубликовано?

Цитата:

Ciura, "Best Increments for the Average Case of Shellsort"

Приведенная последовательность смещений лучшая при размере массива до нескольких тысяч элементов.
А сравнивать... Это опять править программу и на полтора дня ставить сортировку... Мне это уже начинает надоедать)