Big O 表示法是否适用于 while(true) 循环？

Question

while(true) {
    System.out.println("hola");
    break;
}

我在这里有一个while带有true条件的循环的代码片段。我想知道是否可以将大 O 符号应用于此代码片段。

Answer 1

Big O 表示法是我们可以用来分析算法的工具。我们应用它的方法是计算算法执行的步数，将步数表示为输入大小n的函数，并通过忽略常数因子和支配项来简化计数/分析。

对于你的算法，没有“输入”，所以不清楚n应该指什么，但步数也是固定的；它打印一个固定长度的字符串，然后break语句终止循环。所以它的运行时间是 O(1)，即常数。

一般来说，你在算法中使用的控制流语言结构的种类并不重要（例如whilevs. for, vs. 尾递归），因为你可以编写一个等效的算法，用不同的控制流结构做同样的事情. 等效算法将以相同数量的步骤执行，因此以这种方式更改语法不会影响分析结果。的非常第一算法分析物通过高德纳上完成的流程图，其中的任何控制流图（包括while(true)/ break）可以转化成。