space 这段代码的复杂度是多少？

Question

这段代码的时间复杂度是多少？

if not root:
    return 0 
    
if root.left is None and root.right is None:
    return 1

que = []
que.append(root)
maximum = 0
while que:
    for i in range(len(que)):
        node = que.pop(0)
        if node.left:
            que.append(node.left)
        if node.right:
            que.append(node.right)
    maximum += 1
return maximum

Answer 1

你基本上是在访问二叉树的所有节点。

因此，时间和 space 复杂度都是 O(N)（n == 节点数）。

编辑：由于您已将列表用于队列，时间复杂度为 O(N^2)，但有一个改进的途径，可以将性能提高到 O(N).

详细信息：

时间复杂度：您正在使用 list 而不是 built-in queue 或 deque。 list 的 append() 或 pop() 成本 O(1) 但 pop(0) 成本 O(N)。因此您的代码效率不高。这将需要 O(N^2) 只是因为您选择用作队列的数据结构。使用 built-in queue 或 deque 只需要 O(1) 来插入和弹出第一个元素。如果是这样，时间复杂度将是 O(N).

Space复杂度：算法一次遍历二叉树一层，所以在最高层达到队列中的最大项数，其中包含叶节点。
满二叉树有 (n+1)/2 个叶节点。 O((n+1)/2) = O(N).

Answer 2

我也同意时间和 space 复杂度 O(n)，其中 n 是代码数。但是，我认为对结果更详细的解释可以如下（假设root是树的根）：

时间复杂度：每个节点恰好进入que一次，恰好离开que一次。当一个节点离开时，最多执行 2 次检查和 2 次追加。当que为空时程序结束，导致时间复杂度为(2+2)*n=4n --> O(n)
Space 复杂度：que 在任何时候最多只能容纳图中的所有节点，导致 space 复杂度为 O(n)

space 这段代码的复杂度是多少？

What is the time, space complexity of this code?

python

big-o