两个递归O(logn)调用的最大Oh运行时是什么

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

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

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

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

--

另一种方法是，你最终必须把整个列表拼凑起来，那么你怎么可能在不到O(n)的时间内做到这一点呢？

Answer 2

如果len(L)至少为10亿，则您的算法将为O(n(，因为您将列表一分为二，然后将两半相加。切片和加法都是O(n(运算。

如果您想测试两个递归调用的运行时，

1.输入开始和结束索引，然后调用

f(L, start, start+(end-start)//2) + f(L, start+(end-start)//2, end)

2.当end-start小于10亿时，返回end-start或其他一些O(1(值