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

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

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) [в чем я не совсем уверен], но как повлияет пространственная сложность, если опорная точка затем выбирается равномерно в случайный? Я новичок в понимании сложности пространства по сравнению со сложностью времени, поэтому любые отзывы приветствуются!


partitioning algorithm quicksort space-complexity
person Joe Cur    schedule 16.10.2018    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Обратитесь к этой статье, посвященной хвостовой рекурсии

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

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

Несколько статей для более глубокого понимания можно найти ниже:

person B. Cratty    schedule 16.10.2018
comment
Также обратитесь к другому сообщению, если вы все еще ищете дополнительную информацию. - person B. Cratty; 16.10.2018
comment
В приведенной выше статье все прекрасно и модно, но в ней явно не указано, выбирается ли точка поворота состязательно или равномерно случайным образом, что, как я предполагаю, влияет на сложность пространства. - person Joe Cur; 16.10.2018
comment
Для пространственно-временной сложности всегда есть лучшие и худшие сценарии. В основном это то, что отличается по временной сложности. Когда дело доходит до сложности пространства, это будет зависеть от типа раздела, который вы используете в своей реализации быстрой сортировки. То, о чем я говорю, может иметь большее значение, поскольку после прочтения раздела о сложности пространства в этой статье здесь. Дайте мне знать, если это поможет ответить на ваши вопросы. @JoeCur - person B. Cratty; 16.10.2018
comment
Итак, оба метода выбора опорных точек занимают пространство O (logn)? - person Joe Cur; 16.10.2018
comment
Из того, что мне удалось собрать. Я нашел несколько других статей, в которых обсуждается алгоритм анализа быстрой сортировки. Хотите, чтобы и их тоже читали? @JoeCur - person B. Cratty; 16.10.2018
comment
Да, но я не совсем уверен, что это правда вообще. - person Joe Cur; 16.10.2018

arrow_upward
0
arrow_downward

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

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

person btilly    schedule 16.10.2018