这在技术上是"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 )
{ 
   // ... 
}

代码片段作为一个繁忙的循环,当有人要求某种复杂性的算法时,它就像一个笑话.这是正确的吗？

1> Servy..：

---

此上下文中的Big O表示法用于描述函数输入大小与计算该输入结果所需执行的操作数之间的关系.

您的操作没有输出可以与输出相关,因此使用Big O表示法是没有意义的.操作所花费的时间与操作的输入无关(无...).由于是进行输入和操作的次数没有关系,你不能使用大O来描述不存在的关系

---

有人可能会争辩说系统的状态(包括时钟)是程序输入的一部分.从这个意义上讲,您可以使用日期作为输入参数,尽管不是明确的.但这很奇怪.

---

@Bergi [实际上没有[(http://stackoverflow.com/questions/34048740/is-this-technically-an-o1-algorithm-for-hello-world/34048908?noredirect=1#comment55852230_34048740),你不能只是根据您运行作业的时间来描述循环的迭代次数.当然,你将它与系统时钟可以随时由用户改变到他们想要的任何时间等事实相结合,并且你仍然没有一个良好的输入,可以准确地与一些产生输出所需的操作.哎呀,即使输出本身也不一致.

---

更清楚的是,"隐含"输入是2035年1月1日到今天之间的差异.

---

怎么样的'O(最大(1,2035年 - 年度计划开始))`

---

@Hoten但系统时间不是固定值.该函数与仅接受开始时间的"DateTime"作为输入相同*.正如我之前所说,*系统时钟可以随时间变化*.而且,您无法直接将您描述的quazi输入映射到固定输出.对于给定的开始时间,或者对于总是得到"DateTime.Now"的合理值的两个程序,没有已知的操作数量,因此您不能将这两个与时间变化相关联,因为您可以'当时间*不改变时,甚至将它们联系起来.

---

Big O描述了函数的增长率与另一函数的增长率的比较.在没有说明这两个功能是什么的情况下谈论Big O是没有意义的.OP只给出了一个函数:f(N)= 1.在OP提供第二个函数之前,问题简直是荒谬的.它甚至不是对或错,它根本没有意义,甚至连"怀特"或"错误"的问题都没有出现.

---

@scott_fakename实际上并不简单.它不仅仅是读取当前时间,而是基于此的行为.系统时间可以多次访问,以不同的间隔访问,具有不同的效果等.您不能将其视为单个输入值,甚至是集合,序列或值流.最重要的是,您无法可靠地将您获得的任何值与程序输出相关联.

---

简而言之:此*程序*不代表*算法*.例如,您无法将其转换为图灵机(那些没有实时时钟)

---

这里的问题是"功能"和"算法"这两个词具有精确的数学意义; 计算机子程序不是一回事; 人们刚刚编写了混淆这两个概念的编程语言.OP是计算机子程序,不是函数; 它没有实现算法,而是实现"等待和报告状态"控制系统.

2> Steve Cooper..：

---

Big-O表示法大致意味着'给定一个工作量的操作,N,算法需要多少计算时间,与N成比例？'.例如,对大小为N的数组进行排序可以取N ^ 2,Nlog(N)等.

这没有任何输入数据可供使用.所以事实并非如此O(anything).

更糟; 这在技术上不是算法.算法是计算数学函数值的方法 - 数学函数是从一个输入到输出的映射.由于这不需要任何输入并且不返回任何内容,因此在数学意义上它不是函数.来自维基百科:

算法是一种有效的方法,可以在有限的空间和时间内以及用于计算函数的明确定义的形式语言中表达.从初始状态和初始输入(可能是空的)开始,指令描述了一种计算,该计算在执行时通过有限数量的明确定义的连续状态,最终产生"输出"并终止于最终结束状态.

从技术上讲,这是一个控制系统.来自维基百科;

控制系统是管理,命令,指导或调节其他设备或系统的行为的设备或设备集.

对于想要更深入地回答数学函数和算法之间差异的人,以及计算机执行诸如控制台输出,显示图形或控制机器人等副作用的更强大功能,请阅读本文的内容.强大的教会 - 图灵假设

抽象

计算位置计算的经典视图是输入(有理数或有限字符串)到输出的闭箱变换.根据计算的交互式视图,计算是一个持续的交互过程,而不是输入到输出的基于功能的转换.具体而言,与外部世界的通信在计算期间发生,而不是在计算之前或之后发生.这种方法从根本上改变了我们对什么是计算以及如何建模的理解.

互动的新模式的接受是由强邱奇 - 图灵论题(SCT),人们普遍相信,图灵机(TMS)的捕获所有的计算阻碍,所以计算模型的TM相比更富有表现力是不可能的.在本文中,我们展示了SCT以图灵从未想过的方式重新解释了原始的教会 - 图灵论文(CTT); 它通常假定与原始的等价是一个神话.我们确定并分析了SCT普遍信仰的历史原因.只有接受它是假的,我们才能开始采用互动作为另一种计算范式

---

@rpax不是数学上的,没有.功能是从输入到输出的不变的转换; 例如,'square'是在输入3时始终返回9的函数.如果具有相同参数的调用始终给出相同的返回值,则c#方法只是一个数学函数.否则 - 如果它有像​​写入控制台,显示图形,分配内存这样的副作用 - 那些不是数学函数.(将添加一个链接到我的答案,在令人难以忍受的细节:))

3> Yuni Mj..：

---

不,你的代码有时间复杂度O(2^||),

为了正确编码当前时间.
请允许我先为我的英语道歉.

大O在CS中是什么以及如何运作

Big O表示法不用于将程序的输入与其运行时间联系起来.
Big O表示法是一种表达两个量的渐近比率的方法.

在算法分析的情况下,这两个量不是输入(必须首先具有"测量"功能)和运行时间.
它们是问题¹的实例的编码长度和感兴趣的度量.

常用的指标是

在给定的计算模型中完成算法所需的步骤数.

如果存在任何这样的概念,则通过计算模型所需的空间.

隐含地假设TM作为模型,使得第一点转换为转换²函数的应用数量,即"步骤",第二点转换写入至少一次的不同磁带单元的数量.

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

这也解释了为什么类似于试验分区的算法是指数算法,尽管基本上是for(i=2; i<=sqr(N); i++)类似算法³.

看到这个.

这也意味着大O表示法可能会使用尽可能多的参数来描述问题,对于某些算法来说,使用k参数并不罕见.

所以这不是关于"输入"或"没有输入".

现在研究案例

Big O表示法不会质疑您的算法,它只是假设您知道自己在做什么.它本质上是一个适用于所有地方的工具,甚至可能是故意棘手的算法(如你的).

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

具体来说,实例是:

凡<>意味着任何,非病态,编码的选择.

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

所以你的大O复杂时间就是O(2^||),因为你做了一些依赖于当前时间值的迭代.将其他数字常量放在渐近符号中O(10^||*any_time_unit)是没有意义的,因为它消除了常量(例如,使用无意义).

棘手的部分是什么

我们在上面做了一个重要的假设:计算模型需要⁵次修改,而时间我指的是(实际？)物理时间.标准计算模型中没有这样的概念,TM不知道时间,我们将时间与步数联系起来,因为这就是我们现实的工作方式⁴.

在你的模型中,时间是计算的一部分,你可以使用功能人的术语,说Main不是纯粹的,但概念是相同的.

要理解这一点,应该注意到没有什么能阻止框架使用比物理时间快两倍,五倍,十倍的假时间.这样你的代码就会在"时间"的"一半","五分之一","十分之一"中运行.

这种反射对于选择编码很重要,这实际上是编写<(CurrentTime,TimeInFuture)>的简洁方式.由于时间并不在修道院存在,CURRENTTIME的编码很可能是这个词现在(或任何其他选择)的前一天可以被编码为昨天打破的假设,那里的编码长度增加为物理时间前进(并且DeltaTime之一减少)

我们必须在我们的计算模型中正确建模时间才能做一些有用的事情.

我们唯一可以做的安全选择是对时间戳进行编码,增加长度(但仍然不使用一元)作为物理时间前进.这是我们需要的唯一真正的属性,也是编码需要捕获的属性.只有这种类型的编码才能使您的算法具有时间复杂性.

你的困惑(如果有的话)来自" 时间复杂度是多少？" 这句话中的时间这个词.并且'需要多长时间？' 意味着非常不同的东西

唉,术语使用相同的单词,但你可以尝试在脑海中使用"步骤复杂性"并重新问自己你的问题,我希望这会帮助你理解答案真的是^ _ ^

---

¹这也解释了渐近方法的必要性,因为每个实例具有不同但非任意的长度.
²我希望我在这里使用正确的英语术语.
³这也是我们经常log(log(n))在数学中找到术语的原因.
⁴ Id est,一个步骤必须占用一些有限的,但不是空的,也不是连接的,时间间隔.
⁵这意味着计算模式作为其中物理时间的知识,即可以用其术语来表达.类比是泛型如何在.NET框架中工作.

---

"所以你的大O运行时间只是"......我确定你的意思是'大O复杂'？此外,我们仍然可以将'deltaTime'称为'n'右..所以你说O(2 ^ N)类似于Fibonacci算法的复杂性.你是怎么来到"2 ^"的？

4> KT...：

---

虽然这里有很多很棒的答案,但让我稍微改写一下.

存在用于描述函数的 Big-O表示法.当应用于算法分析时,这要求我们首先根据函数定义该算法的一些特征.常见的选择是将步数作为输入大小的函数.正如其他答案所述,在你的情况下提出这样的功能似乎很奇怪,因为没有明确定义的"输入".不过,我们仍然可以尝试这样做:

我们可以将您的算法视为一个常量函数,它接受任何大小的任何输入,忽略它,等待一段固定的时间,然后完成.在这种情况下,它的运行时间是f(n)= const,它是一个O(1)时间算法.这是你期望听到的,对吗？是的,从技术上讲,它是一个O(1)算法.

我们可以将其TwentyYearsLater视为感兴趣的"输入大小"参数.在这种情况下,运行时是f(n)=(nx),其中x是调用时的"现在时间".当以这种方式看时,它是O(n)时间算法.每当你向其他人展示你的技术O(1)算法时,都会遇到这种反驳.

哦,等等,如果k =TwentyYearsLater是输入,则其大小 n实际上是表示它所需的位数,即n = log(k).因此,输入n的大小与运行时之间的依赖关系是f(n)= 2 ^ n-x.好像你的算法刚刚变得指数级慢!啊.

该程序的另一个输入实际上是OS给出的循环中调用序列的答案流DateTime.Now.我们实际上可以想象,在我们运行程序时,整个序列都是作为输入提供的.然后可以认为运行时依赖于该序列的属性 - 即它的长度直到第一个TwentyYearsLater元素.在这种情况下,运行时间再次为f(n)= n,算法为O(n).

但话说回来,在你的问题中,你甚至没有说你对运行时感兴趣.如果你的意思是内存使用怎么办 根据您对情况进行建模的方式,您可以说算法是O(1)-memory,或者也许是O(n)-memory(如果实现DateTime.Now需要跟踪整个调用序列,为什么).

如果你的目标是想出一些荒谬的东西,为什么不全力以赴,并说你对屏幕上算法代码的大小(取决于所选的缩放级别)感兴趣.这可能类似于f(缩放)= 1 /缩放,您可以自豪地将算法声明为O(1/n)像素大小!

---

这是迄今为止最好的答案 - 为了使Big O具有意义,您必须将数学语义/假设应用于物理实现(实质上是为具有有意义的"输​​入"定义的程序定义数学模型).从这个意义上说,"程序"的复杂性取决于你应用的语义 - 如果你假设N是与操作数线性成比例的时间差,它就是O(n).如果由于固定的时间段而采取固定数量的操作,则为O(1).

5> Shaz..：

---

我不得不略微不同意Servy.这个程序有一个输入,即使它不明显,这是系统的时间.这可能是您没有预期的技术性,但您的TwentyYearsFromNow变量不是系统现在的 20年,它是静态分配到2035年1月1日.

因此,如果您使用此代码并在系统时间为1970年1月1日的计算机上执行它,则无论计算机的速度有多快,都需要65年才能完成(如果计算机的时钟有问题,可能会有一些变化).如果您使用此代码并在系统时间为2035年1月2日的计算机上执行它,它几乎会立即完成.

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

然后还有操作次数的问题.有些人已经注意到更快的计算机将更快地打到循环,导致更多的操作,但这是无关紧要的.使用big-O表示法时,我们不考虑处理器的速度或操作的确切数量.如果您使用此算法并在计算机上运行它,然后再次运行它,但在同一台计算机上再运行10倍,您可能会希望操作数增加相同的10倍.

至于这个:

我正在考虑使用[编辑代码]代码片段作为忙碌循环,当有人要求某种复杂性的算法时,将其作为一个笑话.这是正确的吗？

不,不是真的.其他答案已经涵盖了这一点,所以我只是想提一下.您通常不能将执行年数与任何大O表示法相关联.例如.没有办法说20年的执行= O(n ^ 87)或其他任何事情.即使在您给出的算法中,我也可以将其更改为2 TwentyYearsFromNow0110年,75699436或123456789,而大O仍然是O(n).

---

时间不是函数的输入,它是*在整个方法执行过程中不断变化的状态*.在功能运行*时,甚至可以更改系统时钟*.要使Big O有意义,您还需要让每个输入与输出值1-1相对应,以及计算它所需的许多操作.对于这个操作,除了执行的操作数量也变化很大之外,输出对于相同的输入甚至不一致(实际上它变化很大*).

6> Jerry Coffin..：

---

Big-O分析处理所涉及的处理量,因为处理的数据量不受限制地增加.

在这里,您实际上只处理固定大小的单个对象.因此,应用大O分析在很大程度上(主要是？)取决于您如何定义术语.

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

然而,基本操作的数量通常与所花费的时间相当接近,所以这并不是一个巨大的延伸,将两者视为同义词.然而不幸的是,我们仍然坚持使用其他部分:正在处理的数据量不受限制地增加.既然如此,没有固定的延迟就可以实现.要将O(1)与O(N)等同,您必须施加无限延迟,以便永久打印任何固定数量的数据,就像无限量的数据一样.

7> djechlin..：

---

大O相对于什么？

你似乎是直觉,这twentyYearsLater是一个"输入".如果你确实写了你的函数

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

它将是O(N),其中N =年(或者说O(years)).

我会说你的算法是O(N),相对于你在代码行中开始写的任何数字twentyYearsLater =.但人们通常不会将实际源代码中的数字视为输入.他们可能会将命令行输入视为输入,或将函数签名输入视为输入,但很可能不是源代码本身.这就是你和朋友争论的问题 - 这是"输入"吗？您设置代码的方式,使其直观地看起来像一个输入,你一定可以要求它像个大O的运行时间相对于数量N对你的程序的第6行,但如果你使用这种非默认选择作为输入,你真的需要明确它.

但是如果你把输入变成更常见的东西,比如命令行或函数的输入,根本就没有输出,函数是O(1).这需要20年,但由于大O不会变为常数倍,O(1)= O(二十年).

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

void sortArrayOfSizeTenMillion(int[] array)

假设它完成它所说的并且输入有效,并且算法利用快速排序或冒泡排序或任何合理的,它是O(1).

8> waldol1..：

---

该"算法"被正确描述为O(1)或恒定时间.有人认为这个程序没有输入,因此没有N可以用Big Oh来分析.我不同意没有输入.当将其编译为可执行文件并进行调用时,用户可以指定任意长度的任何输入.输入长度是N.

程序只是忽略输入(无论长度如何),因此无论输入的长度如何(给定的固定环境=启动时间+硬件),所用的时间(或执行的机器指令数)都是相同的,因此O(1 ).

9> Cort Ammon -..：

---

有一件事我很惊讶还没有被提及:大O符号是一个上限!

每个人都注意到的问题是没有N描述算法的输入,所以没有什么可以进行大O分析.但是,这可以通过一些基本技巧轻松减轻,例如接受int n和打印"Hello World" n时间.这样可以解决这个问题,并回到真正的问题,即DateTime怪物是如何运作的.

没有实际保证while循环将终止.我们认为它必须在某个时间,但考虑DateTime.now返回系统日期和时间.实际上并不能保证这是单调增加的.有可能是一些经过病程训练的猴子不断改变系统日期和时间,直到2015年10月21日12:00:00 UTC,直到有人给猴子一些自动穿鞋和一个悬浮板.这个循环实际上可以运行无限的时间!

当你真正深入研究big-O符号的数学定义时,它们就是上界.他们展示了最糟糕的情况,无论多么不可能.这里最糟糕的情况是无限运行时,因此我们不得不声明没有大O符号来描述此算法的运行时复杂性. 它不存在,就像1/0不存在一样.

*编辑:从我与KT的讨论中,假设我们使用big-O表示法建模的场景是最坏的情况并不总是有效的.在大多数情况下,如果一个人未能指明我们正在使用哪种情况,他们打算探讨最坏的情况.但是,您可以对最佳情况运行时进行大O复杂性分析.

---

事实上,O在某种意义上是"上限",但并不意味着您只能使用O符号来说"最坏情况复杂性".预期的复杂性,最佳案例复杂性,任何其他功能属性 - 所有这些都可以根据其O界限进行讨论.

10> 小智..：

---

复杂性用于在时间/空间方面测量计算"马力".Big O表示法用于比较哪些问题是"可计算的"或"不可计算的",并且还用于比较哪些解决方案 - 算法 - 比其他解决方案更好.因此,您可以将任何算法分为两类:可以在多项式时间内求解的算法和不能在多项式时间内求解的算法.

像Erathostene的Sieve这样的问题是O(n ^ exp),因此对于小的n值是可解的.它们是可计算的,只是不在多项式时间(NP)中,因此当被问及给定数字是否为素数时,答案取决于这个数字的大小.此外,复杂性并不依赖于硬件,因此拥有更快的计算机不会改变任何东西......

Hello World不是一种算法,因此试图确定其复杂性是没有意义的 - 这是没有的.一个简单的算法可以是这样的:给定一个随机数,确定它是偶数还是奇数.现在,给定的数字有500位数是否重要？不,因为您只需检查最后一位数字是偶数还是奇数.一个更复杂的算法是确定一个给定的数字是否均匀地除以3.虽然有些数字"易于"计算,但其他数字是"硬"的,这是因为它的大小:比较确定两者之间的重复性所需的时间.一个数字,一个数字,另一个数字,500位数字.

更复杂的情况是解码文本.您有一个明显的随机数组符号,您也知道这些符号正在为具有解密密钥的人传达一条消息.假设发件人使用了左边的密钥,你的Hello World会读到:Gwkki Qieks."大锤,无脑"解决方案将为这些字母生成所有组合:从Aaaa到Zzzz,然后搜索单词字典以识别哪些单词有效并共享密码中的两个常用字母(i,k)in同样的立场.这个转换功能是Big O测量的!