这在技术上是 "Hello World" 的 O(1) 算法吗？
Is this technically an O(1) algorithm for "Hello World"?
这会被归类为 "Hello, World!" 的 O(1) 算法吗？？
public class Hello1
{
public static void Main()
{
DateTime TwentyYearsLater = new DateTime(2035,01,01);
while ( DateTime.Now < TwentyYearsLater )
{
System.Console.WriteLine("It's still not time to print the hello ...");
}
System.Console.WriteLine("Hello, World!");
}
}
我正在考虑使用
DateTime TwentyYearsLater = new DateTime(2035,01,01);
while ( DateTime.Now < TwentyYearsLater )
{
// ...
}
代码片段作为一个繁忙的循环，当有人要求某种复杂性的算法时作为一个笑话。这是正确的吗？
此上下文中的大 O 表示法用于描述函数输入的大小与计算该输入的结果需要执行的操作数之间的关系。
您的操作没有与输出相关的输入，因此使用大 O 表示法是荒谬的。该操作花费的时间是 独立于 的操作输入（即...none）。由于输入和执行的操作数之间没有关系，你不能用Big O来描述不存在的关系
Big-O 表示法大致表示 'given an operation on an amount of work, N, how much calculation time, proportional to N, does the algorithm take?'。例如，对大小为 N 的数组进行排序可以采用 N^2、Nlog(N) 等
这没有任何输入数据可供操作。所以不是 O(anything).
更糟；这在技术上不是算法。算法是一种计算数学函数值的方法——数学函数是从一个输入到输出的映射。由于这不需要任何输入并且 returns 什么也没有，所以它不是数学意义上的函数。来自维基百科：
An algorithm is an effective method that can be expressed within a
finite amount of space and time and in a well-defined formal language
for calculating a function. Starting from an initial state and initial
input (perhaps empty), the instructions describe a computation that,
when executed, proceeds through a finite number of well-defined
successive states, eventually producing "output" and terminating at a
final ending state.
从技术上讲，这是一个控制系统。来自维基百科；
A control system is a device, or set of devices, that manages,
commands, directs or regulates the behavior of other devices or
systems.
如果人们想要更深入地了解数学函数和算法之间的区别，以及计算机更强大的处理控制台输出、显示图形或控制机器人等副作用的能力，请 read of this paper on the Strong Church-Turing Hypothesis
摘要
The classical view of computing positions computation as a closed-box transformation of inputs (rational numbers or finite strings) to outputs. According to the interactive view of computing, computation is an ongoing interactive process rather than a function-based transformation of an input to an output. Specifically, communication with the outside world happens during the computation, not before or after it. This approach radically changes our understanding of what is computation and how it is modeled.
The acceptance of interaction as a new paradigm is hindered by the Strong Church-Turing Thesis (SCT), the widespread belief that Turing Machines (TMs) capture all computation, so models of computation more expressive than TMs are impossible. In this paper, we show that SCT reinterprets the original Church-Turing Thesis (CTT) in a way that Turing never intended; its commonly assumed equivalence to the original is a myth. We identify and analyze the historical reasons for the widespread belief in SCT. Only by accepting that it is false can we begin to adopt interaction as an alternative paradigm of computation
Big-O 分析处理涉及的处理量，因为正在处理的数据量无限制地增加。
在这里，您实际上只处理一个固定大小的对象。因此，应用大 O 分析在很大程度上（主要是？）取决于您如何定义术语。
例如，您可能指的是一般打印输出，并强制等待很长时间，以便在完全相同的时间段内打印任何合理数量的数据 would/will。您还必须以一些不寻常的（如果不是完全错误的）定义的方式添加更多内容才能走得更远——特别是，大 O 分析 通常 定义为执行特定任务所需的基本操作的数量（但请注意，复杂性也可以从内存使用等方面考虑，而不仅仅是 CPU use/operations 执行）。
然而，基本操作的数量通常与所花费的时间相当接近，因此将两者视为同义词并不过分。然而，不幸的是，我们仍然坚持另一部分：正在处理的数据量无限制地增加。既然如此，你施加的任何固定延迟都不会真正奏效。要将 O(1) 等同于 O(N)，您必须施加无限延迟，以便任何固定数量的数据都需要永远打印，就像无限量的数据一样。
我有点不同意Servy。这个程序有一个输入，即使它不明显，那就是系统的时间。这可能是您意想不到的技术问题，但您的 TwentyYearsFromNow 变量距离 系统现在的时间 不到二十年，它被静态分配到 2035 年 1 月 1 日。
因此，如果您使用此代码并在系统时间为 1970 年 1 月 1 日的机器上执行它，则无论计算机有多快（可能会有一些差异），都需要 65 年才能完成如果它的时钟有故障）。如果您使用此代码并在系统时间为 2035 年 1 月 2 日的机器上执行它，它将几乎立即完成。
我会说你的输入 n 是 January 1st, 2035 - DateTime.Now，并且是 O(n)。
然后还有操作次数的问题。有些人注意到更快的计算机会更快地进入循环，从而导致更多的操作，但这无关紧要。使用大 O 表示法时，我们不考虑处理器的速度或确切的操作数。如果您采用此算法并在计算机上 运行 它，然后再次 运行 它但在同一台计算机上运行 10 倍的时间，您会期望操作数以 10 倍的相同因子增长。
至于这个：
I'm thinking of using the [redacted code] snippet of code as a busy loop to put in as a joke whenever someone asks for an algorithm of a certain complexity. Would this be correct?
不，不是真的。其他答案已经涵盖了这一点，所以我只是想提一下。您通常无法将执行年数与任何大 O 符号相关联。例如。没有办法说 20 年的执行 = O(n^87) 或其他任何与此相关的内容。即使在您提供的算法中，我也可以将 TwentyYearsFromNow 更改为 20110 年、75699436 或 123456789 并且 big-O 仍然是 O(n)。
big-O 相对于什么？
您似乎凭直觉认为 twentyYearsLater 是一个 "input"。如果您确实将函数写为
void helloWorld(int years) {
// ...
}
这将是 O(N)，其中 N = 年（或者只说 O(years)）。
我会说你的算法是 O(N) 相对于你在以 twentyYearsLater = 开头的代码行中碰巧写的任何数字。但是人们通常不会将实际源代码中的数字视为输入。他们可能会将命令行输入视为输入，或将函数签名输入视为输入，但很可能不是源代码本身。这就是您与朋友争论的问题 - 这是 "input" 吗？您以某种方式设置您的代码，使其在直觉上看起来像一个输入，并且您绝对可以在程序的第 6 行就数字 N 询问它的大 O 运行 时间，但是如果您使用这样的非默认选择作为输入，您确实需要对其进行明确说明。
但是如果你把输入当作更普通的东西，比如命令行或函数的输入，那么根本就没有输出，函数是 O(1) 的。需要二十年，但由于big-O不会变化到常数倍，所以O(1) = O(tenty years).
类似问题 - 什么是运行时间：
void sortArrayOfSizeTenMillion(int[] array)
假设它按照它说的去做并且输入有效，并且该算法利用快速排序或冒泡排序或任何合理的算法，它是 O(1)。
虽然这里有很多很好的答案，但让我稍微改一下。
Big-O 符号用于描述函数。当应用于算法分析时，这需要我们首先根据 函数 定义该算法的某些特征。常见的选择是将 步数 视为 输入大小 的函数。如其他答案所述，在您的案例中提出这样的功能似乎很奇怪，因为没有明确定义 "input"。不过，我们仍然可以尝试这样做：
- 我们可以将您的算法视为一个常量函数，它接受任何大小的任何输入，忽略它，等待一段固定的时间，然后完成。在这种情况下，它的 运行time 是 f(n) = const，并且它是一个 O(1)-time 算法。这是你希望听到的，对吧？ 是的，从技术上讲，它是一个 O(1) 算法。
- 我们可以将
TwentyYearsLater 视为感兴趣的类似 "input-size" 的参数。在这种情况下，运行时间是 f(n) = (n-x) 其中 x 是 "now time" 在调用的时刻。这样看，它是一个 O(n) 时间算法。每当你向其他人展示你的技术上 O(1)-算法 时，都期待这种反驳。
- 哦，等等，如果 k=
TwentyYearsLater 是输入，那么它的 size n 实际上是表示它所需的位数，即 n = log(k)。因此，输入大小 n 和 运行 之间的依赖关系是 f(n) = 2^n - x。好像你的算法刚刚变得指数级慢！ 呃
- 程序的另一个输入实际上是 答案流 由 OS 给循环中的
DateTime.Now 调用序列。我们实际上可以想象，在我们 运行 程序的那一刻，整个序列作为输入提供。然后可以认为 运行 时间取决于此序列的 属性 - 即它的长度，直到第一个 TwentyYearsLater 元素。在这种情况下，运行时间又是f(n) = n，算法是O(n).
但话又说回来，在你的问题中你甚至没有说你对 运行时间感兴趣。如果你的意思是内存使用怎么办？根据您对情况建模的方式，您可以说该算法是 O(1)-内存，或者也许是 O(n)-内存（如果 DateTime.Now 的实现需要以某种方式跟踪整个调用序列） .
如果你的目标是想出一些荒谬的东西，你为什么不全力以赴并说你对屏幕上算法代码的大小（以像素为单位）如何取决于所选的缩放级别感兴趣.这可能类似于 f(zoom) = 1/zoom 你可以自豪地声明你的算法是 O(1/n)-pixel尺码！
不，您的代码的时间复杂度为 O(2^|<DeltaTime>|)、
当前时间的正确编码。
请让我先为我的英语道歉。
Big O 在 CS 中是什么以及如何工作
大 O 表示法 不用于将程序的输入与其 运行 宁时间 联系起来。
大 O 表示法是一种表达两个量 .
的 渐近比的方法，将严谨性抛在脑后
在算法分析的情况下，这两个量是不是输入（为此必须首先具有“测量”功能）和运行宁时间.
它们是问题实例的编码长度1和一个感兴趣的度量。
常用指标有
- 在给定的计算模型中完成算法所需的步骤数。
- 计算模型要求 space（如果存在任何此类概念）。
隐式假设一个 TM 作为模型，以便第一个点转换为转换2函数的应用次数，即“步数”，第二个转换 至少写入一次的不同磁带单元的数量 。
是否也经常隐含地假设我们可以使用多项式相关编码而不是原始编码，例如从头到尾搜索数组的函数具有 O(n) 复杂度，尽管编码是此类数组实例的长度应为 n*b+(n-1)，其中 b 是每个元素的（常数）符号数。这是因为 b 被认为是计算模型的常数，因此上面的表达式和 n 渐近相同。
这也解释了为什么像 Trial Division 这样的算法是 指数级 算法，尽管本质上是 for(i=2; i<=sqr(N); i++) 算法 3.
参见 this。
这也意味着大 O 表示法可能会使用描述问题所需的尽可能多的参数，对于某些算法来说使用 k 参数并不罕见。
所以这不是关于“输入”或“没有输入”的。
现在学习案例
大 O 表示法不会质疑您的算法，它只是假设您知道自己在做什么。它本质上是一种适用于任何地方的工具，甚至适用于可能故意棘手的算法（如您的算法）。
为了解决您的问题，您使用了当前日期和未来日期，因此它们一定是问题的一部分；简单地说：它们是问题实例的一部分。
具体实例为：
<DeltaTime>
其中 <> 表示选择的任何非病态编码。
请参阅下面的非常重要 说明。
所以你的大 O 复杂度时间只是 O(2^|<DeltaTime>|)，因为你进行了多次迭代，这取决于当前时间的值。
放置其他数字常量没有意义，因为渐近符号很有用，因为它消除了常量（因此例如 O(10^|<DeltaTime>|*any_time_unit) 的使用毫无意义）。
棘手的部分在哪里
我们在上面做了一个重要的假设：计算模型具体化了5 时间，我所说的时间是指（真实的？）物理时间。
标准计算模型中没有这样的概念，TM不知道时间，我们link用步数计算时间因为这就是我们现实中的工作方式4.
在您的模型中，但是时间是计算的一部分，您可以使用功能人员的术语说 Main 不是纯粹的，但概念是相同的。
要理解这一点，应该注意没有什么可以阻止框架使用假时间，该假时间 运行 比物理时间快两倍、五倍、十倍。这样你的代码将运行在“时间”的“一半”、“五分之一”、“十分之一”中。
这个反射对于选择<DeltaTime>的编码很重要，这本质上是一种浓缩的写法<(CurrentTime, TimeInFuture)>。
由于修道院不存在时间，因此 CurrentTime 的编码很可能是单词 Now（或任何其他选择），前一天可以编码为 Yesterday，打破了编码长度增加随着物理时间前进的假设（DeltaTime之一减少）
为了做一些有用的事情，我们必须在我们的计算模型中正确地建模时间。
我们可以做的唯一安全选择是随着物理时间的增加对时间戳进行编码（但仍然不使用一元）。这是我们需要的唯一真实 属性 时间，也是编码需要捕捉的时间。
是不是只有这种类型的编码，你的算法才有时间复杂度。
你的困惑，如果有的话，是因为 time 在短语 'What is its time complexity?' 和 'How much time will it take?' 中的意思是非常非常不同的东西
唉，术语使用相同的词，但你可以尝试在脑海中使用“步骤复杂性”并重新问自己你的问题，我希望能帮助你理解答案真的是^_^
1 这也解释了渐近方法的必要性，因为每个实例都有不同但不是任意的长度。
2希望我在这里使用的是正确的英文术语。
3 这也是为什么我们经常在数学中找到 log(log(n)) 个术语。
4据我所知，一个步骤必须占用一些有限的，但不是空的，也不是未连接的时间间隔。
5 这意味着计算模式作为一种物理时间的知识在其中，即可以用它的术语来表达它。类比是泛型在 .NET 框架中的工作方式。
令我惊讶的一件事还没有被提及：大 O 符号是一个上限！
大家都注意到的问题是没有N描述算法的输入，所以没有什么可以做big-O分析的。然而，这很容易通过一些基本的技巧来缓解，例如接受 int n 并打印 "Hello World" n 次。这将解决那个抱怨并回到真正的问题，即 DateTime 怪物是如何工作的。
并不能真正保证 while 循环永远终止。我们喜欢认为它必须在 一些 时间，但考虑 DateTime.now returns 系统日期和时间 。实际上并不能保证这是单调递增的。可能有一些受过病态训练的猴子不断将系统日期和时间更改回 2015 年 10 月 21 日 12:00:00 UTC，直到有人给猴子一些自动合脚的鞋子和悬浮滑板。这个循环实际上可以 运行 无限长！
当你真正深入研究大 O 符号的数学定义时，它们是上界。他们展示了最坏的情况，无论多么不可能。这里最坏的情况*是无限 运行 时间，因此我们不得不声明 没有大 O 符号来描述此算法的 运行 时间复杂度。它不存在，就像1/0不存在一样。
* 编辑：根据我与 KT 的讨论，假设我们使用大 O 符号建模的场景是最坏的情况并不总是有效。在大多数情况下，如果某人未能指定我们使用的是哪种情况，他们打算探索最坏的情况。但是，您可以对最佳情况 运行 时间进行大 O 复杂性分析。
每个人都正确地指出你没有定义N，但在最合理的解释下答案是否定的。如果 N 是我们正在打印的字符串的长度，“hello, world!”只是一个例子，正如我们可以从对这个算法的描述中推断出“for hello, world!”，那么该算法是 O(N)，因为你可能有一个输出字符串需要三十、四十或五十年才能打印出来，而你只是在其中添加了一个常数时间。 O(kN+c) ∈ O(N).
附录：
令我惊讶的是，有人对此提出异议。回想大 O 和大 Θ 的定义。假设我们有一个算法等待固定的时间 c，然后在线性时间内打印出一条长度为 N 的消息。 （这是对原始代码示例的概括。）我们武断地说，我们等了 20 年才开始打印，而打印一万亿个字符又需要 20 年。例如，让 c = 20 和 k = 10¹²，但任何正实数都可以。这是 d = c/k（在本例中为 2×10⁻¹¹）年的比率每个字符，所以我们的执行时间 f(N) 是渐近的 dN+ c 年。每当 N > k, dN = c/k N > c。因此，dN < dN+c = f( N) < 2 dN 所有 N > k , 和 f(N) ∈ Θ(N). Q.E.D.
这个 "algorithm" 被正确描述为 O(1) 或常数时间。有人认为这个程序没有输入，因此没有 N 可以根据 Big Oh 进行分析。我不同意没有输入。当它被编译成可执行文件并被调用时，用户可以指定任意长度的任何输入。该输入长度是 N.
程序只是忽略输入（无论长度如何），因此无论输入的长度如何，所花费的时间（或执行的机器指令数）都是相同的（给定固定环境=开始时间+硬件） ，因此 O(1).
大多数人似乎都忽略了两件非常重要的事情。
程序 有输入。它是硬编码的 date/time
系统时间与之进行比较。输入由人 运行 算法控制，而系统时间则不然。这个程序 运行 人唯一可以控制的是 date/time 他们硬编码到比较中。
程序会根据输入值而变化，但不会根据输入set的大小而变化，即什么是大 O 符号。
因此，它是不确定的，这个程序最好的 'big-O' 表示法可能是 O(null)，或者可能是 O(NaN)。
在这个时间点，是的
该算法有一个隐式输入，即程序启动的时间。执行时间将线性变化1取决于在它启动时。 2035年以后，while循环立即退出，程序在不断的运算2后终止。所以可以说运行时间是O(max(2035 - start year, 1))3。但是由于我们的开始年份有一个最小值，所以该算法的执行时间永远不会超过 20 年（即恒定值）。
您可以通过定义 DateTime TwentyYearsLater = DateTime.Now + new TimeSpan(365*20,0,0,0);4
使您的算法更符合您的意图
1 这适用于更技术意义上的以操作数衡量的执行时间，因为每个时间单位有最大操作数。
2假设取DateTime.Now是常量操作，这是合理的
3 我在这里有点滥用大 O 符号，因为这是相对于 start year 的递减函数，但我们可以通过用 [=14] 表示来轻松纠正这个问题=].
4 那么算法不再依赖于开始时间的隐式输入，但这没有任何影响。
复杂性用于根据 time/space 来衡量计算 "horsepower"。大 O 表示法用于比较哪些问题是 "computable" 或 "not computable"，也用于比较哪些解决方案 - 算法 - 优于其他解决方案。因此，您可以将任何算法分为两类：可以在多项式时间内求解的算法和不能求解的算法。
诸如埃拉托斯汀筛之类的问题是 O(n ^exp)，因此对于较小的 n 值是可以解决的。它们是可计算的，只是不在多项式时间 (NP) 中，因此当被问及给定数字是否为素数时，答案 取决于 该数字的大小。此外，复杂性不取决于硬件，因此拥有更快的计算机不会改变任何事情...
Hello World 不是一种算法，因此尝试确定其复杂性是毫无意义的 - 即 none。一个简单的算法可以是这样的：给定一个随机数，确定它是偶数还是奇数。现在，给定数字有 500 位是否重要？不，因为您只需要检查最后一位数字是偶数还是奇数。一个更复杂的算法是确定一个给定的数字是否能被 3 整除。虽然有些数字需要 "easy" 来计算，但其他的需要 "hard"，这是因为它的大小：比较它花费的时间确定一个数字与 500 位数字之间的余数。
更复杂的情况是解码文本。你有一个明显的随机符号阵列，你也知道这些符号正在为那些拥有解密密钥的人传达信息。假设发件人使用左侧的键，您的 Hello World 将显示为：Gwkki Qieks。 "big-hammer, no-brain" 解决方案将生成这些字母的所有组合：从 Aaaa 到 Zzzz，然后搜索字典以确定哪些词有效，并在相同位置共享密码 (i, k) 中的两个常用字母。这个变换函数就是大O测的！
我认为人们被抛弃是因为代码看起来不像传统算法。这是格式更正确的代码翻译，但忠实于 OP 问题的精神。
void TrolloWorld(long currentUnixTime, long loopsPerMs){
long laterUnixTime = 2051222400000; //unix time of 01/01/2035, 00:00:00
long numLoops = (laterUnixTime-currentUnixTime)*loopsPerMs;
for (long i=0; i<numLoops; i++){
print ("It's still not time to print the hello …");
}
print("Hello, World!");
}
输入是显式的，而在代码启动时和硬件速度 运行 代码中隐式给出输入之前。该代码是确定性的，并且对于给定的输入具有明确定义的输出。
由于我们可以提供的输入受到限制，将执行的操作数存在上限，因此该算法实际上是 O(1)。
我认为这是 O(n)。
使用 http://www.cforcoding.com/2009/07/plain-english-explanation-of-big-o.html 作为参考。
What is Big O?
Big O notation seeks to describe the relative complexity of an
algorithm by reducing the growth rate to the key factors when the key
factor tends towards infinity.
和
The best example of Big-O I can think of is doing arithmetic. The basic arithmetic operations we learnt
in school were:
addition; subtraction; multiplication; and division. Each of these is
an operation or a problem. A method of solving these is called an
algorithm.
以你的例子为例，
给定 n = 20（单位为年）的输入。
该算法是一个数学函数 f()。其中 f() 恰好等待 n 年，中间有 'debug' 个字符串。比例因子为 1。f() 可以通过更改此比例因子 reduced/or 增加。
对于这种情况，输出也是 20（改变输入会线性改变输出）。
本质上的功能是
f(n) = n*1 = n
if n = 20, then
f(20) = 20
这会被归类为 "Hello, World!" 的 O(1) 算法吗？？
public class Hello1
{
public static void Main()
{
DateTime TwentyYearsLater = new DateTime(2035,01,01);
while ( DateTime.Now < TwentyYearsLater )
{
System.Console.WriteLine("It's still not time to print the hello ...");
}
System.Console.WriteLine("Hello, World!");
}
}
我正在考虑使用
DateTime TwentyYearsLater = new DateTime(2035,01,01);
while ( DateTime.Now < TwentyYearsLater )
{
// ...
}
代码片段作为一个繁忙的循环，当有人要求某种复杂性的算法时作为一个笑话。这是正确的吗？
此上下文中的大 O 表示法用于描述函数输入的大小与计算该输入的结果需要执行的操作数之间的关系。
您的操作没有与输出相关的输入，因此使用大 O 表示法是荒谬的。该操作花费的时间是 独立于 的操作输入（即...none）。由于输入和执行的操作数之间没有关系，你不能用Big O来描述不存在的关系
Big-O 表示法大致表示 'given an operation on an amount of work, N, how much calculation time, proportional to N, does the algorithm take?'。例如，对大小为 N 的数组进行排序可以采用 N^2、Nlog(N) 等
这没有任何输入数据可供操作。所以不是 O(anything).
更糟；这在技术上不是算法。算法是一种计算数学函数值的方法——数学函数是从一个输入到输出的映射。由于这不需要任何输入并且 returns 什么也没有，所以它不是数学意义上的函数。来自维基百科：
An algorithm is an effective method that can be expressed within a finite amount of space and time and in a well-defined formal language for calculating a function. Starting from an initial state and initial input (perhaps empty), the instructions describe a computation that, when executed, proceeds through a finite number of well-defined successive states, eventually producing "output" and terminating at a final ending state.
从技术上讲，这是一个控制系统。来自维基百科；
A control system is a device, or set of devices, that manages, commands, directs or regulates the behavior of other devices or systems.
如果人们想要更深入地了解数学函数和算法之间的区别，以及计算机更强大的处理控制台输出、显示图形或控制机器人等副作用的能力，请 read of this paper on the Strong Church-Turing Hypothesis
摘要
The classical view of computing positions computation as a closed-box transformation of inputs (rational numbers or finite strings) to outputs. According to the interactive view of computing, computation is an ongoing interactive process rather than a function-based transformation of an input to an output. Specifically, communication with the outside world happens during the computation, not before or after it. This approach radically changes our understanding of what is computation and how it is modeled.
The acceptance of interaction as a new paradigm is hindered by the Strong Church-Turing Thesis (SCT), the widespread belief that Turing Machines (TMs) capture all computation, so models of computation more expressive than TMs are impossible. In this paper, we show that SCT reinterprets the original Church-Turing Thesis (CTT) in a way that Turing never intended; its commonly assumed equivalence to the original is a myth. We identify and analyze the historical reasons for the widespread belief in SCT. Only by accepting that it is false can we begin to adopt interaction as an alternative paradigm of computation
Big-O 分析处理涉及的处理量，因为正在处理的数据量无限制地增加。
在这里，您实际上只处理一个固定大小的对象。因此，应用大 O 分析在很大程度上（主要是？）取决于您如何定义术语。
例如，您可能指的是一般打印输出，并强制等待很长时间，以便在完全相同的时间段内打印任何合理数量的数据 would/will。您还必须以一些不寻常的（如果不是完全错误的）定义的方式添加更多内容才能走得更远——特别是，大 O 分析 通常 定义为执行特定任务所需的基本操作的数量（但请注意，复杂性也可以从内存使用等方面考虑，而不仅仅是 CPU use/operations 执行）。
然而，基本操作的数量通常与所花费的时间相当接近，因此将两者视为同义词并不过分。然而，不幸的是，我们仍然坚持另一部分：正在处理的数据量无限制地增加。既然如此，你施加的任何固定延迟都不会真正奏效。要将 O(1) 等同于 O(N)，您必须施加无限延迟，以便任何固定数量的数据都需要永远打印，就像无限量的数据一样。
我有点不同意Servy。这个程序有一个输入，即使它不明显，那就是系统的时间。这可能是您意想不到的技术问题，但您的 TwentyYearsFromNow 变量距离 系统现在的时间 不到二十年，它被静态分配到 2035 年 1 月 1 日。
因此，如果您使用此代码并在系统时间为 1970 年 1 月 1 日的机器上执行它，则无论计算机有多快（可能会有一些差异），都需要 65 年才能完成如果它的时钟有故障）。如果您使用此代码并在系统时间为 2035 年 1 月 2 日的机器上执行它，它将几乎立即完成。
我会说你的输入 n 是 January 1st, 2035 - DateTime.Now，并且是 O(n)。
然后还有操作次数的问题。有些人注意到更快的计算机会更快地进入循环，从而导致更多的操作，但这无关紧要。使用大 O 表示法时，我们不考虑处理器的速度或确切的操作数。如果您采用此算法并在计算机上 运行 它，然后再次 运行 它但在同一台计算机上运行 10 倍的时间，您会期望操作数以 10 倍的相同因子增长。
至于这个：
I'm thinking of using the [redacted code] snippet of code as a busy loop to put in as a joke whenever someone asks for an algorithm of a certain complexity. Would this be correct?
不，不是真的。其他答案已经涵盖了这一点，所以我只是想提一下。您通常无法将执行年数与任何大 O 符号相关联。例如。没有办法说 20 年的执行 = O(n^87) 或其他任何与此相关的内容。即使在您提供的算法中，我也可以将 TwentyYearsFromNow 更改为 20110 年、75699436 或 123456789 并且 big-O 仍然是 O(n)。
big-O 相对于什么？
您似乎凭直觉认为 twentyYearsLater 是一个 "input"。如果您确实将函数写为
void helloWorld(int years) {
// ...
}
这将是 O(N)，其中 N = 年（或者只说 O(years)）。
我会说你的算法是 O(N) 相对于你在以 twentyYearsLater = 开头的代码行中碰巧写的任何数字。但是人们通常不会将实际源代码中的数字视为输入。他们可能会将命令行输入视为输入，或将函数签名输入视为输入，但很可能不是源代码本身。这就是您与朋友争论的问题 - 这是 "input" 吗？您以某种方式设置您的代码，使其在直觉上看起来像一个输入，并且您绝对可以在程序的第 6 行就数字 N 询问它的大 O 运行 时间，但是如果您使用这样的非默认选择作为输入，您确实需要对其进行明确说明。
但是如果你把输入当作更普通的东西，比如命令行或函数的输入，那么根本就没有输出，函数是 O(1) 的。需要二十年，但由于big-O不会变化到常数倍，所以O(1) = O(tenty years).
类似问题 - 什么是运行时间：
void sortArrayOfSizeTenMillion(int[] array)
假设它按照它说的去做并且输入有效，并且该算法利用快速排序或冒泡排序或任何合理的算法，它是 O(1)。
虽然这里有很多很好的答案，但让我稍微改一下。
Big-O 符号用于描述函数。当应用于算法分析时，这需要我们首先根据 函数 定义该算法的某些特征。常见的选择是将 步数 视为 输入大小 的函数。如其他答案所述，在您的案例中提出这样的功能似乎很奇怪，因为没有明确定义 "input"。不过，我们仍然可以尝试这样做：
- 我们可以将您的算法视为一个常量函数，它接受任何大小的任何输入，忽略它，等待一段固定的时间，然后完成。在这种情况下，它的 运行time 是 f(n) = const，并且它是一个 O(1)-time 算法。这是你希望听到的，对吧？ 是的，从技术上讲，它是一个 O(1) 算法。
- 我们可以将
TwentyYearsLater视为感兴趣的类似 "input-size" 的参数。在这种情况下，运行时间是 f(n) = (n-x) 其中 x 是 "now time" 在调用的时刻。这样看，它是一个 O(n) 时间算法。每当你向其他人展示你的技术上 O(1)-算法 时，都期待这种反驳。 - 哦，等等，如果 k=
TwentyYearsLater是输入，那么它的 size n 实际上是表示它所需的位数，即 n = log(k)。因此，输入大小 n 和 运行 之间的依赖关系是 f(n) = 2^n - x。好像你的算法刚刚变得指数级慢！ 呃 - 程序的另一个输入实际上是 答案流 由 OS 给循环中的
DateTime.Now调用序列。我们实际上可以想象，在我们 运行 程序的那一刻，整个序列作为输入提供。然后可以认为 运行 时间取决于此序列的 属性 - 即它的长度，直到第一个TwentyYearsLater元素。在这种情况下，运行时间又是f(n) = n，算法是O(n).
但话又说回来，在你的问题中你甚至没有说你对 运行时间感兴趣。如果你的意思是内存使用怎么办？根据您对情况建模的方式，您可以说该算法是 O(1)-内存，或者也许是 O(n)-内存（如果 DateTime.Now 的实现需要以某种方式跟踪整个调用序列） .
如果你的目标是想出一些荒谬的东西，你为什么不全力以赴并说你对屏幕上算法代码的大小（以像素为单位）如何取决于所选的缩放级别感兴趣.这可能类似于 f(zoom) = 1/zoom 你可以自豪地声明你的算法是 O(1/n)-pixel尺码！
不，您的代码的时间复杂度为 O(2^|<DeltaTime>|)、
当前时间的正确编码。
请让我先为我的英语道歉。
Big O 在 CS 中是什么以及如何工作
大 O 表示法 不用于将程序的输入与其 运行 宁时间 联系起来。
大 O 表示法是一种表达两个量 .
在算法分析的情况下，这两个量是不是输入（为此必须首先具有“测量”功能）和运行宁时间.
它们是问题实例的编码长度1和一个感兴趣的度量。
常用指标有
- 在给定的计算模型中完成算法所需的步骤数。
- 计算模型要求 space（如果存在任何此类概念）。
隐式假设一个 TM 作为模型，以便第一个点转换为转换2函数的应用次数，即“步数”，第二个转换 至少写入一次的不同磁带单元的数量 。
是否也经常隐含地假设我们可以使用多项式相关编码而不是原始编码，例如从头到尾搜索数组的函数具有 O(n) 复杂度，尽管编码是此类数组实例的长度应为 n*b+(n-1)，其中 b 是每个元素的（常数）符号数。这是因为 b 被认为是计算模型的常数，因此上面的表达式和 n 渐近相同。
这也解释了为什么像 Trial Division 这样的算法是 指数级 算法，尽管本质上是 for(i=2; i<=sqr(N); i++) 算法 3.
参见 this。
这也意味着大 O 表示法可能会使用描述问题所需的尽可能多的参数，对于某些算法来说使用 k 参数并不罕见。
所以这不是关于“输入”或“没有输入”的。
现在学习案例
大 O 表示法不会质疑您的算法，它只是假设您知道自己在做什么。它本质上是一种适用于任何地方的工具，甚至适用于可能故意棘手的算法（如您的算法）。
为了解决您的问题，您使用了当前日期和未来日期，因此它们一定是问题的一部分；简单地说：它们是问题实例的一部分。
具体实例为：
<DeltaTime>
其中 <> 表示选择的任何非病态编码。
请参阅下面的非常重要 说明。
所以你的大 O 复杂度时间只是 O(2^|<DeltaTime>|)，因为你进行了多次迭代，这取决于当前时间的值。
放置其他数字常量没有意义，因为渐近符号很有用，因为它消除了常量（因此例如 O(10^|<DeltaTime>|*any_time_unit) 的使用毫无意义）。
棘手的部分在哪里
我们在上面做了一个重要的假设：计算模型具体化了5 时间，我所说的时间是指（真实的？）物理时间。 标准计算模型中没有这样的概念，TM不知道时间，我们link用步数计算时间因为这就是我们现实中的工作方式4.
在您的模型中，但是时间是计算的一部分，您可以使用功能人员的术语说 Main 不是纯粹的，但概念是相同的。
要理解这一点，应该注意没有什么可以阻止框架使用假时间，该假时间 运行 比物理时间快两倍、五倍、十倍。这样你的代码将运行在“时间”的“一半”、“五分之一”、“十分之一”中。
这个反射对于选择<DeltaTime>的编码很重要，这本质上是一种浓缩的写法<(CurrentTime, TimeInFuture)>。
由于修道院不存在时间，因此 CurrentTime 的编码很可能是单词 Now（或任何其他选择），前一天可以编码为 Yesterday，打破了编码长度增加随着物理时间前进的假设（DeltaTime之一减少）
为了做一些有用的事情，我们必须在我们的计算模型中正确地建模时间。
我们可以做的唯一安全选择是随着物理时间的增加对时间戳进行编码（但仍然不使用一元）。这是我们需要的唯一真实 属性 时间，也是编码需要捕捉的时间。 是不是只有这种类型的编码，你的算法才有时间复杂度。
你的困惑，如果有的话，是因为 time 在短语 'What is its time complexity?' 和 'How much time will it take?' 中的意思是非常非常不同的东西
唉，术语使用相同的词，但你可以尝试在脑海中使用“步骤复杂性”并重新问自己你的问题，我希望能帮助你理解答案真的是^_^
1 这也解释了渐近方法的必要性，因为每个实例都有不同但不是任意的长度。
2希望我在这里使用的是正确的英文术语。
3 这也是为什么我们经常在数学中找到 log(log(n)) 个术语。
4据我所知，一个步骤必须占用一些有限的，但不是空的，也不是未连接的时间间隔。
5 这意味着计算模式作为一种物理时间的知识在其中，即可以用它的术语来表达它。类比是泛型在 .NET 框架中的工作方式。
令我惊讶的一件事还没有被提及：大 O 符号是一个上限！
大家都注意到的问题是没有N描述算法的输入，所以没有什么可以做big-O分析的。然而，这很容易通过一些基本的技巧来缓解，例如接受 int n 并打印 "Hello World" n 次。这将解决那个抱怨并回到真正的问题，即 DateTime 怪物是如何工作的。
并不能真正保证 while 循环永远终止。我们喜欢认为它必须在 一些 时间，但考虑 DateTime.now returns 系统日期和时间 。实际上并不能保证这是单调递增的。可能有一些受过病态训练的猴子不断将系统日期和时间更改回 2015 年 10 月 21 日 12:00:00 UTC，直到有人给猴子一些自动合脚的鞋子和悬浮滑板。这个循环实际上可以 运行 无限长！
当你真正深入研究大 O 符号的数学定义时，它们是上界。他们展示了最坏的情况，无论多么不可能。这里最坏的情况*是无限 运行 时间，因此我们不得不声明 没有大 O 符号来描述此算法的 运行 时间复杂度。它不存在，就像1/0不存在一样。
* 编辑：根据我与 KT 的讨论，假设我们使用大 O 符号建模的场景是最坏的情况并不总是有效。在大多数情况下，如果某人未能指定我们使用的是哪种情况，他们打算探索最坏的情况。但是，您可以对最佳情况 运行 时间进行大 O 复杂性分析。
每个人都正确地指出你没有定义N，但在最合理的解释下答案是否定的。如果 N 是我们正在打印的字符串的长度，“hello, world!”只是一个例子，正如我们可以从对这个算法的描述中推断出“for hello, world!”，那么该算法是 O(N)，因为你可能有一个输出字符串需要三十、四十或五十年才能打印出来，而你只是在其中添加了一个常数时间。 O(kN+c) ∈ O(N).
附录：
令我惊讶的是，有人对此提出异议。回想大 O 和大 Θ 的定义。假设我们有一个算法等待固定的时间 c，然后在线性时间内打印出一条长度为 N 的消息。 （这是对原始代码示例的概括。）我们武断地说，我们等了 20 年才开始打印，而打印一万亿个字符又需要 20 年。例如，让 c = 20 和 k = 10¹²，但任何正实数都可以。这是 d = c/k（在本例中为 2×10⁻¹¹）年的比率每个字符，所以我们的执行时间 f(N) 是渐近的 dN+ c 年。每当 N > k, dN = c/k N > c。因此，dN < dN+c = f( N) < 2 dN 所有 N > k , 和 f(N) ∈ Θ(N). Q.E.D.
这个 "algorithm" 被正确描述为 O(1) 或常数时间。有人认为这个程序没有输入，因此没有 N 可以根据 Big Oh 进行分析。我不同意没有输入。当它被编译成可执行文件并被调用时，用户可以指定任意长度的任何输入。该输入长度是 N.
程序只是忽略输入（无论长度如何），因此无论输入的长度如何，所花费的时间（或执行的机器指令数）都是相同的（给定固定环境=开始时间+硬件） ，因此 O(1).
大多数人似乎都忽略了两件非常重要的事情。
程序 有输入。它是硬编码的 date/time 系统时间与之进行比较。输入由人 运行 算法控制，而系统时间则不然。这个程序 运行 人唯一可以控制的是 date/time 他们硬编码到比较中。
程序会根据输入值而变化，但不会根据输入set的大小而变化，即什么是大 O 符号。
因此，它是不确定的，这个程序最好的 'big-O' 表示法可能是 O(null)，或者可能是 O(NaN)。
在这个时间点，是的
该算法有一个隐式输入，即程序启动的时间。执行时间将线性变化1取决于在它启动时。 2035年以后，while循环立即退出，程序在不断的运算2后终止。所以可以说运行时间是O(max(2035 - start year, 1))3。但是由于我们的开始年份有一个最小值，所以该算法的执行时间永远不会超过 20 年（即恒定值）。
您可以通过定义 DateTime TwentyYearsLater = DateTime.Now + new TimeSpan(365*20,0,0,0);4
1 这适用于更技术意义上的以操作数衡量的执行时间，因为每个时间单位有最大操作数。
2假设取DateTime.Now是常量操作，这是合理的
3 我在这里有点滥用大 O 符号，因为这是相对于 start year 的递减函数，但我们可以通过用 [=14] 表示来轻松纠正这个问题=].
4 那么算法不再依赖于开始时间的隐式输入，但这没有任何影响。
复杂性用于根据 time/space 来衡量计算 "horsepower"。大 O 表示法用于比较哪些问题是 "computable" 或 "not computable"，也用于比较哪些解决方案 - 算法 - 优于其他解决方案。因此，您可以将任何算法分为两类：可以在多项式时间内求解的算法和不能求解的算法。
诸如埃拉托斯汀筛之类的问题是 O(n ^exp)，因此对于较小的 n 值是可以解决的。它们是可计算的，只是不在多项式时间 (NP) 中，因此当被问及给定数字是否为素数时，答案 取决于 该数字的大小。此外，复杂性不取决于硬件，因此拥有更快的计算机不会改变任何事情...
Hello World 不是一种算法，因此尝试确定其复杂性是毫无意义的 - 即 none。一个简单的算法可以是这样的：给定一个随机数，确定它是偶数还是奇数。现在，给定数字有 500 位是否重要？不，因为您只需要检查最后一位数字是偶数还是奇数。一个更复杂的算法是确定一个给定的数字是否能被 3 整除。虽然有些数字需要 "easy" 来计算，但其他的需要 "hard"，这是因为它的大小：比较它花费的时间确定一个数字与 500 位数字之间的余数。
更复杂的情况是解码文本。你有一个明显的随机符号阵列，你也知道这些符号正在为那些拥有解密密钥的人传达信息。假设发件人使用左侧的键，您的 Hello World 将显示为：Gwkki Qieks。 "big-hammer, no-brain" 解决方案将生成这些字母的所有组合：从 Aaaa 到 Zzzz，然后搜索字典以确定哪些词有效，并在相同位置共享密码 (i, k) 中的两个常用字母。这个变换函数就是大O测的！
我认为人们被抛弃是因为代码看起来不像传统算法。这是格式更正确的代码翻译，但忠实于 OP 问题的精神。
void TrolloWorld(long currentUnixTime, long loopsPerMs){
long laterUnixTime = 2051222400000; //unix time of 01/01/2035, 00:00:00
long numLoops = (laterUnixTime-currentUnixTime)*loopsPerMs;
for (long i=0; i<numLoops; i++){
print ("It's still not time to print the hello …");
}
print("Hello, World!");
}
输入是显式的，而在代码启动时和硬件速度 运行 代码中隐式给出输入之前。该代码是确定性的，并且对于给定的输入具有明确定义的输出。
由于我们可以提供的输入受到限制，将执行的操作数存在上限，因此该算法实际上是 O(1)。
我认为这是 O(n)。 使用 http://www.cforcoding.com/2009/07/plain-english-explanation-of-big-o.html 作为参考。
What is Big O?
Big O notation seeks to describe the relative complexity of an algorithm by reducing the growth rate to the key factors when the key factor tends towards infinity.
和
The best example of Big-O I can think of is doing arithmetic. The basic arithmetic operations we learnt in school were:
addition; subtraction; multiplication; and division. Each of these is an operation or a problem. A method of solving these is called an algorithm.
以你的例子为例，
给定 n = 20（单位为年）的输入。
该算法是一个数学函数 f()。其中 f() 恰好等待 n 年，中间有 'debug' 个字符串。比例因子为 1。f() 可以通过更改此比例因子 reduced/or 增加。
对于这种情况，输出也是 20（改变输入会线性改变输出）。
本质上的功能是
f(n) = n*1 = n
if n = 20, then
f(20) = 20