为何该递归函数时间复杂度为O(n)而非O(nlogn)？

首先看你的递归函数：

def function(n):
    if n <= 1:
       return
    function(n / 2)
    function(n / 2)

我们用递推公式来推导时间复杂度：

• 设T(n)表示处理输入规模为n时的总时间。
• 当n <= 1时，函数直接返回，没有递归调用，所以T(n) = O(1)（常数时间）。
• 当n > 1时，函数会递归调用两次function(n/2)，除此之外没有其他耗时操作（只有条件判断和函数调用的常数开销），因此递推式为：T(n) = 2*T(n/2) + O(1)

接下来用递归树法计算这个递推式：

1. 每一层的节点数：第0层（根节点）是1个，第1层是2个，第k层是2^k个节点。
2. 每一层的输入规模：第k层每个节点的输入规模是n/(2^k)，当n/(2^k) = 1时，递归停止，此时k = log₂n（也就是树的高度）。
3. 每一层的总时间：因为每个节点的耗时是O(1)，所以第k层的总时间是2^k * O(1)。
4. 总和计算：把所有层的时间加起来，就是O(1)*(2^0 + 2^1 + ... + 2^log₂n)。这是一个等比数列求和，结果是O(1)*(2^(log₂n + 1) - 1) = O(1)*(2n - 1)，也就是O(n)。

你之所以误以为是O(nlogn)，是混淆了另一种常见场景——比如归并排序的递推式是T(n) = 2*T(n/2) + O(n)（每次递归除了调用两次，还要做O(n)的合并操作），这种情况才会得到O(nlogn)的复杂度。而你的函数每次递归只有常数级的额外操作，所以最终时间复杂度是O(n)。

内容的提问来源于stack exchange，提问作者NooBabyyy