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

2024-03-29 11:01:01 发布

您现在位置:Python中文网/ 问答频道 /正文

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

问题是,我不确定是使用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循环必须检查多个语句时会发生什么情况。在


Tags: andtrueifis时间数学语句解决方案
2条回答

两者都具有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

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

I recall that nested if result in O(N^2)

错误,嵌套的for循环的复杂度为O(N^2),而不是if。在

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

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

你会看到“你好”印了多少次?N^2,这就是复杂性。在

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

重要的是while循环中的代码“主体”执行的频率,这决定了复杂性。在

因为两个例子都有相同的复杂性,所以让我们来分解第一个:

^{pr2}$

b似乎是一个自变量,所以我们可以忽略它。如果xTrue,那么时间复杂度是无穷大的,因为while循环永远不会结束(至少在整数a溢出为负数之前)。注意,这意味着您的语句“while loop has complexity O(n)”也是错误的)。如果xFalse,那么代码的时间复杂度为O(a-1)(或者简单地说是O(a)),因为它将经历a-1次迭代。在

相关问题 更多 >