渐近分析: Python Big-O作业
渐近分析: Python Big-O作业
提问于 2014-03-24 05:49:30
我有一个家庭作业问题，要求我对以下Python代码的最坏情况下的时间复杂度进行严格的big-o估计：
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 )时间复杂度。内部循环似乎具有O(n^2)时间复杂度，因为范围是n*n。两个循环似乎彼此独立，那么总体时间复杂度是O(n^2)吗？
回答 1
Stack Overflow用户
发布于 2014-03-24 22:37:29
您可以将复杂性视为完成给定任务所需的简单操作的数量。现在，您的外部循环表明您执行了给定的操作log(n)次，您在问题中正确地指出了这一点。然而，这些操作并不简单-它们包括执行一个循环。正如您再次正确指出的那样，此循环执行O(n^2)简单操作。现在试着思考一下代码片段执行的简单操作的总数是多少？
注意:在我的答案中，我假设加法和整数除法是简单的操作。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/22597566
复制相关文章
相似问题
腾讯云开发者
