proof - master - R80/seek

proof
67 строк3 KB
Денис Вергун
proof
09 апр 2025, 09:31
09 апр 2025, 09:31a2f1f53
понятия:

перестановккой конечного множества называется некоторое расположение его элементов в ряд.

инверсии:  a1, a2, a3...an перестановка
если ai>aj а i<j то пара (ai,aj) называется инверсией
например перестановка 3142 имеет три инверсии (3,1), (3,2), (4,2)

h-упорядоченная перестановка это перестановка упорядоченная с шагом h (сортировка Шелла)

ls - длинна hs-упорядоченной последовательности или шаг сортировки.

сочетание из n по k называется набор из k элементов, выбранных из данного множества, содержащего n элементов.

Время работы программы:

ПОДСЧЕТОМ:
(N^2-N)/2 где
N-число записей
(N^2-N) число способов(сочетаний) выбрать 2 из N.
n(n-1)...(n-k+1)=n(n-1)= n^2-n.
/2 убираем повторяощиеся сравнения.

ШЕЛЛА:
алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками.
n^1,5 среднее время где
n число записей

Кнут с. 103 Теорема (А.А. Папернов, Г.В. Стасевич):
Если hs=2^(s+1)−1(колл. пар групп) при 0⩽s<t=⌊log(2)N⌋(логарифм N по основанию 2), то время сортировки есть O(N^3/2).

Достаточно найти оценку числа перезаписей Bs на s проходе, такую, что бы Bt−1+…+B0=O(N^3/2).
Bs=O(hs(N/2^(s+1))),или рекурентное соотношение Bs=B   -ls. S0=N/2.
                                                    s-1
Возьмем последовательность упарядоченную на k этапе, где i- номер группы, j- номер элемента в группе:

 k    k         k
ai,1;ai+h,1;...ai+h,j;
Колл. пар из a-элементов, умноженное на  шаг прохода есть максимальное колл. инверсий Bs перестановки см выше формулу, следовательно Bt−1+…+B0=O(N^3/2).

см также:
https://www.youtube.com/watch?v=lvts84Qfo8o
Кнут 96 таблица N=16 h=8,4,2,1

например:
для N=32

h0=2^(0+1)-1=1
h1=2^(1+1)-1=3
h2=2^(2+1)-1=7
h3=2^(3+1)-1=15
h4=2^(4+1)-1=31

B0=1(32/(2^(0+1)))=16 циклов
B1=3(32/(2^(1+1)))=24 цикла
B2=7(32/(2^(2+1)))=28 циклов
B3=15(32/(2^(3+1)))=30 циклов
B4=31(32/(2^(4+1)))=31 цикл

B0+B1+B2+B3+B4=129 циклов, даже меньше чем N^(1.5)=181
N^2=1024 цикла

вывод:
16^2(O(N^2) подсчетом)=256 циклов, говорят о квадпатичной зависимости скорости работы от входных даных. парабола очень быстро растет(см график функции).
16^1.5 O(N^1.5) шелла =64 циклов сдесь зависимость между пораболой и линейной.  x^1.5 более пологий и на больших N намного быстрее
		   
		lim U=lim lim(N^2)/lim(N^1.5) = inf