这在技术上是“ Hello World”的 O (1)算法吗？

这会被归类为“ 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 )
{
// ...
}

作为繁忙循环的代码片段，当有人询问一个具有一定复杂度的算法时，作为一个笑话放进去。这样对吗？

18242 次浏览
小开
最佳答案

Big O notation in this context is being used to describe a relationship between the size of the input of a function and the number of operations that need to be performed to compute the result for that input.

您的操作没有与输出相关的输入，因此使用大 O 符号是没有意义的。操作所花费的时间是操作输入的 独立(也就是... 无)。因为在输入和执行的操作数之间没有 是关系，所以不能使用大 O 来描述这种不存在的关系

小开

Big-O notation means roughly 'given an operation on an amount of work, N, how much calculation time, proportional to N, does the algorithm take?'. Eg, sorting an array of size N can take N^2, Nlog(N), etc.

这里没有大量的输入数据可以处理，所以它不是 O(anything)。

Even worse; this isn't technically an algorithm. An algorithm is a method for computing the value of a mathematical function -- maths functions are a mapping from one input to an output. Since this takes no input and returns nothing, it's not a function, in the mathematical sense. From wikipedia:

算法是一种有效的方法，可以在 有限的空间和时间，并在一个明确定义的形式语言 用于计算函数。从初始状态和初始状态开始 输入(也许是空的) ，指令描述一个计算, 执行时，通过有限数量的定义良好的 successive states, eventually producing "output" and terminating at a 最终结束状态最终结束状态。

从技术上讲，这是一个控制系统

A control system is a device, or set of devices, that manages, 命令、指示或规范其他设备的行为或 系统。

如果人们想要更深入地了解数学函数和算法之间的区别，以及计算机在做控制台输出、显示图形或控制机器人等副作用方面更强大的能力，可以使用 阅读这篇关于强丘奇-图灵假说的论文

摘要

计算的经典观点将计算定位为输入(有理数或有限字符串)到输出的闭盒变换。根据交互式计算的观点，计算是一个持续的交互过程，而不是一个基于函数的输入到输出的转换。具体来说，与外部世界的通信发生在计算过程中，而不是在计算之前或之后。这种方法从根本上改变了我们对什么是计算以及计算是如何建模的理解。

接受交互作为一种新的范式受到强邱奇－图灵论题(SCT)的阻碍，这种普遍的观点认为图灵机(tm)捕获了所有的计算，因此比 tm 更具表现力的计算模型是不可能的。在这篇文章中，我们展示了 SCT 以图灵从未打算过的方式重新解释了原始邱奇－图灵论题(CTT) ，它通常假定的与原始的等价性是一个神话。我们识别并分析了 SCT 广泛流行的历史原因。只有接受它是错误的，我们才能开始采用交互作为计算的另一种范式

小开

大 O 分析处理的数据处理量无限制地增加所涉及的数据处理量。

Here, you're really only dealing with a single object of fixed size. As such, applying big-O analysis depends heavily (primarily?) upon how you define your terms.

例如，您可能意味着打印输出，并强制等待如此长的时间，以至于任何合理数量的数据将/将在完全相同的时间段内打印。你还需要添加一些不同寻常(如果不是完全错误的话)的定义，以便走得更远——特别是，big-O 分析是根据执行特定任务所需的基本操作数量定义的 通常(但请注意，复杂性也可以根据内存使用来考虑，而不仅仅是 CPU 使用/执行的操作)。

然而，基本操作的数量通常与所花费的时间相当接近，因此将两者视为同义词并不是一个很大的延伸。然而，不幸的是，我们仍然受困于另一部分: 正在处理的数据量无限制地增加。在这种情况下，你可以强加的任何固定延迟都不会真正起作用。为了将 O (1)等同于 O (N) ，您必须施加一个无限延迟，以便任何固定数量的数据永远不会打印出来，就像无限数量的数据一样。

小开

我有点不同意塞维的观点。这个程序有一个输入，即使不是很明显，那就是系统的时间。这可能是一个你没有打算的技术细节，但你的 TwentyYearsFromNow变量不是从 系统时间到了二十年，它是静态分配到2035年1月1日。

