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

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

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 ответа

Худший случай для времени - это если вы разделите массив как можно неравномернее, и это время будет 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)),

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

Источник

См. Эту статью о рекурсии хвоста

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

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

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

Источник
Другие вопросы по тегам