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)。我说得对吗?
最佳答案
考虑一下您正在调用多少个电话。在递归的第一级,您将执行 2 次调用。对于每一个,您都将再进行两次调用。等等...这意味着在递归的第 i
层,您将总共进行 O(2^i)
次函数调用。
递归有多少层?这只是具有 n
个元素的二叉树的高度,即 O(log_2 n)
。
因此,当您到达递归的所有叶子时,您将完成 O(2^(log_2 n)) = O(n)
函数调用。
--
另一种看待它的方式是,您最终必须将整个列表拼凑在一起,那么您怎么可能在 O(n)
时间内完成这一任务呢?
关于python - 两个递归 O(logn) 调用的大 O 运行时是多少?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23231799/