当两个嵌套循环被重新写入一个循环时，时间复杂度会改变吗？

Question

嵌套for、while和if语句的时间复杂度相同吗？假设a作为长度n的数组给出。

for _ in range(len(a)):
    for _ in range(len(a)):
        do_something

上述声明的适用范围为O（n²）。

i = 0
while i < len(a) * len(a):
    do_something
    i += 1

乍一看，上面的循环可以被认为是O（n），但最终我认为它也是O（n²）。

我没说错吧？

Answer 1

我们需要根据IMHO执行的操作数量来确定时间复杂度。笼统地说某些循环具有特定的时间复杂性是不正确的。

嵌套for循环的时间复杂度通常为o（n平方）-并不总是如此。一些涉及嵌套for循环的操作也可能只有O（n）复杂度。单个if语句通常是O（1），因为您只进行基本的比较。而循环可以是任何东西，这取决于你的退出条件。

虽然记住这些概括可能是有用的，但我们应该始终检查所执行的操作的数量以确定复杂性。

Answer 2

它确实仍然是O（n^2）。当您查看具有len（a）*len（a）迭代的循环时，这一点尤其清楚。

你“展平”了循环，但没有改变工作量，因此这只是一个“风格”变化，对复杂性没有影响。

Answer 3

我没说错吧？

是的！

双循环：

for _ in range(len(a)):
    for _ in range(len(a)):
        do_something

时间复杂度为O（n）*O（n）=O（n²），因为每个循环一直运行到n。

单回路：

i = 0
while i < len(a) * len(a):
    do_something
    i += 1

时间复杂度为O（n*n）=O（n²），因为循环一直运行到i=n*n=n²。