python - 两个递归 O(logn) 调用的大 O 运行时是多少？

Question

def f(L):
    if len(L) < 1 billion:
        return L
    else:
        return f(L[:len(L) // 2]) + f(L[len(L) // 2:])

L 是大小为 n 的列表

我知道如果是一次递归调用，那么时间复杂度就是O(logn)，但是这里有两次递归调用。

但是当我开始在可视化工具上运行它时，它开始表现出更多的 O(n) 运行时间。

我认为应该是 O(logn+logn) = O(2logn) = O(logn)。我说得对吗？

Answer 1

考虑一下您正在调用多少个电话。在递归的第一级，您将执行 2 次调用。对于每一个，您都将再进行两次调用。等等...这意味着在递归的第 i 层，您将总共进行 O(2^i) 次函数调用。

递归有多少层？这只是具有 n 个元素的二叉树的高度，即 O(log_2 n)。

因此，当您到达递归的所有叶子时，您将完成 O(2^(log_2 n)) = O(n) 函数调用。

--

另一种看待它的方式是，您最终必须将整个列表拼凑在一起，那么您怎么可能在 O(n) 时间内完成这一任务呢？