时间戳

首页 > 解决方案 > while循环时间复杂度内的两个条件

java - while循环时间复杂度内的两个条件

问题描述

而（varz > deviceNum || varz == 0）；

我有这段代码，我想测量它的时间复杂度，但我很困惑它是大 O(n) 还是 o(n^2)，因为它里面有两个条件

标签： javawhile-looptime-complexitybig-o

解决方案

这取决于 while 循环内部的内容，以及此示例中“N”代表的内容。假设 N 是“equipmentnumz”并且在 while 内部不存在内部循环，这是一个 O(n) 算法。

相比之下，O(n)^2 将是一个嵌套循环（例如，另一个循环内部的循环）。例子：

while ($x < 1000): 
    while ($y < 1000): 
        y = y + 1
    x = x + 1

O(n) 表示法本身与算法如何处理不断增加的数据集的行为有关。如果列表大小加倍，O(n) 算法的时间正好是两倍。如果将列表加倍，上面的示例将花费两倍的时间（实际上它会花费很多倍的时间）。因为所需的迭代次数为 n^2，所以这是一个 O(n^2) 算法。

什么是 O(n)？

O(n) 算法随数据集线性扩展。以下示例都是 O(n)。

# O(n) algorithm
while (number < 1000): 
    number = number + 1; 

# Example 2. Also O(n) 

while (number < 1000): 
    number = number * 2; 
    number = number / 2; 
    number = number + 1;

虽然第二个例子有更多的代码并且需要更长的执行时间，但如果你将 N 的大小加倍，它仍然只需要恰好两倍的时间。因此，它是 O(n)，所需的时间与数据集的大小。

计算 O(n) 的实际过程比这篇文章能够充分涵盖的要复杂得多。这篇文章有一个很好的解释和更多的信息。（此页面也可能会有所帮助。它以更简单的术语解释了其背后的概念/理论。）

推荐阅读