渐近分析：Python 大O作业

Question

我有一个作业问题，要求我给出以下Python代码在最坏情况下的时间复杂度的紧凑大O估计：

sum = 0
i = n
while i > 1:
    for k in range(n*n):
        sum = sum + k*i
    i = i // 2

外层循环看起来有O(log n)的时间复杂度，因为有一句代码是i = i // 2。内层循环似乎有O(n^2)的时间复杂度，因为它的范围是n*n。这两个循环似乎是相互独立的，所以整体的时间复杂度会是O(n^2)吗？

Answer 1

你可以把复杂度想象成完成一个任务所需的简单操作次数。现在，你的外层循环表示你要执行某个操作 log(n) 次，这一点你在问题中说得很对。不过，这些操作并不简单——它们实际上是一个循环。这个循环会执行 O(n^2) 次简单操作，正如你所指出的那样。现在，试着想一下，这段代码总共会执行多少次简单操作呢？

注意：在我的回答中，我假设加法和整数除法是简单操作。