这在技术上是“Hello World”的O（1）algorithm吗？

这将被分类为“你好，世界！”O（1）algorithm。 ??

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 ) { // ... } 

代码片段作为一个忙碌的循环，当有人要求一个复杂的algorithm时，把它作为一个笑话。 这是正确的吗？

Answer 1

在这种情况下，大O符号被用来描述函数input大小和计算input结果所需执行的操作数之间的关系。

您的操作没有输出可以相关的input，所以使用Big O符号是无意义的。 操作所花费的时间独立于操作的input（这是…无）。 由于input和执行的操作数量之间没有关系，因此不能使用Big O来描述不存在的关系

Answer 2

大O符号意思是大致“给予一定数量的工作的操作，N，该algorithm需要多less计算时间，与N成比例”。 例如，sorting大小为N的数组可以取N ^ 2，Nlog（N）等。

这没有任何input数据的行为。 所以这不是O(anything) 。

更糟; 这在技术上不算algorithm。 algorithm是一种计算math函数值的方法 – math函数是从一个input到一个输出的映射。 由于这不需要任何input，并且什么也不返回，所以在math意义上它不是一个函数。 从维基百科：

algorithm是一种有效的方法，可以在有限的空间和时间内以一种明确定义的forms语言来expression，以计算一个函数。 从初始状态和初始input（也许是空的）开始，指令描述了一个计算，当执行时，它通过有限数量的定义明确的连续状态，最终产生“输出”并终止于最终结束状态。

这在技术上是一个控制系统。 从维基百科

控制系统是pipe理，命令，引导或调节其他设备或系统的行为的设备或一组设备。

对于想要更深入地回答math函数和algorithm之间差异的人，以及计算机执行诸如控制台输出，显示graphics或控制机器人等副作用的更强大function，请阅读本文强大的教会图灵假设

抽象

计算位置的经典视图计算为input（有理数或有限的string）到输出的闭箱变换。 根据交互式计算的观点，计算是一个持续的交互过程，而不是input到输出的基于函数的转换。 具体而言，在计算过程中与外部世界进行沟通，而不是之前或之后。 这种方法从根本上改变了我们对什么是计算以及如何build模的理解。

交互作为一种新范式的接受受到强大的教会图灵论（SCT）的阻碍，普遍认为图灵机（TM）捕捉所有计算，所以计算模型比TM更具performance力是不可能的。 在本文中，我们展示SCT以图灵从未打算的方式重新解释原始的教会图灵论文（CTT） 它通常假设的与原文等价是一个神话。 我们确定和分析SCT普遍信仰的历史原因。 只有接受它是错误的，才能开始采取互动作为计算的替代范式

Answer 3

不，您的代码的时间复杂度为O(2^|<DeltaTime>|) ，

对于当前时间的正确编码。
请让我先为我的英语道歉。

什么是和大怎么在CS工作

大O符号不用于将程序的input与运行时间联系起来 。
大O符号是一种expression两个量的渐近比率的方法 。

在algorithm分析的情况下，这两个量不是input（为此必须首先具有“测量”function）和运行时间。
它们是问题¹实例编码的长度和感兴趣的度量。

常用的指标是

1. 在给定的计算模型中完成algorithm所需的步骤数。
2. 所需的空间，如果有任何这样的概念存在，用计算模型。

隐含地假设一个TM作为模型，以便第一点转化为转换²函数的应用程序的数量 ，即“步骤”，第二个转换至less写入一次的不同带单元的数量。

是否经常隐含地认为我们可以使用多项式相关的编码而不是原始的编码，例如，从头到尾search数组的函数具有O(n)复杂性，尽pipe这样的数组的实例的编码应该具有n*b+(n-1)长度，其中b是每个元素的（恒定）数目的符号。 这是因为b被认为是计算模型的常数，所以上面的expression式和n是渐近相同的。

这也解释了为什么一个像Trial Division这样的algorithm是一个指数algorithm，尽pipe它基本上是一个类似于algorithm³的for(i=2; i<=sqr(N); i++) 。

看到这个

这也意味着大O符号可以使用尽可能多的参数来描述问题，对于一些algorithm来说有一个k参数并不罕见。

所以这不是 “input”或“没有input”。

现在研究案例

大O符号不会质疑你的algorithm，它只是假定你知道你在做什么。 它本质上是一个适用于任何地方的工具，甚至可能是故意棘手的algorithm（如你的）。

为了解决你的问题，你使用了当前的date和未来的date，所以他们必须以某种方式成为问题的一部分。 简单地说：它们是问题实例的一部分。

具体的例子是：

<DeltaTime>

其中<>是指任何非病理性select的编码。

请参阅下面的非常重要的说明。

所以你的大O复杂度时间就是O(2^|<DeltaTime>|) ，因为你做了一些取决于当前时间值的迭代。 因为它消除了常量（所以例如使用O(10^|<DeltaTime>|*any_time_unit)是毫无意义的），所以放入其他数字常量是毫无意义的。

棘手的部分在哪里

我们在上面做了一个重要的假设：计算certificate模型certificate了⁵次，而我的意思是指（真实的）物理时间。 在标准的计算模型中没有这样的概念，TM不知道时间，我们把时间和步数联系起来，因为这是我们实际工作的方式⁴ 。

在你的模型中，时间是计算的一部分，你可以使用function人员的术语，说Main不是纯粹的，但概念是相同的。

要理解这一点，应该注意的是，没有什么能够阻止框架使用比物理时间快两倍，五倍和十倍的假时间。 这样你的代码将运行在“时间”的“一半”，“五分之一”，“十分之一”。

这个reflection对于select<DeltaTime>的编码非常重要，这实际上是写<<CurrentTime，TimeInFuture>的一种浓缩方式。 由于时间不在priory，所以CurrentTime的编码很可能是前一天（或任何其他select）的前一天可以被编码为昨天 ，通过打破编码的长度随着物理时间而增加的假设前进（而DeltaTime的减less）

我们必须在我们的计算模型中正确地build模时间，以便做一些有用的事情。

我们唯一可以做的安全的select是将时间戳长度的增加（但仍然不使用一元）作为物理时间步长。 这是我们所需要的唯一真正的时间属性，也是编码所需要的。 只有使用这种types的编码，您的algorithm才会具有时间复杂性。

如果有的话，你的困惑是由于“ 时间复杂度是多less？ 和“需要多less时间 ？” 意味着非常非常不同的东西

唉，术语使用相同的话，但你可以尝试在你的头上使用“步骤复杂性”，并重新问你自己的问题，我希望这将有助于你理解答案真的是^ _ ^

---

¹这也解释了渐近方法的需要，因为每个实例具有不同的长度，但不是任意的长度。
²我希望我在这里使用正确的英语词汇。
³这也是为什么我们经常在math中findlog(log(n))项的原因。
⁴ Id est，一个步骤必须占用一些有限的，但不是空的，也不连接的时间间隔。
⁵这意味着计算模式作为其中物理时间的知识，也就是说可以用它的术语来expression它。 类比是generics如何在.NET框架中工作。

Answer 4

虽然这里有很多很好的答案，但是让我们稍微改述一下。

存在大O符号来描述函数 。 当应用于algorithm分析时，这要求我们首先根据函数定义该algorithm的一些特征。 常见的select是考虑作为input大小的函数的步数 。 正如其他答案所指出的，在你的情况下提出这样的function似乎很奇怪，因为没有明确定义的“input”。 但是我们仍然可以尝试去做：

• 我们可以把你的algorithm看作一个常量函数，它可以接受任何大小的input，忽略它，等待一定的时间，然后结束。 在这种情况下，它的运行时间是f（n）= const ，它是一个O（1）时间algorithm。 这是你期望听到的，对吗？ 是的，在技术上它是一个O（1）algorithm 。
• 我们可以把“二TwentyYearsLater当作“input大小”一样的兴趣参数。 在这种情况下，运行时间是f（n）=（nx） ，其中x是调用时的“现在时间”。 当看到这种方式时，它是一个O（n）时间algorithm。 每当你把技术上的O（1）algorithm展示给其他人的时候，都会期待这种反驳。
• 哦，但是等一下，如果k = TwentyYearsLater是input，那么它的大小 n实际上是表示它所需的比特数，即n = log（k） 。 因此inputn和运行时间之间的依赖关系是f（n）= 2 ^ n – x 。 似乎你的algorithm已经成倍地变慢了！ 啊。
• 该程序的另一个input实际上是OS给出的循环中的DateTime.Now调用序列的stream 。 我们实际上可以想象，当我们运行程序的时候，这个整个序列是作为input提供的。 运行时可以被认为是依赖于这个序列的属性 – 也就是它的长度，直到第一个TwentyYearsLater元素。 在这种情况下，运行时间又是f（n）= n ，algorithm是O（n） 。

但是再一次，在你的问题中，你甚至没有说你对运行时感兴趣。 如果你的意思是记忆使用？ 根据你如何模拟情况，你可以说algorithm是O（1） – 内存，或者也许是O（n） – 内存（如果DateTime.Now的实现需要跟踪整个调用序列）。

如果您的目标是想出一些荒谬的东西，为什么不全力以赴，并说您对屏幕上像素的algorithm代码大小取决于所选的缩放级别感兴趣。 这可能是f（zoom）= 1 / zoom之类的东西 ，你可以自豪地声明你的algorithm是O（1 / n）像素的大小！

Answer 5

我不得不稍微反对Servy。 这个程序有一个input，即使不明显，那就是系统的时间。 这可能是你没有打算的技术性，但是你的TwentyYearsFromNowvariables不是系统现在的二十年，而是静态分配到2035年1月1日。

所以，如果你把这个代码放在一台1970年1月1日的系统上执行它，那么无论计算机有多快，它都需要65年的时间才能完成（如果它的时钟有问题，可能会有一些变化）。 如果你在2035年1月2日的系统中使用这个代码并执行它，那么它几乎可以立即完成。

我会说你的input， n是January 1st, 2035 - DateTime.Now ，它是O（n）。

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

至于这个：

我正在考虑使用[编辑代码]代码片段作为一个繁忙的循环，当有人要求一个复杂的algorithm时，把它作为一个笑话。 这是正确的吗？

不，不是。 其他答案已经涵盖了这一点，所以我只是想提到它。 一般来说，你不能将年份的执行与任何大O符号联系起来。 例如。 没有办法说20年的执行= O（N ^ 87）或其他任何事情。 即使在你给的algorithm中，我也可以把TwentyYearsFromNow年，75699436年或123456789年，而大O仍然是O（n）。

Answer 6

Big-O分析处理所处理的数据量，因为正在处理的数据量没有限制地增加。

在这里，你真的只处理一个固定大小的单个对象。 因此，应用大O分析很大程度上取决于您如何定义术语。

例如，你可能意味着打印输出一般，并且要等待很长时间才能在相同的时间内打印任何合理数量的数据。 你还必须添加一些有点不寻常的（如果不是完全错误的）定义，以获得很大的进展 – 特别是，大O分析通常是根据进行特别的任务（但要注意的是复杂性也可以考虑像内存使用，而不仅仅是CPU使用/操作）。

基本操作的数量通常与所花费的时间相当接近，然而，这并不是一个巨大的延伸，而是把两者当作同义词。 然而，不幸的是，我们仍然坚持另一部分：正在处理的数据量不受限制地增长。 既然如此，那么你可以强加的固定延迟真的会起作用。 把O（1）和O（N）等同起来，你必须施加一个无限的延迟，使得任何固定数量的数据都被永久地打印出来，就像无限的数据一样。

Answer 7

大O相对于什么？

你似乎是直觉，二twentyYearsLater是一个“投入”。 如果你真的写了你的function

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

这将是O（N）N =年（或者说O(years) ）。

我会说你的algorithm是O（N）相对于你写在twentyYearsLater =开头的代码行中的任何数字。 但是人们通常不会将实际源代码中的数字视为input。 他们可能会将命令行input视为input，或者将函数签名input视为input，但很可能不是源代码本身。 这就是你与你的朋友争吵 – 这是“input”？ 你设置你的代码的方式，使它看起来像一个input，而且你可以肯定地问你的程序的第6行的数字N的大运行时间，但如果你使用这样的非默认select作为input你真的需要明确的。

但是如果你把input作为更平常的东西，比如命令行或者函数的input，那么根本就没有输出，函数是O（1）。 这需要二十年，但由于大O不会变成一个常数倍数，O（1）= O（二十年）。

类似的问题 – 什么是运行时间：

 void sortArrayOfSizeTenMillion(int[] array) 

假设它所做的事情和input是有效的，algorithm利用快速sorting或冒泡sorting或任何合理的，它是O（1）。

Answer 8

这个“algorithm”正确地描述为O（1）或恒定时间。 有人认为，这个程序没有input，所以没有N来分析大哦。 我不同意没有任何意见。 当这被编译成可执行文件并被调用时，用户可以指定任意长度的input。 那input长度是N.

程序只是忽略input（无论长度），所以所花费的时间（或执行的机器指令的数量）是相同的，而不pipeinput的长度（给定的固定环境=开始时间+硬件），因此O（1 ）。

Answer 9

我很惊讶的一件事还没有被提及：大O符号是一个上界！

大家都注意到的问题是没有N描述algorithm的input，所以没有什么可以做大O分析。 但是，通过一些基本的技巧就可以很容易地解决这个问题，比如接受一个int n和打印“Hello World” n次。 那样可以避免这种抱怨，并回到那个DateTime怪物如何工作的真正问题上。

没有实际的保证，while循环将永远终止。 我们希望在某个时候想到它，但是请考虑DateTime.now返回系统date和时间 。 实际上不能保证这是单调递增的。 It is possible that there is some pathologically trained monkey constantly changing the system date and time back to October 21, 2015 12:00:00 UTC until someone gives the monkey some auto-fitting shoes and a hoverboard. This loop can actually run for an infinite amount of time!

When you actually dig into the mathematical definition of big-O notations, they are upper bounds. They demonstrate the worst case scenario, no matter how unlikely. The worst case* scenario here is an infinite runtime, so we are forced to declare that there is no big-O notation to describe the runtime complexity of this algorithm. It doens't exist, just as 1/0 doesn't exist.

* 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.

Answer 10

Most people seem to be missing two very important things.

1. The program does have an input. It is the hard-coded date/time against which the system time is being compared. The inputs are under the control of the person running the algorithm,and the system time is not. The only thing the person running this program can control is the date/time they've hard-coded into the comparison.

2. The program varies based on the input value , but not the size of the input set , which is what big-O notation is concerned with.

Therefore, it is indeterminate, and the best 'big-O' notation for this program would probably be O(null), or possibly O(NaN).

Answer 11

Everyone's correctly pointed out that you don't define N , but the answer is no under the most reasonable interpretation. If N is the length of the string we're printing and “hello, world!” is just an example, as we might infer from the description of this as an algorithm “for hello, world! ,” then the algorithm is O( N ), because you might have an output string that takes thirty, forty or fifty years to print, and you're adding only a constant time to that. 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 ). QED

