嵌套if的时间复杂度，与时间的多个情况相比

Question

我正在研究各种解决方案的时间复杂度，因为我不太喜欢数学；我不能很好地计算出我的呼叫的最佳时间复杂度。

问题是，我不确定是否需要更长的时间才能通过带有1条语句的while循环获得嵌套的if-else，或者是否最好删除嵌套的if-else并在while循环中添加检查。

作为一般性的例子，这会执行得更快吗

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

而不是

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

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

Answer 1

两者都有O（n）的复杂性，n与while循环迭代有关。如果其他语句不能改变这一点。试想一下：当你的输入变量变为无穷大时，你的迭代计数是如何伸缩的？线性？立体的？否则呢？

例如，检查以下伪代码：

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

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

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

我还建议大家阅读以下内容：https://www.cs.cmu.edu/~adamchik/15-121/讲座/算法复杂性/复杂性。html

毕竟这是一个深奥的话题。

Answer 2

我记得嵌套if的结果是O（N^2）

错误，嵌套的for循环的复杂性为O（N^2）而不是if。

如果你有一个大小为N的数组

for i in arr:
    for j in arr:
        print "hello"

你会看到多少次“你好”的打印？N^2，这就是复杂性。

请注意，在循环中做什么并不重要（无论是打印、添加还是执行if语句），这都是固定成本。因此，你重新安排if语句的事实并不重要——这两种情况的复杂性完全相同。

重要的是while循环中的代码“主体”执行的频率，这就是复杂性的决定因素。

因为你们两个例子都有相同的复杂性，所以我们来分解第一个例子：

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

如果x是True，则您的时间复杂度是无穷大的，因为当循环永远不会结束（至少直到整数a溢出到负数为止。请注意，这意味着您的语句“当循环具有复杂性O（n）”也是错误的）。如果x是False，则您的代码的时间复杂度为O（a-1）（或简单地O（a）），因为它将通过a-1迭代运行。