时间戳

首页 > 解决方案 > Big O 表示法是否适用于 while(true) 循环？

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

问题描述

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

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

标签： algorithmbig-o

解决方案

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

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

一般来说，您在算法中使用的控制流语言结构的类型并不重要（例如whilevs. for，vs. 尾递归），因为您可以编写一个等效的算法，用不同的控制流结构做同样的事情. 等效算法将以相同数量的步骤执行，因此以这种方式更改语法不会影响分析结果。Donald Knuth 对流程图进行了第一个算法分析，任何控制流图（包括 for / ）都可以转换为流程图。while(true)break

推荐阅读