Answer 12

Complexity is used to measure computational "horsepower" in terms of time/space. Big O notation is used to compare which problems are "computable" or "not computable" and also to compare which solutions -algorithms- are better than other. As such, you can divide any algorithm into two categories: those that can be solved in polynomial time and those that can't.

Problems like the Sieve of Erathostene are O(n ^exp) and thus are solvable for small values of n. They are computable, just not in polynomial time (NP) and thus when asked if a given number is prime or not, the answer depends on the magnitude of such number. Moreover, complexity does not depend on the hardware, so having faster computers changes nothing…

Hello World is not an algorithm and as such is senseless to attempt to determine its complexity -which is none. A simple algorithm can be something like: given a random number, determine if it is even or odd. Now, does it matter that the given number has 500 digits? No, because you just have to check if the last digit is even or odd. A more complex algorithm would be to determine if a given number divides evenly by 3. Although some numbers are "easy" to compute, others are "hard" and this is because of its magnitude: compare the time it takes to determine the remaninder between a number with one digit and other with 500 digits.

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!

Answer 13

I think people are getting thrown off because the code doesn't look like a traditional algorithm. Here is a translation of the code that is more well-formed, but stays true to the spirit of OP's question.

 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!"); } 

The inputs are explicit whereas before they were implicitly given by the time the code was started at and by the speed of the hardware running the code. The code is deterministic and has a well-defined output for given inputs.

