这个算法（伪代码）的时间复杂度是多少？
What's the time complexity of this algorithm (pseudo code)?
假设树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，如果不为空，则相应地设置深度并设置其子节点的深度。然后这是递归完成的。
现在请注意，树中的每个节点都会调用一次该函数，加上叶子数量的两倍。在二叉树中，叶子的数量是n/2（四舍五入），所以函数调用的总数是：
n + 2*(n/2) = 2n
这就是算法完成的工作量。所以时间复杂度是 O(n).
假设树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，如果不为空，则相应地设置深度并设置其子节点的深度。然后这是递归完成的。
现在请注意，树中的每个节点都会调用一次该函数，加上叶子数量的两倍。在二叉树中，叶子的数量是n/2（四舍五入），所以函数调用的总数是：
n + 2*(n/2) = 2n
这就是算法完成的工作量。所以时间复杂度是 O(n).