Студопедия

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

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

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






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






    Среднее время работы алгоритма зависит от длин промежутков — 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 :: Мои Лекции
    Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
    Копирование текстов разрешено только с указанием индексируемой ссылки на источник.