是否有可能预测程序运行需要多长时间？

Question

我想知道,用任意程序做到这一点有可能吗？我听说,通过一些数学,你可以估计一个简单的算法,如排序算法,将运行多长时间; 但是更复杂的程序呢？

有一次我参观了一所大学的大型集群,该集群运行着来自世界各地的科学家的程序.当我向其中一位工程师询问他们如何安排每个程序的运行时,他说研究人员根据先前对某些程序所做的分析,通过他们的程序发送了他们需要运行多长时间的估计.以此目的.

那么,这种程序真的存在吗？如果没有,我怎样才能很好地估计我的程序的运行时间？

Answer 1

一般来说,你不能这样做,因为一般来说你无法证明一个程序会完成.这被称为暂停问题

Answer 2

你实际上是在同一时间提出一些相关的问题,而不仅仅是一个问题.

有一个程序A,当给定另一个任意程序B作为输入时,可以估计程序B运行多长时间？不,绝对不是.你甚至不能设计一个程序A来告诉你任意程序B是否会停止.

第二个版本 - 程序B将停止 - 被称为停止问题,巧妙地说,并且已经证明它不是可判定的.维基百科有一个很好的网页,而且Goedel,Escher,Bach这本书是一个非常长的,但非常对话和可读的阐述,涉及Goedel的不完全性定理,这是非常密切相关的.

http://en.wikipedia.org/wiki/Halting_problem

http://en.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach

那么,如果这是真的,那么科学家们如何得出这些估计呢？好吧,他们没有任意程序,他们有自己编写的特定程序. 有些程序是不可判定的,但不是**所有*程序都是不可判定的.因此,除非有人犯了严重错误,否则科学家们不会尝试运行他们尚未证实会停止的程序.

一旦他们证明某些程序将停止,其中一个主要的数学工具称为Big O表示法.在非常直观的层面上,Big O表示法有助于针对程序的运行时间如何随输入的大小而变化而制定缩放法则.在一个非常简单的例子中,假设你的程序是一个循环,循环需要一个任意的时间单位来运行.如果你运行循环N次,则需要N个单位的时间.但是,如果该循环本身在另一个运行N次的循环中,则整个过程需要N*N个时间单位.这两个项目的规模差别很大.(这是一个微不足道的例子,但真实的例子会变得非常复杂.)

http://en.wikipedia.org/wiki/Big_oh

这是一个相当抽象的数学工具.大O分析通常是如此抽象,以至于他们只是假设所有足够低级别的操作都需要大约"大约"相同的时间,而Big O无论如何都不会在秒,小时或天数方面给出答案.在实践中,真正的计算机也受到硬件细节的影响,例如执行某些非常低级别的操作需要多长时间,或者更糟糕的是,将信息从机器的一个部分移动到另一个部分需要多长时间,这对于多处理器计算机.因此,在实践中,Big O分析的见解与对其运行的机器的详细知识相结合,以便得出估计值.