Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Выбор длины промежутков






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

● первоначально используемая Шеллом последовательность длин промежутков: в худшем случае, сложность алгоритма составит cN 2;

● предложенная Хиббардом последовательность: все значения ; такая последовательность шагов приводит к алгоритму сложностью O (N 3 / 2);

● предложенная Седжвиком последовательность: , если i четное и , если i нечетное. При использовании таких приращений средняя сложность алгоритма составляет: O (n 7 / 6), а в худшем случае порядка O (n 4 / 3). При использовании формулы Седжвика следует остановиться на значении inc[s-1], если 3*inc[s] > size.[1];

● предложенная Праттом последовательность: все значения ; в таком случае сложность алгоритма составляет O (N (logN)2);

● эмпирическая последовательность Марцина Циура (последовательность A102549 в OEIS): ; является одной из лучших для сортировки массива ёмкостью приблизительно до 4000 элементов.[2];

● эмпирическая последовательность, основанная на числах Фибоначчи: ;

● все значения [ источник не указан 770 дней ], ; такая последовательность шагов приводит к алгоритму сложностью O (N 3 / 2).

 

 






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.