Python时间复杂度计算题答案

评论

题目链接

• https://blog.csdn.net/qq_33254766/article/details/132255078

答案

1. 时间复杂度：O(n)。
   分析：这段代码遍历了n次，所以时间复杂度是线性的，即O(n)。

2. 时间复杂度：O(n^2)。
   分析：两个嵌套的循环，每个循环都运行n次，因此时间复杂度是二次的，即O(n^2)。

3. 时间复杂度：O(log n)。
   分析：每次循环i都翻倍，因此循环的次数是log2(n)。

4. 时间复杂度：O(n*m)。
   分析：两个嵌套循环，第一个循环n次，第二个循环m次，因此总的循环次数是n乘以m。

5. 时间复杂度：O(n)。
   分析：列表推导遍历了n次，所以时间复杂度是线性的。

6. 时间复杂度：O(n + m)。
   分析：两个独立的循环，分别循环n次和m次，因此总时间复杂度是n加上m。

7. 时间复杂度：O(n)。
   分析：遍历了整个列表一次，因此时间复杂度是线性的。

8. 时间复杂度：O(log n)。
   分析：二分查找每次将搜索范围减半，因此时间复杂度是对数级的。

9. 时间复杂度：O(n)。
   分析：递归调用n次，每次减1，因此是线性的。

10. 时间复杂度：O(n^2)。
    分析：两个嵌套循环，最坏情况下每个元素都和其他元素比较一次。

11. 时间复杂度：O(n^3)。
    分析：三个嵌套循环，每个循环n次，因此时间复杂度是立方的。

12. 时间复杂度：O(nml)。
    分析：三个嵌套循环，分别是n、m、l次，因此总的时间复杂度是它们的乘积。

13. 时间复杂度：O(n)。
    分析：单个循环遍历整个列表一次。

14. 时间复杂度：O(log n)。
    分析：每次循环将i减半，因此循环的次数是log2(n)。

15. 时间复杂度：O(n^2)。
    分析：两个嵌套循环，第二个循环的次数随第一个循环的变量增加，总的时间复杂度是二次的。

16. 时间复杂度：O(n^2)。
    分析：两个嵌套循环，虽然第二个循环的起始点随第一个循环的变量变化，但总的时间复杂度依然是二次的。

17. 时间复杂度：O(n + m)。
    分析：两个独立的循环，分别是n次和m次。

18. 时间复杂度：O(n)。
    分析：两个独立的循环，每个循环遍历n次，但总的时间复杂度依然是线性的。

19. 时间复杂度：O(2^n)。
    分析：递归调用指数级增长，每一层都产生两个新的调用。

20. 时间复杂度：O(n + m)。
    分析：两个独立的循环，分别是n次和m次。

这些问题覆盖了基本的线性、对数级、平方级、立方级以及指数级时间复杂度。理解这些概念对于评估算法效率至关重要。