Пространственная сложность построения бинарного дерева из обходов по порядку и по предзаказу

Question

Этот вопрос о ПРОСТРАНСТВЕ, а не о сложности времени.Более того, речь идет не о том, как решить вопрос, как я смог это сделать.Я пытаюсь выяснить пространственную сложность алгоритма в моем решении.Я нашел вопрос на Leetcode.Допущения и описание вопроса можно найти там.

Я понимаю сложность времени, как объяснено в этом сообщении StackOverflow , но пост не говорит о сложности пространства.

Я попытался объяснить это после окончания моегокод.

# Definition for a binary tree node.
class TreeNode(object):
  def __init__(self, x):
    self.val = x
    self.left = None
    self.right = None

class Solution(object):
  def buildTree(self, preorder, inorder):
    """
    :type preorder: List[int]
    :type inorder: List[int]
    :rtype: TreeNode
    """
    preorder.reverse()
    return self.buildTreeHelper(preorder, inorder)

  def buildTreeHelper(self, preorder, inorder):
    if not preorder or not inorder:
      return None

    rootValue = preorder.pop()
    root = TreeNode(rootValue)

    inorderRootIndex = inorder.index(rootValue)

    root.left = self.buildTreeHelper(preorder, inorder[:inorderRootIndex])
    root.right = self.buildTreeHelper(preorder, inorder[inorderRootIndex+1:])
    return root

Поскольку я посылаю фрагменты списка в рекурсивной функции, я использую больше места.Если мы не рассматриваем очистку пространства, то нам нужно O (n ^ 2) место для срезов списка.Мы могли бы предположить, что мы очищаем это пространство, поскольку мы продолжаем, но для каждого шага мы передаем 2n массива длины [pre & inorder] для всех n шагов.Какова сложность пространства, если мы считаем, что мы очищаем пространство?

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

Имеет ли смысл говорить, что сложность пространства тогда равна O (n ^ 3) из-за каждого добавления в стек вызовов или я дважды сосчитал, создавая дополнительную мощность?

Answer 1

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

Нет необходимости умножать на дополнительные nтермин для того факта, что у вас есть два списка или для пространства, занятого рекурсивным стеком вызовов.В большинстве случаев эти проблемы могут изменить его с n^2 на 2*n^2 или n^2 + n, а система обозначений big-O игнорирует постоянные кратные и медленнее растущие термины, подобные этим.