python - 具有两次调用的递归函数的时间复杂度

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)。

所以，我的 inutation 告诉我它是 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

因为 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 .

更新:背后的直觉

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

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

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

希望对你有帮助