理解时间复杂度，大 O 符号

Question

编辑-这个问题来自我课程中的一个以前的测试，官方答案是O(n)

我需要帮助来理解为什么以下代码中的运行时间复杂度是 O(n) 而不是 O(n*log(n))

def fun(n):
   total = 0
   while n > 5:
       n = n // 2
       total += sum(range(n))
   return total

while 循环执行 log(n) 次，并且在每次迭代中求和函数对 n/2 个数字求和，因此它的复杂度是 o(n)，我看到每个 while迭代有更少的数字求和，但我不明白为什么它是 O(n)。

谢谢。

Answer 1

所以我想通了。

每个 while 迭代求和 n/2 项。这意味着总迭代次数为 n + n +n +...，此和收敛为 n

Understanding time complexity, big-O notation