两次调用的递归函数的时间复杂度

考虑这段代码：

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:])

note:切片操作将被视为 O(1)。

所以，我的直觉告诉我它是 O(n*logn)，但我正在努力科学地证明它。
很高兴获得帮助！

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

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 when k == logN so:

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

since T(1) = 1并应用对数属性

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.

UPDATE:直觉背后

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

例如，您将问题分为两个大小一半的子问题，然后每个子问题也分为大小的一半，并且将继续下去，直到每个子问题的大小为 1。完成后，您将有 n 个大小为 1 的子问题，即n*O(1) = O(n).

从第一个问题开始到 N 个大小为 1 的问题的路径是对数的，因为在每一步中您都将其细分为两部分。但在每个步骤中，您不对结果执行任何操作，因此这不会增加解决方案的时间复杂性。

希望这可以帮助