new*_*eyo 23 python loops time-complexity
嵌套的 for、while 和 if 语句的时间复杂度相同吗？假设a是一个长度为 的数组n。
for _ in range(len(a)):\n for _ in range(len(a)):\n do_something\n上面的 for 语句的复杂度为 O(n\xc2\xb2)。
\ni = 0\nwhile i < len(a) * len(a):\n do_something\n i += 1\n乍一看，上面的循环可以认为是 O(n)，但最终我认为也是 O(n\xc2\xb2)。
\n我对吗？
\ngsa*_*ras 49
\n\n我对吗？
\n
是的！
\n双循环：
\nfor _ in range(len(a)):\n for _ in range(len(a)):\n do_something\n时间复杂度为 O(n) * O(n) = O(n\xc2\xb2) 因为每个循环都运行到n。
单循环：
\ni = 0\nwhile i < len(a) * len(a):\n do_something\n i += 1\n时间复杂度为 O(n * n) = O(n\xc2\xb2)，因为循环运行到i = n * n = n\xc2\xb2。
Viv*_*ick 26
确实还是O(n^2)。当您查看具有 len(a)*len(a) 次迭代的循环时，这一点尤其明显。
您“扁平化”了循环，但没有改变工作量，因此这只是一种“风格”变化，对复杂性没有影响。
小智 7
我们需要根据构造所执行的操作数量来确定时间复杂度。概括地说某些循环具有特定的时间复杂度是不正确的。
嵌套 for 循环的时间复杂度通常为 O(n 平方) - 并非总是如此。一些涉及的嵌套 for 循环也可能只有 O(n) 复杂度。单个 if 语句通常是 O(1)，因为您只进行基本比较。while 循环可以是任何内容，具体取决于您的退出条件。
虽然记住这些概括可能很有用，但我们应该始终检查所执行的操作数量以确定复杂性。