DEV Community
·
今天学到：在某些情况下，嵌套的for/while循环可以具有O(N)时间复杂度（技术面试中的数据结构与算法）
💡
原文英文，约400词，阅读约需2分钟。
📝
内容提要
在Python中，嵌套循环的时间复杂度取决于结构。如果for循环中嵌套的while循环每次只执行常数次或总次数不超过N，复杂度为O(N)。若while循环每次执行N次，则复杂度为O(N^2)。关键在于while循环的迭代次数是否与for循环独立。
🎯
关键要点
- 在Python中，嵌套循环的时间复杂度取决于循环的结构。
- 如果while循环在for循环中每次只执行常数次，复杂度为O(N)。
- 如果while循环每次执行N次，复杂度为O(N^2)。
- while循环的迭代次数是否与for循环独立是关键。
- 示例1：for循环运行N次，while循环每次只执行一次，整体复杂度为O(N)。
- 示例2：for循环运行N次，while循环最多执行5次，整体复杂度为O(N)。
- 示例3：for循环运行N次，while循环总共执行N次，整体复杂度为O(N)。
- 如果内层while循环的迭代次数独立于for循环，整体复杂度可以保持为O(N)。
- 只有当内层while循环在每次外层for循环中执行N次时，复杂度才会为O(N^2)。
➡️
