Как сложность пространства O (m + n) здесь?

Question

Слияние двух отсортированных связанных списков и возврат их в виде нового списка. Новый список следует создать, соединив узлы первых двух списков.

class Solution:
    def mergeTwoLists(self, l1, l2):
        if l1 is None:
            return l2
        elif l2 is None:
            return l1
        elif l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

Я знаю, что это как-то связано со стеком. Может кто-нибудь прояснить это для меня? Я новичок в этом спасибо.

Answer 1

Принципиальная особенность алгоритма состоит в том, что каждый рекурсивный вызов выбирает один элемент из l1 или l2. Поскольку это может произойти только M + N раза, временная сложность составит O(M + N).

Пространственная сложность - это другое дело.

Я знаю, что есть чем заняться со стеком.

Да. В Python для рекурсивных вызовов требуется кадр стека для каждого уровня рекурсии. Кадр стека содержит аргументы вызова и локальные переменные, а также информацию, необходимую для разрешения возврата вызова в правильное место в коде, который его вызвал.

В вашем примере есть уровни M + N, поэтому пространство сложность стекового пространства составляет O(M + N).

Если предположить, что узлы связанного списка реализованы очевидным образом, ваш метод слияния мутирует объекты l1 и l2 и больше не потребляет space.

---

Многие языки / компиляторы поддерживают то, что называется оптимизация хвостового вызова для многих случаев, когда метод рекурсивно вызывает сам себя. По возможности рекурсивный вызов оптимизируется для перехода к началу метода, а не для использования инструкции вызова. Таким образом, кадр стека не требуется.

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

Однако Python не поддерживает ; см. Оптимизирует ли Python хвостовую рекурсию?