因此，如果你在一台系统时间为1970年1月1日的机器上执行这段代码，那么无论计算机有多快(如果它的时钟有问题，可能会有一些变化) ，完成这段代码都需要65年的时间。如果你在一台系统时间为2035年1月2日的机器上执行这段代码，它几乎会立即完成。

我会说你的输入 n是 January 1st, 2035 - DateTime.Now是 O (n)。

然后还有一个操作数量的问题。有些人已经注意到，更快的计算机将更快地触发循环，导致更多的操作，但这是无关紧要的。当使用 big-O 表示法时，我们不考虑处理器的速度或确切的操作数。如果你用这个算法在一台计算机上运行，然后在同一台计算机上再次运行，但是运行时间延长了10倍，那么你会期望操作的数量增加10倍。

As for this:

我正在考虑使用[编校的代码]片段作为一个繁忙的循环，当有人要求一个具有一定复杂度的算法时，作为一个笑话放入。这样对吗？

不，没有。其他答案已经涵盖了这一点，所以我只想提一下。通常不能将执行年限与任何大 O 符号相关联。艾格。没有办法说20年的执行时间 = O (n ^ 87)或者其他任何东西。即使在您给出的算法中，我也可以将 TwentyYearsFromNow改为20110、75699436或123456789，而大 O 仍然是 O (n)。

小开

big-O relative to what?

你似乎直觉地认为 twentyYearsLater是一个“输入”

void helloWorld(int years) {
// ...
}

它应该是 O (N) ，其中 N = 年(或者只说 O(years))。

I would say your algorithm is O(N) relative to whatever number you happen to write in the line of code starting with twentyYearsLater =. But people do usually not consider numbers in the actual source code as the input. They might consider the command line input as the input, or the function signature input as the input, but, most likely not the source code itself. That is what you are disputing with your friend - is this the "input"? You set up your code in a way to make it intuitively seem like an input, and you can definitely ask its big O running time with respect to the number N on line 6 of your program, but if you use such a non-default choice as input you really need to be explicit about it.

但是如果将输入设置为更常见的值，如命令行或函数的输入，则根本没有输出，函数为 O (1)。它需要20年，但是因为大 O 不会变成常数倍，所以 O (1) = O (20年)。

类似的问题-什么是运行时间:

void sortArrayOfSizeTenMillion(int[] array)

假设它按照它说的做，输入是有效的，算法利用快速排序或者冒泡排序或者任何合理的东西，它就是 O (1)。

小开

Although there are a bunch of great answers here, let me rephrase all of them a bit.

存在大 O 符号来描述 functions。在应用于算法分析时，这要求我们首先根据 function定义该算法的某些特征。通常的选择是考虑 步数作为 输入大小的一个函数。正如在其他答案中指出的，在您的情况下提出这样的函数似乎很奇怪，因为没有明确定义的“输入”。尽管如此，我们仍然可以尝试这么做:

  • 我们可以把你的算法看作一个常量函数，它接受任何大小的输入，忽略它，等待固定的时间，然后完成。在这种情况下，它的运行时是 F (n) = const，它是一个 O (1)时算法。这就是你想听到的，对吧？是的，从技术上讲，它是一个 O (1)算法.
  • 我们可以将 TwentyYearsLater视为感兴趣的“类似输入大小”的参数。在这种情况下，运行时是 F (n) = (n-x)，其中 X是调用时的“现在时间”。这样看来，它是一个 O (n)时间算法。当你向别人展示你的 technically O(1)-algorithm的时候，期待这个相反的争论。
  • 哦，等等，如果 K = TwentyYearsLater是输入，那么它的 尺寸N实际上是表示它所需的位数，也就是 n = log(k)。因此，输入 N的大小和运行时之间的依赖关系是 F (n) = 2 ^ n-x。看来你的算法已经变得指数级慢了！呃。
  • 程序的另一个输入实际上是操作系统给循环中 DateTime.Now调用序列的 stream of answers。实际上，我们可以想象，在运行程序时，整个序列都被作为输入提供。然后可以认为运行时依赖于这个序列的属性-即它的长度直到第一个 TwentyYearsLater元素。在这种情况下，运行时同样是 F (n) = n，算法是 O(n)。

