假设树T是一棵二叉树。
Algorithm computeDepths(node, depth)
Input: node and its depth. For all depths, call with computeDepths(T.root, 0)
Output: depths of all the nodes of T
if node != null
depth ← node.depth
computeDepths(node.left, depth + 1)
computeDepths(node.right, depth + 1)
return depth
如果结束
我用包含 7 个元素的完整二叉树在纸上运行它，但我仍然无法理解它的时间复杂度。如果非要我猜的话，我会说是 O(n*log n)。
最佳答案
是O(n)
要了解时间复杂度，我们需要找出算法完成的工作量与输入大小的比较。在此算法中，每次函数调用完成的工作是恒定的(仅将给定值分配给变量)。那么让我们数一数该函数被调用了多少次。
第一次调用该函数时，它是在根上调用的。
然后对于任何后续调用，函数检查节点是否为 null，如果不为 null，则相应地设置深度并设置其子节点的深度。然后这是递归完成的。
现在请注意，该函数在树中的每个节点调用一次，加上叶子数量的两倍。在二叉树中，叶子的数量是n/2(四舍五入)，所以函数调用的总数是:
n + 2*(n/2) = 2n
这就是算法完成的工作量。所以时间复杂度是O(n)。
关于algorithm - 这个算法(伪代码)的时间复杂度是多少？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40796942/