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( 表示的。