73
правки
Изменения
м
→Анализ метода Шелла
{{Теорема
|id=teotema1
|aboutauthor=1Д.Х. Ханту
|statement=
Среднее число инверсий в <tex>h</tex> упорядоченной перестановке множества <tex>\{</tex> ''1, 2, ..., <tex>n \}</tex> равно
{{Лемма
|id=sledstvie1
|about=1
|statement=
Данная лемма является следствием теоремы выше.
Таким образом, применяя метод Шелла и используя всего 2 прохода, можно сократить время по сравнению с методом простых вставок с <tex>O(N^2)</tex> до <tex>O(N^{1.(6)})</tex>.
Используя приведенные выше формулы порог <tex>N^{1.5}</tex> преодолеть не возможноневозможно, но если убрать ограничение <tex> h_{s+1}\,\bmod\,h_s = 0</tex> его можно преодолеть.
{{Теорема
|id=teotema2
|aboutauthor=А.А. Папернов, Г.В. Стасевич
|statement=
Если <tex>h_s=2^{s+1}-1</tex> при <tex>0 \leqslant s < t = \left \lfloor ln N \right \rfloor</tex>, то время сортировки есть <tex>O(N^{3/2})</tex>.
