我正在研究各种解决方案的时间复杂性,而且由于我不是一个很喜欢数学的人,所以我不能很好地为我的呼吁找出最好的时间复杂性。在
问题是,我不确定是使用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循环必须检查多个语句时会发生什么情况。在
两者都具有O(n)的复杂度,n与while循环迭代有关。If-else语句不能改变这一点。想想看:当你的输入变量变为无穷大时,你的迭代计数是如何缩放的?线性的?立方?不然呢?在
例如,请检查以下伪代码:
我们有三次嵌套循环。所以复杂度是O(x*y*z),也就是O(n^3)。你不在乎条件,因为当变量变为无穷大时,迭代次数不会缩放。在
在决定复杂性时,通常应该检查嵌套循环,并检查哪些变量对迭代计数有重要意义。在
我还建议您阅读以下内容:https://www.cs.cmu.edu/~adamchik/15-121/lectures/Algorithmic%20Complexity/complexity.html
毕竟这是一个很深的话题。在
错误,嵌套的
for
循环的复杂度为O(N^2)
,而不是if
。在如果你有一个N大小的数组
你会看到“你好”印了多少次?N^2,这就是复杂性。在
请注意,在循环中做什么并不重要(无论是打印、添加还是执行if语句),这都是固定成本。因此,你重新安排if语句的事实并不重要-这两种情况都有完全相同的复杂性。在
重要的是while循环中的代码“主体”执行的频率,这决定了复杂性。在
因为两个例子都有相同的复杂性,所以让我们来分解第一个:
^{pr2}$b
似乎是一个自变量,所以我们可以忽略它。如果x
是True
,那么时间复杂度是无穷大的,因为while循环永远不会结束(至少在整数a
溢出为负数之前)。注意,这意味着您的语句“while loop has complexity O(n)”也是错误的)。如果x
是False
,那么代码的时间复杂度为O(a-1)
(或者简单地说是O(a)
),因为它将经历a-1
次迭代。在相关问题 更多 >
编程相关推荐