python - 有人可以用大 Oh 表示法计算时间复杂度吗

Question

有人可以帮我解释一下这个算法的复杂性吗？我已经尝试了一个小时，但我不明白递归的复杂性。我知道前 3 个语句是 O(1)，并且认为下面的语句是 O(n/2) 和 O(n/2)，所以加起来是 O(n)，但我不确定。

def sum(a):
    if len ( a ) == 0:
        return 0
    elif len ( a ) == 1:
        return a [0]
    m = len (a )//2

    b = sum (a [: m ])
    c = sum (a [ m :])

    return b + c

Answer 1

如果考虑递归调用该函数的次数，则该数字为2n-1。对于每次调用，您都有恒定数量的恒定时间操作(因此 O(1))。

总而言之，时间复杂度为O(n)，与列表的长度成线性关系。

您可以尝试定义一个递归关系来形式化地证明它。

注意
由于每次迭代时使用的切片操作，这个问题可能很棘手。这取决于实现细节(对于 python 来说，它看起来是 O(k) ，其中 k 是列表的长度，但对于 numpy 来说，它应该是 O( 1) 正如评论中指出的那样)并且可以很容易地通过传递索引(例如开始、结束)而不是切片列表来替换。
这里我假设操作需要恒定时间。