但是，在您的问题中，您甚至没有说您对运行时感兴趣。如果你指的是内存使用呢？根据您对情况的建模方式，您可以说算法是 O (1)-内存，或者可能是 O (n)-内存(如果 DateTime.Now的实现需要跟踪整个调用序列)。

如果你的目标是想出一些荒谬的东西，你为什么不全力以赴，说你感兴趣的是，算法代码在屏幕上的像素大小如何取决于所选择的缩放水平。这可能是像 F (缩放) = 1/缩放的东西，你可以自豪地宣布你的算法是 O (1/n)像素大小！

小开

不，你的代码的时间复杂度是 O(2^|<DeltaTime>|),

获取当前时间的正确编码。
Please, let me first apologize for my English.

大 O 在计算机科学领域是什么以及如何工作的

大 O 符号 不用于将程序的输入与其运行时间绑定。
大 O 符号是抛开严格性，表示 asymptotic ratio of two quantities的一种方法。

在算法分析的情况下，这两个量是 没有的输入(对于它，必须首先有一个“测量”函数)和运行时间。
它们是问题 1实例的编码长度和感兴趣的度量。

常用的度量标准是

  1. 在给定的计算模型中完成算法所需的步骤数。
  2. 计算模型所需要的空间，如果存在这样的概念的话。

隐式地假定 TM 作为模型，因此第一个点转换为 转换 < sup > 2 函数的应用程序数，即“步骤”，第二个点转换为 至少写入一次不同的磁带单元的数目。

是否也经常隐含地假设我们可以使用多项式相关的编码代替原始的编码，例如一个从头到尾搜索一个数组的函数具有 O(n)复杂度，尽管这样的数组实例的编码应该具有 n*b+(n-1)的长度，其中 b是每个元素的符号(常数)数。这是因为 b被认为是计算模型的常数，所以上面的表达式和 n是渐近相同的。

这也解释了为什么像 审讯科这样的算法是 指数增长算法，而本质上是像 for(i=2; i<=sqr(N); i++)这样的算法 3。

See this.

这也意味着大 O 表示法可以使用描述问题所需的任意多个参数，对于某些算法来说，使用 K参数并不罕见。

所以这个 不是关于“输入”或者那个“没有输入”。

学习案例

Big O notation doesn't question your algorithm, it just assumes that you know what you are doing. It is essentially a tool applicable everywhere, even to algorithm which may be deliberately tricky (like yours).

为了解决您的问题，您使用了当前日期和未来日期，因此它们必须以某种方式成为问题的一部分; 简单地说: 它们是问题实例的一部分。

具体的例子是:

<DeltaTime>

Where the <> means any, non pathological, coding of choice.

见下面的 非常重要澄清。

所以你的大 O 复杂度时间就是 O(2^|<DeltaTime>|)，因为你需要根据当前时间的值进行大量的迭代。 放置其他数值常量毫无意义，因为大O符号是有用的，因为它消除了常量(例如，使用 O(10^|<DeltaTime>|*any_time_unit)是没有意义的)。

最棘手的是什么

我们在上面做了一个重要的假设: 计算模型具体化了 5时间，我所说的时间是指(真实的?)物理时间。 在标准计算模型中没有这样的概念，TM 不知道时间，我们将时间与步数联系起来，因为这是我们的现实工作方式。

In your model however time is part of the computation, you may use the terminology of functional people by saying that Main is not pure but the concept is the same.

为了理解这一点，我们应该注意到，没有什么可以阻止框架使用一个比物理时间快两倍、五倍、十倍的假时间。这样，你的代码将在“一半”，“五分之一”，“十分之一”的“时间”运行。

这种反射对于选择 <DeltaTime>的编码非常重要，本质上是一种浓缩的写法 < (CurrentTime，TimeInFuture) > 。 由于时间在 priory 不存在，CurrentTime 的编码很可能是前一天的字 Now(或任何其他选择) ，可以被编码为 昨天，在那里，通过打破编码 增加的长度随着物理时间前进的假设(DeltaTime 的长度减少)

