时间复杂度

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 

因为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. 完成后，您将拥有大小为1的子问题，即n*O(1) = O(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 ......但复杂性是一样的。