algorithm - 大 O 符号是否适用于 while(true) 循环？

Question

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

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

Answer 1

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

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

一般来说，您在算法中使用的控制流语言结构类型并不重要(例如 while 与 for，与尾递归)，因为你可以只写一个等效的算法，它用不同的控制流结构做同样的事情。等效算法将以相同数量的步骤执行，因此以这种方式更改语法不会影响分析结果。 very first algorithm analysis由 Donald Knuth 在 flowcharts 上完成, 哪个 control-flow graph (包括for while(true)/break)可以转化为。