递归函数的复杂性(大O表示法)

Question

我有两个函数，我想确定它们的复杂性。

第一个问题我只需要知道我的求解是否正确，第二个问题是因为我正在努力寻找两个递归调用的解决方案，如果可能的话，最好进行求解，这样我就可以了解它是如何完成的。

第一：

def sum(list):
    assert len(list)>0
    if len(list) == 1:
        return list[0]
    else:
        return sum(list[0:-1]) + list[-1]

尝试的解决方案：

T(0) = 4
T(n) = T(n-1) + 1 + c -- True for all n >0 
T(n) = T(n-1) + 1 + c
     = T(n-2) + 2 + 2C
     = T(n-k) + k = kC --(n-k = 0 implies that k=n)
T(n) = T(0) + n + nC
     = T(0) + 2nC --(T0 is nothing but 4)
     = 6nC
Complexity = O(n)  

第二：

def binSum(list):
    if len(list) == 1:  
        return list[0]
    else:
        return binSum(list[:len(list)//2]) + binSum(list[len(list)//2:])

如有任何帮助，我们将不胜感激。

问候

Answer 1

对于第一种情况，可以使用递归函数T(n) = T(n-1) + O(1)和T(0) = O(1)对时间复杂性进行建模。明显地解决了CCD_ 3。

这里有一个更直接、更正式的归纳证明。根据O(1)的定义，基本情况很简单：T(0)<=C。对于归纳步骤，假设T(k) <= C*k对于所有k<=n对于某个绝对常数C>0。现在T(n+1) <= D + T(n) <= D + C*n <= max(C,D)*(n+1)通过归纳假设，其中D>0是一个绝对常数。

对于第二种情况，可以使用T(n) = T(n/2) + T(n/2) = 2T(n/2)为n>1和T(1)=O(1)建模时间复杂性。用主定理求解T(n)=O(n)。