嵌套if的时间复杂度与whi中多个情况的比较

Question

我正在研究各种解决方案的时间复杂性，而且由于我不是一个很喜欢数学的人，所以我不能很好地为我的呼吁找出最好的时间复杂性。在

问题是，我不确定是使用1语句完成while循环并嵌套if-else需要更长的时间，还是最好删除嵌套的if-else并在while循环中添加检查。在

作为一个通用的例子，这样做会更快吗

while a>1 and b is True
    if x is True:
        a -= 1
    else
        a += 1

而不是

^{pr2}$

我记得嵌套if的结果是O（N^2），而一个简单的while循环有复杂度O（N），但是while循环必须检查多个语句时会发生什么情况。在

Answer 1

两者都具有O（n）的复杂度，n与while循环迭代有关。If-else语句不能改变这一点。想想看：当你的输入变量变为无穷大时，你的迭代计数是如何缩放的？线性的？立方？不然呢？在

例如，请检查以下伪代码：

for(x time)
    for(y time)
        for(z time)
            do ....
            if(z=x+y)

我们有三次嵌套循环。所以复杂度是O（x*y*z），也就是O（n^3）。你不在乎条件，因为当变量变为无穷大时，迭代次数不会缩放。在

在决定复杂性时，通常应该检查嵌套循环，并检查哪些变量对迭代计数有重要意义。在

我还建议您阅读以下内容：https://www.cs.cmu.edu/~adamchik/15-121/lectures/Algorithmic%20Complexity/complexity.html

毕竟这是一个很深的话题。在