O(logn) 外循环内 O(n) 的时间复杂度

Question

我想弄清楚这个算法的时间复杂度。A 是数组输入。顺便说一下，代码没有运行，只是为了演示目的。

def func(A):
    result = 0
    n = len(A)
    while n > 1:
        n = n/2
        result = result + min(A[1,...,n])
    return result

这假设数组 A 的长度为 n。

我假设它的时间复杂度为 O(n(log n))，因为 while 循环的复杂度为 O(log n)，而 min 函数的复杂度为 O(n)。然而，这个函数的复杂度显然是 O(n) 而不是 O(n(log n))。我想知道这怎么可能？

Answer 1

您线性获得的总迭代次数取决于 n。它是 n/2 + n/4 + n/8 + ... = n(1/2 + 1/4 + 1/8 + ...) 这就是 O(n) 表示的。