На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> Как оцениваются комбинированные алгоритмы сортировки?
    Всем прива!

    Собственно - сабж. Давайте на примере Timsort. Вот цитата из вики:

    Цитата
    Сортировка Timsort (англ. Timsort) — комбинированный алгоритм (используется сортировка вставками и сортировка слиянием). Сложность алгоритма: O(n*log(n)). Требуется O(n) дополнительной памяти. Разработан для использования в языке Python[14].

    Собственно, вопрос: сабж!

    В данном случае имеем два алгоритма, которые "сочетаем":

    1) Сортировка вставками - вычислительная сложность O(n²)
    2) Сортировка слиянием - вычислительная сложность O(n*log(n))

    Откуда - результирующий O(n*log(n))?
      Сортировка вставками используется на малых фрагментах, скажем, порядка 100 элементов. Для каждого из таких фрагментов она выполнится быстрее, чем более сложные сортировки, т.к. у неё меньше накладные расходы (множитель для выражения со сложностью, который обычно опускают).

      Таким образом общее время немного уменьшается, сложность O(n*log(n)) сохраняется, потому что на вставки тратится в данном случае n/100 * 100^2 = 100*n - т.е. линейное время от общего количества элементов.
        Вообще-то алгоритм сортировки в Python ещё немного более сложен.

        Для начала ищутся строго убывающие последовательности. Эти последовательности сортируются просто обратной перестановкой.
        Потом производится разбивка на возрастающие серии, составляется оптимальный порядок объединения. Первыми при этом объединяются короткие пары.
        Объединение производится методом слияния (слияние может производиться как слева направо, так и справа налево, в зависимости от того какая из сливаемых последовательность короче).
        В некоторых случаях быстрее произвести слияние методом вставок (когда одна из последовательностей имеет длину один или два элемента).

        Это для обычной, возрастающей сортировки.

        Добавлено
        Производится это параллельно по мере обнаружения описанных подцепочек
          Для начала надо с трактовкой определиться.
          Либо это выбор одного из существующих алгоритмов, в зависимости от размера данных, как говорил MBo
          Либо это что-то объединенное, "закрученное", как пишет amk.
          Ну, а так, можно построить график зависимости от тестов. Визуально определить чем его описать. :lol:
          0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
          0 пользователей:


          Рейтинг@Mail.ru
          [ Script execution time: 0,0335 ]   [ 16 queries used ]   [ Generated: 28.03.24, 09:07 GMT ]