是否可以预测程序运行需要多长时间？
我在想，是否可以用一个任意程序来做到这一点？我听说，通过一些数学，你可以估计一个简单的算法，比如排序算法需要多长时间才能运行;但更复杂的程序呢？是否可以预测程序运行需要多长时间？
有一次，我访问了一个大型集群，它负责运行来自世界各地的科学家的程序。当我问其中一位工程师如何安排每个项目的运行时间时，他表示，研究人员通过他们的项目发出了估计他们需要运行多长时间的估计，根据之前的分析，以此目的。
那么，这种程序真的存在吗？如果不是，我怎样才能很好地估计我的程序运行时间？
你不可能真的。
对于一个简单的算法，你知道是O（n）还是O（n^2）。你可以估价。然而，如果你有一个运行大量不同算法的程序，它将变得非常难以估算它。但是，你可以做什么。根据以前的运行预测结果。
如果你第一次估计yuor程序运行一个小时。它运行了半个小时。而且你在te build/releases之间的变化很小，那么下次你会知道它会在半个小时左右的时间里运行。
如果你做了根本性的变化则变得更难找到ETA： - ]
一般你不能做到这一点，因为一般你不能证明一个程序将完成在所有。这被称为halting problem
非常有趣！不知道这一点。 – bluewhale 2012-03-06 00:46:29
你应该研究大O表示法。虽然它没有给出固定的数字，但它会告诉你它的性能会随着尺寸的不同而发生变化。有一些简单的规则（如果你的代码在n次迭代的循环中，那么运行循环需要n *时间）。
问题是：
复杂的程序有影响它的多个变量。
不考虑用户交互。
同为网络延迟等
所以，这种方法适用于科学方案，其中程序是重积分，使用非常学习算法（而且很多时候它只是刚刚运行相同的算法在不同的数据集）。
你实际上是在同一时间问几个相关的问题，而不是一个单一的问题。
是否有程序A，当给定另一个任意程序B作为输入时，提供程序B运行需要多长时间的估计？不，绝对不是。你甚至不能设计一个程序A，它会告诉你程序B是否会停止。
第二个版本 - 程序B是否会暂停 - 被巧妙地称为停机问题，并且已经证明它是不可判定的。*有一个很好的网页，而且这本书很有意思，但是非常长，但却非常对话和可读，涉及与戈德尔的不完全性定理有很密切关系的想法。
http://en.wikipedia.org/wiki/Halting_problem
http://en.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach
因此，如果这是真的，那么如何科学家想出这些估计？那么，他们没有任意的程序，他们有他们写的特定程序。 某些程序是不可判定的，但不是所有*程序都是不可判定的。所以，除非有人犯了严重的错误，科学家们不会去尝试运行一个他们没有证明的程序会停止。
一旦他们证明某些程序会停止，其中一个主要的数学工具被称为大O符号。在一个非常直观的层面上，Big O符号有助于为程序的运行时间随输入大小的变化制定比例定律。在一个非常简单的例子中，假设你的程序是一个循环，并且循环需要一个任意的时间单位运行。如果您运行循环N次，则需要N个时间单位。但是，如果该循环本身位于运行N次的另一个循环中，则整个事件需要N * N个时间单位。这两个计划的规模非常不同。 （这是一个简单的例子，但实际例子可以得到相当复杂。）
http://en.wikipedia.org/wiki/Big_oh
这是一个相当抽象的数学工具。大O分析通常是非常抽象的，他们只是假设所有足够低级别的操作都需要“大约”相同的时间量，而无论如何，Big O并没有真正给出答案，无论如何，无论在几秒钟，几小时还是几天。实际上，真正的计算机也受到硬件细节的影响，例如执行一些非常低级的操作需要多长时间，或者更糟糕的是，将信息从机器的一个部分移动到另一个部分需要多长时间，这对于非常重要多处理器计算机。因此，在实践中，来自大O分析的见解与对机器的详细了解结合起来，以便提出估算。
我问，因为有时我只是没有线索，如果我的程序需要5分钟，1小时或1个月结束......还因为它很有趣，当然:-P – bluewhale 2012-03-06 00:09:45
基于知识必须连续完成的操作，以及每个操作的运行时间，可以估计整个运行时间。就自动化过程而言，计算机科学的早期证明之一就是你甚至不能确定它是否会完成，更不用说它将花费多长时间。 – 2012-03-06 00:12:40
你的意思是一系列的投入？这是[暂停问题]的一个子集（http://en.wikipedia.org/wiki/Halting_problem）。 – paislee 2012-03-06 00:15:18