We have to properly model time in our computational model in order to do something useful.

我们可以做的唯一安全的选择是，随着物理时间的推进，用增加的长度(但仍然不使用一元)对时间戳进行编码。这是我们需要的时间的唯一真实属性，也是编码需要捕捉的属性。 只有用这种编码方式，你的算法才会有时间复杂度。

你的困惑，如果有的话，源于这样一个事实: 在短语“它的 time复杂性是什么?”？和“需要多少 time?”意味着非常不同的东西

唉，术语用的是同样的词，但是你可以尝试在脑海中使用“复杂步骤”，然后重新问自己你的问题，我希望这能帮助你理解真正的答案是 ^ _ ^

这也解释了渐近方法的必要性，因为每个实例的长度不同，但不是任意的。
我希望我在这里使用的是正确的英语术语。
这也是为什么我们经常在数学中找到 log(log(n))项的原因。
4 Id est，一个步骤必须占用一些有限的，但不为空，也不连通的时间间隔。
这意味着计算模式作为物理时间的知识，可以用它的术语来表示。类比一下泛型在。NET 架构。

小开

有一件事我很惊讶还没有被提到: big-O 符号是一个上界！

每个人都注意到的问题是，没有 N 来描述算法的输入，因此没有什么可以进行大 O 分析。然而，这很容易通过一些基本的技巧来减轻，例如接受一个 int n并打印“ Hello World”n次。这样就绕过了那个抱怨，回到了 DateTime这个怪物是如何工作的真正问题上。

实际上并不能保证 while 循环将永远终止。我们喜欢认为它必须在 一些的时间，但考虑到 DateTime.now返回的 系统日期和时间。实际上并不能保证这是单调增长的。有可能是一些经过病理训练的猴子不断地改变系统的日期和时间回到协调世界时2015年10月21日12:00:00，直到有人给猴子一些自动装配的鞋子和一个悬浮滑板。这个循环实际上可以运行无限长的时间！

当你真正深入研究大 O 符号的数学定义时，它们是上界。他们证明了最坏的情况，不管多么不可能。这里最糟糕的情况 * 场景是一个无限运行时，所以我们被迫声明 没有大 O 符号来描述这个算法的运行时复杂度。 It 不存在，就像1/0不存在一样。

* Edit: from my discussion with KT, it is not always valid to presume the scenario we are modeling with big-O notation is the worst-case. In most cases, if an individual fails to specify which case we're using, they intended to explore the worst case. However, you can do a big-O complexity analysis on the best-case runtime.

小开

每个人都正确地指出，您没有定义 N，但是根据最合理的解释，答案是否定的。如果 N是我们正在打印的字符串的长度，那么“ Hello，world!”这只是一个例子，我们可以从这个算法的描述中推断出“ for hello, world!”，那么算法是 O (N) ，因为你可能有一个输出字符串，需要30年，40年或50年来打印，你只需要增加一个常量的时间。O (KN + c)∈ O (N)。

附录:

To my surprise, someone is disputing this. Recall the definitions of big O and big Θ. Assume we have an algorithm that waits for a constant amount of time C and then prints out a message of length N in linear time. (This is a generalization of the original code sample.) Let’s arbitrarily say that we wait twenty years to start printing, and that printing a trillion characters takes another twenty years. Let C = 20 and K = 10¹², for example, but any positive real numbers will do. That’s a rate of D = C/K (in this case 2×10⁻¹¹) years per character, so our execution time F(N) is asymptotically DN+C years. Whenever N > K, DN = C/K N > C. Therefore, DN < DN+C = F(N) < 2 DN for all N > K, and F(N) ∈ Θ(N). C9

小开

这个“算法”被正确地描述为 O (1)或常数时间。有人认为，这个程序没有输入，因此没有 N 可以用大欧来分析。我不同意没有投入。当它被编译成可执行文件并被调用时，用户可以指定任意长度的任何输入。输入长度是 N。

The program just ignores the input (of whatever length), so the time taken (or the number of machine instructions executed) is the same irrespective of the length of the input (given fixed environment = start time + hardware), hence O(1).

