Как вычислить сложность пространства для рекурсивной функции

Question

Я знаю, что сложность пространства для кучи сортирует его O (1). Но для рекурсивной программы при вычислении сложности пространства учитывается глубина, на которую она идет, т. Е. Количество рекурсивных вызовов, которые она делает. Таким образом, сложность пространства для итеративного и рекурсивного подхода для одного и того же кода отличается. Итак, какова будет сложность пространства для сортировки кучи при рекурсивном подходе?

Answer 1

Когда функция heapify реализована с использованием рекурсии, она будет выглядеть примерно так: псевдокод:

heapify(arr, n, root): 
    largest = root 
    left = 2*root + 1 
    right = 2*root + 2
    if left < n && arr[left] > arr[largest]: largest = left
    if right < n && arr[right] > arr[largest]: largest = right 
    if largest != root:
        swap(arr[root], arr[largest])
        heapify(arr, n, largest)

Напомним, функция heapify используется для того, чтобы сначала превратить массив в кучу, а затем упорядочить массив с кучей, размер которой уменьшается.

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

Таким образом, если рекурсивный алгоритм также не определяет как рекурсивный вызов должен быть реализован "под капотом" - возможно исключая механику хвостовой рекурсии - он все еще может быть реализован с помощью O (1) пробел.

Если, однако, хвостовая рекурсия не используется, то следует учитывать глубину рекурсии. Эта глубина - самое большее глубина дерева (кучи), которая составляет logn .

Answer 2

Вы правы, это O (1) только если вы выполняете операцию heapify итеративно.

В случае рекурсивного подхода, аналогичного описанному здесь HeapSort , сложность памяти становится O (log N) .

Сложность памяти рекурсивной функции рассчитывается путем умножения глубины рекурсивных вызовов на сложность памяти одного вызова, в нашем случае глубина O (log N), а одного вызова O (1)