Доказательство алгоритма сортировки и время работы

Hydrosort – это алгоритм сортировки. Ниже приведен псевдокод.

*/A is arrary to sort, i = start index, j = end index */

    Hydrosort(A, i, j):                 // Let T(n) be the time to find where n = j-1+1

      n = j – i + 1                              O(1)
      if (n < 10) {                              O(1)
        sort A[i…j] by insertion-sort            O(n^2) //insertion sort = O(n^2) worst-case
        return                                   O(1)
      }
      m1 = i + 3 * n / 4                         O(1)
      m2 = i + n / 4                             O(1)
      Hydrosort(A, i, m1)                        T(n/2)
      Hydrosort(A, m2, j)                        T(n/2)
      Hydrosort(A, i, m1)                        T(n/2)

T(n) = O(n^2) + 3T(n/2), поэтому T(n) равно O(n^2). Я использовал 3-й случай основной теоремы, чтобы решить это повторение.

У меня есть 2 вопроса:

  1. Правильно ли я рассчитал время работы в наихудшем случае?

  2. как мне доказать, что Hydrosort(A, 1, n) правильно сортирует массив A из n элементов?


performance sorting algorithm big-o master-theorem
person Daniel    schedule 24.05.2020    source источник
comment
Ваш заголовок спрашивает, правильно ли отсортированы данные. Предпоследняя строка вопроса спрашивает о наихудшем времени выполнения. В чем вопрос?   -  person AdrianHHH    schedule 24.05.2020
comment
Пожалуйста, отредактируйте свой вопрос (и его заголовок). В заголовке должно быть указано (кратко и точно), на какую деталь направлен ваш вопрос (и затем соответствовать этому вопросу!), а пример кода должен иметь правильный синтаксис программирования (включая то, как писать комментарии).   -  person HelpingHand    schedule 25.05.2020
comment
@HelpingHand спасибо за совет!   -  person Daniel    schedule 25.05.2020
comment
@AdrianHHH Я внес исправления. У меня есть 2 вопроса относительно этого псевдокода. Один касается доказательства, а другой — проверки времени выполнения :)   -  person Daniel    schedule 25.05.2020
comment
Операция sort A[i…j] by insertion-sort ограничена некоторой константой, максимальным временем сортировки массива из 10 элементов, поэтому это не O(n^2), можно просто считать за O(1).   -  person g.kov    schedule 25.05.2020
comment
Кроме того, интервалы [i, m1] и [m2, j] содержат не n/2 элементов, а 3n/4, поэтому должно быть T(3n/4) вместо T(n/2).   -  person g.kov    schedule 25.05.2020
comment
Это похоже на вариант сортировки марионеток и определенно не O(n^2)   -  person Blastfurnace    schedule 26.05.2020

Ответы (1)


arrow_upward
0
arrow_downward

Правильно ли я рассчитал время работы в наихудшем случае?

Я боюсь, не. Функция сложности:

T(n) = 3T(3n/4) + CONST

Это потому что:

  1. У вас есть три рекурсивных вызова для задачи размером 3n/4.
  2. Константный модификатор здесь — O(1), поскольку все операции нерекурсивных вызовов ограничены постоянным размером (в частности, сортировка вставками для n‹=10 — O(1)).

Если вы продолжаете и вычисляете это, вы получите хуже, чем O(n^2) сложность

как мне доказать, что Hydrosort(A, 1, n) правильно сортирует массив A из n элементов?

По индукции. Предположим, ваш алгоритм работает для задач размера n, и давайте рассмотрим задачу размера n+1. Для n+1<10 это тривиально, поэтому мы игнорируем этот случай.

  • После первого рекурсивного вызова вам гарантируется, что первые 3/4 массива отсортированы, и, в частности, вам гарантируется, что первые n/4 элементов являются наименьшими в этой части. Это означает, что они не могут быть в последних n/4 массива, потому что есть по крайней мере n/2 элементов больше их. Это означает, что n/4 самых больших элементов находятся где-то между m2 и j.
  • После второго рекурсивного вызова, поскольку он гарантированно будет вызываться для n/4 самых больших элементов, он поместит эти элементы в конец массива. Это означает, что часть между m1 и j теперь отсортирована правильно. Это также означает, что 3n/4 наименьших элементов находятся где-то между i и m1.
  • Третий рекурсивный вызов правильно сортирует 3n/4 элемента, а n/4 самых больших элементов уже на месте, так что теперь массив отсортирован.
person amit    schedule 25.05.2020