Because of the limitations that are imposed on the inputs we can provide, there is an upper bound to the number of operations that will be executed, so this algorithm is in fact O(1).

Answer 14

At this point in time, yes

This algorithm has an implicit input, namely the time that the program is started at. The execution time will vary linearly ¹ depending on when it is started. During the year 2035 and after, the while loop immediately exits and the program terminates after constant operations ² . So it could be said that the runtime is O(max(2035 - start year, 1)) ³ . But since our start year has a minimum value, the algorithm will never take more than 20 years to execute (ie a constant value).

You can make your algorithm more in keeping with your intent by defining DateTime TwentyYearsLater = DateTime.Now + new TimeSpan(365*20,0,0,0); ⁴

¹ This holds for the more technical sense of execution time measured as number of operations because there is a maximum number of operations per time unit.
² Assuming fetching DateTime.Now is a constant operation, which is reasonable.
³ I'm somewhat abusing big O notation here because this is a decreasing function with respect to start year , but we could easily rectify this by expressing it in terms of years prior to 2035 .
⁴ Then the algorithm no longer depends on the implicit input of the start time, but that's of no consequence.

Answer 15

I'd argue that this is O(n). using http://www.cforcoding.com/2009/07/plain-english-explanation-of-big-o.html as a reference.

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.

For your example,

given the input of n = 20 (with units years).

the algorithm is a mathematical function f(). where f() happens to be wait for n years, with 'debug' strings in between. The scale factor is 1. f() can be reduced/or increased by changing this scale factor.

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

essentially the function is

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