具有两个调用的递归函数的时间复杂性

Question

考虑以下代码：

def count_7(lst):
    if len(lst) == 1:
        if lst[0] == 7:
            return 1
        else:
            return 0
    return count_7(lst[:len(lst)//2]) + count_7(lst[len(lst)//2:])

注意：切片操作将被视为O（1）。

所以，我的因纽特人告诉我它是O（n*logn），但我很难用科学的方法证明它
很高兴得到帮助！

Answer 1

好的，从数学上（有点；）我得到了这样的东西：

T(n) = 2T(n/2) + c
T(1) = 1

推广方程式：

T(n) = 2^k * T(n/2^k) + (2^k - 1) * c
T(1) = 1

n/2^k == 1当k == logN如此时：

T(n) = 2^logN * T(1) + (2^logN - 1) * c

由于CCD_ 3和应用对数性质

T(n) = n * 1 + (n-1) * c
T(n) = n + n * c
T(n) = n * (1+c)
T(n) = O(n)

这不是O(n*logn)的一个线索是，您不必将这两个子问题结合起来。与必须组合两个子数组的mergesort不同，该算法不必对递归结果做任何处理，因此其时间可以表示为常数c。

更新：背后的直觉

这个算法应该是O（n），因为您只访问数组中的每个元素一次。这可能看起来并不微不足道，因为递归从来都不是。

例如，您将问题划分为大小为一半的两个子问题，然后每个子问题也被划分为大小的一半，并将继续进行，直到每个子问题的大小为1当您完成时，您将有n个子问题，大小为1，即n*O(1) = O(n)

从第一个问题开始到N个大小为1的问题的路径是对数的，因为在每一步中你都会细分为两个。但在每一步中，您都不处理结果，因此不会给解决方案增加任何时间复杂性。

希望这能帮助

Answer 2

为了简单起见，最简单的方法是假设n是2的倍数：n = 2m

你的算法的时间复杂度是（c是一个常数）：

t(n) = 2 t(n/2) + c

使用递归可以得到：

t(n) = 22 t(n/22) + 2c + c

     ...

     = 2log(n) t(n/2log(n)) + c(2log(n)-1 + ... + 22 + 21 + 20)

可以通过注意到log(n) = m，从而2log(n) = 2m = n。

     = n + c(2log(n)-1 + ... + 22 + 21 + 20)

最后，上述总和可以减少为2log(n)（等于n）

 t(n) = (1 + c) n

所以你的解决方案是O（n）

Answer 3

您扫描列表中的所有元素一次，即O（n）。与简单递归扫描的唯一区别是您扫描它们的顺序。你做1，n/2，2，3/4n等…而不是1,2,3。。。。但是复杂性是一样的。