小开

大多数人似乎忽略了两件非常重要的事情。

  1. The program 是的 have an input. It is the hard-coded date/time 正在与系统时间进行比较的。输入由运行算法的人控制，而系统时间不受控制。运行这个程序的人唯一可以控制的是他们硬编码到比较中的日期/时间。

  2. 程序根据输入 价值而变化，但输入 set的大小不变，这正是 big-O 符号所关心的。

因此，它是不确定的，对于这个程序，最好的“ big-O”表示法可能是 O (null) ，或者可能是 O (NaN)。

小开

此时此刻，是的

该算法有一个隐式输入，即程序启动的时间。根据启动时间的不同，执行时间会有线性变化。在2035年及其后，while 循环立即退出，程序在常量操作 2之后终止。所以可以说运行时是 O(max(2035 - start year, 1))3。但是由于我们的起始年份有一个最小值，算法执行不会超过20年(即一个常数值)。

通过定义 DateTime TwentyYearsLater = DateTime.Now + new TimeSpan(365*20,0,0,0);4，可以使算法更符合您的意图

1 对于执行时间的技术意义来说，这是以操作的数量来衡量的，因为每个时间单元有最大的操作数量。
假设取 DateTime.Now是一个恒定的操作，这是合理的。
3 我在这里有点滥用大 O 符号，因为这是一个相对于 start year的递减函数，但是我们可以很容易地用 years prior to 2035来表示它。
然后算法不再依赖于开始时间的隐式输入，但这是无关紧要的。

小开

复杂性是用来衡量计算的“马力”在时间/空间方面。大 O 表示法用于比较哪些问题是“可计算的”或“不可计算的”，也用于比较哪些解决方案(算法)比其他方案更好。因此，您可以将任何算法分为两类: 可以用多项式时间求解的算法和不能用多项式时间求解的算法。

像埃氏筛这样的问题是 O (n ^ exp) ，因此对于 n 的小值是可以解决的。它们是可计算的，只不过不是在多项式时间(NP)中，因此当被问到一个给定的数字是否为素数时，答案就是这个数字的大小 看情况。此外，复杂性不依赖于硬件，因此拥有更快的计算机不会改变任何东西..。

Hello World 不是一个算法，因此试图确定它的复杂性是毫无意义的——其实根本没有复杂性。一个简单的算法可以是这样的: 给定一个随机数，判断它是偶数还是奇数。现在，给定的数字有500个数字有关系吗？不，因为你只需要检查最后一个数字是奇数还是偶数。一个更复杂的算法是确定一个给定的数字是否等于3。尽管有些数字“容易”计算，有些数字“难”计算，这是因为它的大小: 比较确定一个数字和500个数字之间的余数所需的时间。

A more complex case would be to decode a text. You have an apparent random array of symbols which you also know are conveying a message for those having the decrypting key. Let's say that the sender used the key to the left and your Hello World would read: Gwkki Qieks. The "big-hammer, no-brain" solution would produce all combinations for those letters: from Aaaa to Zzzz and then search a word dictionary to identify which words are valid and share the two common letters in the cypher (i, k) in the same position. This transformation function is what Big O measures!

小开

我认为人们之所以感到困惑，是因为代码不像传统算法那样使用 听着。这里是代码的一个翻译，它更加格式良好，但是仍然忠实于 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作为参考。

大 O 是什么？

大 O 符号试图描述一个 算法通过降低关键因子的增长速度来实现关键时的关键 因子趋向于无穷大。

还有

我能想到的关于大 O 的最好的例子就是做算术。我们学过的基本算术运算 在学校是:

addition; subtraction; multiplication; and division. Each of these is 一个操作或一个问题。解决这些问题的方法称为 算法。

For your example,

给定 n = 20的输入(以单位年为单位)。

算法是一个数学函数 f ()。其中 f ()恰好等待 n 年，中间有“ debug”字符串。比例因子是1。F ()可以通过改变这个比例因子来减少或增加。

for this case, the output is also 20 (changing the input changes the output linearly).

本质上函数是

f(n) = n*1 = n
if  n = 20, then
f(20) = 20

提交答案