能否预测程序运行所需时间？

Question

我想知道是否有可能使用任意程序进行这样的操作？我听说，通过一些数学方法，可以估算出简单算法的执行时间，比如排序算法，但是对于更复杂的程序呢？

我曾经参观过一所大学的一个大型集群系统，该系统运行来自世界各地科学家的程序。当我询问其中一名工程师他们是如何安排每个程序的运行时间时，他说研究人员会在他们的程序中附上预计运行时间，这是基于之前某些程序针对此目的进行分析得出的。

因此，这种程序真的存在吗？如果不存在，我该如何对我的程序进行良好的运行时间估算？

- bluewhale

---

我问这个问题是因为有时候我根本不知道我的程序需要5分钟、1小时还是1个月才能结束...当然，也因为这很有趣 :-P - bluewhale

根据对必须按顺序完成的工作和每个工作所需的运行时间的了解，您可以估计总运行时间。就自动化流程而言，计算机科学的早期证明之一是您甚至无法确定它是否会完成，更不用说需要多长时间了。 - Jerry Coffin

你的意思是在一系列输入范围内吗？那就是停机问题的一个子集。 - calebds

@JerryCoffin 那个定理是关于程序一般性的，而不是关于任何特定程序的。这意味着对于许多程序，你可以证明其是否会结束以及在何时结束，但对于某些程序则无法做到这点。只要测试其中一个“坏”程序，一切都没问题 :-) - SJuan76

@SJuan76：是的，但他的第一句话是：“我在想，是否有可能用任意程序来做到这一点？” - Jerry Coffin

好的，我可能无法对任意程序有很多了解。但是考虑到我编写了一些源代码；是否有技术可以粗略地估计执行时间呢？我的意思是，我希望能够说出类似于“这个程序大约会花费O(n^2)”的话。 - bluewhale

Answer 1

通常情况下，你无法做到这一点，因为通常你无法证明程序会完成运行。这被称为停机问题。

- andrew cooke

Answer 2

你实际上同时提出了几个相关问题，而不仅仅是一个单一的问题。

是否有一个程序A，当输入另一个任意的程序B时，能够给出Program B运行所需时间的估计？不可能。甚至无法设计出一个程序A来告诉你任意的程序B是否会停止。

第二个版本- Program B是否会停止- 被巧妙地称为停机问题，并且已经被证明它是不可判定的。维基百科有一个很好的网页，而书籍《哥德尔、艾舍尔、巴赫》则是涉及哥德尔不完备性定理的非常长但非常对话和易读的阐述，这与停机问题密切相关。

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

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

如果这是真的，那么科学家们如何得出这些估计值呢？他们没有任意的程序，而是编写了特定的程序。一些程序是不可判定的，但并非所有程序都是不可判定的。因此，除非有人犯了严重错误，否则科学家们不会尝试运行一个他们没有证明会停止的程序。

一旦他们证明了某个程序会停止，其中一个主要的数学工具就是所谓的大O符号。在非常直观的层面上，大O符号有助于开发关于程序运行时间如何随输入大小变化的缩放规律。举个非常简单的例子，假设你的程序是一个循环，每次循环需要一个任意单位的时间。如果你运行N次循环，它将需要N个单位的时间。但是，如果这个循环本身又在另一个运行N次的循环中，整个过程将需要N*N个单位的时间。这两个程序的缩放方式非常不同。（这是一个简单的例子，但实际例子可能会变得非常复杂。）

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

那是一个相当抽象的、数学工具。大 O 分析通常如此抽象，以至于它们仅假定所有足够低级别的操作需要“大约”相同的时间，而且大 O 也不会真正给出以秒、小时或天为单位的答案。在实践中，真正的计算机也受到硬件细节的影响，例如执行某些非常低级别操作需要多长时间，或者更糟糕的是，将信息从机器的一部分移动到另一部分需要多长时间，这在多处理器计算机上非常重要。因此，在实践中，从大 O 分析中获得的见解与对将运行的机器的详细了解相结合，以便得出估计值。

- Novak

Answer 3

你应该研究Big O符号。虽然它不会给出一个固定的数字，但它可以告诉你在不同规模下它的性能将如何改变。有几个简单的规则（如果你的代码在一个n次迭代的循环中，那么运行这个循环将需要n*time的时间）。

问题在于：

对于复杂的程序，有多个影响它的变量。

不考虑用户交互。

网络延迟等也是如此。

因此，这种方法适用于科学程序，在其中程序是重度计算，使用非常研究过的算法（而且许多时候只是在不同的数据集上运行相同的算法）。

- SJuan76

Answer 4

你其实无法确定。

对于一个简单的算法，你知道它是O(n)还是O(n^2)。你可以猜测它是哪一个。

然而，如果你有一个运行大量不同算法的程序，那么猜测就会变得非常困难。但是，你可以根据之前的运行结果来预测结果。

假设你最初估计程序运行一小时，但实际只运行了半小时。如果在构建/发布之间几乎没有改变，那么下一次你就知道它将在半小时左右运行。

如果你进行了根本性的更改，那么找到预计时间就会变得更加困难 :-]

- Daan Timmer