如何找到递归函数的时间复杂度？

Question

问题陈述：给定一棵二叉树和一个数字“sum”，找到从根到叶的所有路径，使得每条路径的所有节点值的总和等于“总和”。

如何计算这个算法的时间复杂度？

它的递归关系是什么？

   def func(currNode, sum, currPath, allPaths):
       if not currNode:
           return
       currPath.append(currNode.val)
       
       if currNode.val == sum and not currNode.left and not currNode.right:
           allPaths.append(currPath)
       else:
           func(currNode.left, sum-currNode.val, currPath, allPaths)
           func(currNode.right, sum-currNode.val, currPath, allPaths)
       currPath.pop()

Answer 1

这是 O(N)。没有循环，您将只访问每个节点一次。

Answer 2

我们假设树的高度是H。此外，假设递归创建了一个完整的二叉树，因此每个级别的 节点数将是 2^0、2^1、2^2、..... 2^(H-1 ).

 def func(currNode, sum, currPath, allPaths):
       if not currNode:
           return
       currPath.append(currNode.val) # ----------------> O(1)
       
       if currNode.val == sum and not currNode.left and not currNode.right:
           allPaths.append(currPath) # -----------------> O(H)
       else:
           func(currNode.left, sum-currNode.val, currPath, allPaths) # --> T(H-1)
           func(currNode.right, sum-currNode.val, currPath, allPaths) # --> T(H-1)
       currPath.pop() # ---------------------------------> O(1)

注意，currPath是一个列表，包含了从根到叶的所有路径的节点。因此，将该列表附加到列表 allPaths 将花费我们 O(H)。 记住，树的高度是'H'。

所以，最终的递归关系是：T(H) = O(H) + 2T(H-1) ----- (1)

T(0) = 1 ------ 基本情况

我们来求解递推关系： 将式(1)中的H用H-1代入式(2):

T(H-1) = (H-1) + 2T(H-2) ------------------ (2)

在解决 (1) 和 (2) 时，我们得到： T(H) = H + 2(H-1) + (2^2)T(H-2) --- (3)

再解决几次，我们得到这个模式：

T(H) = H*(2^0 + 2^1 +...+ 2^(k-1)) + (2^k)T(H-k) - [(2^1)*1 + (2^2)*2 +....+(2^(k-1))*(k-1)] -------------- (4)

T(H) = H*(2^k - 1) + 2^k - k*(2^(k-1)) - 2*k -------------- (5)

现在，当 H-k = 0 时，我们得到 T(H-k) = 1（基本情况）。 因此，k = H。

上，将式(5)中的k = H代入得到, T(H) = O(H*(2^H)) -------------- (6)

式(6)是上述算法的最终复杂度。现在，让递归树中的总节点数为 N，则 N = 每一层上的总节点数之和。即 N = 2^H - 1 或 H = logN.

所以，时间复杂度可以重写为：O(NlogN)

如何找到递归函数的时间复杂度？

How to find time complexity of recursive function?

python

binary-tree

time-complexity