问题描述
我有一个家庭作业问题，要求我对以下Python代码的最坏情况下的时间复杂性进行严格的估计：
sum = 0
i = n
while i > 1:
for k in range(n*n):
sum = sum + k*i
i = i // 2
由于线i = i // 2，外循环似乎具有O（log n）时间复杂度。内循环似乎具有O（n ^ 2）时间复杂度，因为范围为n * n 。 这两个回路似乎彼此独立，因此总的时间复杂度是否为O（n ^ 2）？
1楼
您可能将复杂度视为完成给定任务所需的简单操作数。
现在，您的外循环说您执行了给定的操作log(n)次，您在问题中正确指出了该次数。
但是，这些操作并不简单-它们包含执行一个循环。
再次指出，此循环执行O(n^2)简单操作。
现在尝试思考一下代码片段执行的简单操作的总数是多少？
注意：在我的回答中，我假设加法和整数除法是简单的运算。