Что такое космическая сложность хвостовой рекурсивной быстрой сортировки? - PullRequest
Новая
       54

Что такое космическая сложность хвостовой рекурсивной быстрой сортировки?

0 голосов
/ 16 октября 2018

Глядя на следующий хвостовой рекурсивный псевдокод быстрой сортировки 

QuickSort(A[1, ..., n], lo, hi)
Input: An array A of n distinct integers, the lower index and the higher index
         // For the first call lo = 1 and hi = n
Output: The array A in sorted order

If lo = hi return
         // The array A is already sorted in this case
If lo > hi or indices out of the range 1 to n then return

Else
      Pick an index k in [lo,hi] as the pivot
              // Assume that this can be done using O(1) cells on the stack
      i = Partition(A[lo, ..., hi], k)
              // Use in-place partitioning here so assume that this can be done
              // using O(1) space on the stack

If i - lo <= hi - i
      QuickSort(A, lo, i-1) // sort the smaller half first
      QuickSort(A, i+1, hi)
Else
      QuickSort(A, i+1, hi) // sort the smaller half first
      QuickSort(A, lo, i-1)

Предполагая, что стержень выбирается с состязанием каждый раз, когда я анализировал, что он должен иметь пространственную сложность O (logn) [в которой я не совсем уверенэто правильно], но как повлияет сложность пространства, если стержень тогда будет выбран случайным образом равномерно?Я довольно новичок в понимании сложности пространства во времени, поэтому любая обратная связь приветствуется!

Ответы [ 2 ]

0 голосов
/ 16 октября 2018

Наихудший случай для времени - если вы разделите массив как можно неравномернее, и это время будет O(n^2).Если вы не выполняете хвостовую рекурсию, это также будет наихудшим случаем для пробела.

Однако если вы разделите массив неравномерно и выполняете хвостовую рекурсию, вызов сортировки по большей половине занимаетнет места, потому что вы просто замените текущий кадр вызова.Поэтому максимальное используемое пространство - это когда вы делаете первые рекурсивные вызовы снова и снова.Что составляет максимум 1/2 из максимум 1/2 из ... в общей сложности log_2(n) фреймов вызова.

Если вы переключаетесь с наихудшего случая на средний случай с равномерно выбранной точкой поворота, этоO(log(n)) снова, но с лучшей константой.Прежде всего, это не может быть чем-то большим, потому что средний случай не может превышать худший случай.

Хитрость заключается в том, чтобы доказать, что вы не можете улучшить эту границу.Чтобы продемонстрировать это, мы можем доказать, что среднее пространство для сортировки массива размером n составляет по крайней мере C log(n+1)/(3 log(2)), где C - это пространство для одного вызова.

По проверке это верно дляn = 1, 2, ..., 7, поскольку первоначальный вызов занимает пробел C и log(n+1)/(3 log(2)) <= 1.

Если n больше 7 и утверждение верно до n, наша точка разбит нас на группыразмер m и n-m, где m <= n-m.С хотя бы четными коэффициентами n <= 4m и нашей ожидаемой максимальной стоимостью во время первого рекурсивного вызова - не менее 

C 1 + f(m)
  >= C  + f(n/4 rounded up)
  >= C (3 log(2)) /(3 log(2))    + C log(n/4 + 1)/(3 log(2)))
  >  C (3 log(2)                 + log(n+1) - 2 log(2)    ) / (3 log(2)) )
   = C (log(n+1) + log(2)) / (3 log(2))

В остальное время, которое не сохраняется, и нашими ожидаемыми максимальными затратами во время хвоста.рекурсивный вызов не менее 

f(n-m)
  >= f(n/2 rounded down)
  >= C log(n/2 + 1/2) / (3 log(2)) # n/2
   = C (log(n+1) - log(2)) / (3 log(2))

При усреднении этих двух значений вы получите желаемую нижнюю границу C log(n+1) / (3 log(2)).

(возможно, я допустил небольшую ошибку, но идея заключается в том, чтоправый.)

0 голосов
/ 16 октября 2018

См. Эту статью, охватывающую Хвостовая рекурсия

В статье говорится, что Пространственная сложность рекурсивной быстрой сортировки хвоста выглядит следующим образом: 

space complexity = input + O(log(n))

Aнесколько статей, чтобы получить более глубокое понимание, можно найти ниже:

...