algorithm - 运行时间，复杂性，编译时间和执行时间有什么区别？

Question

运行时间、复杂性、编译时间和执行时间有什么区别？
运行时间与时间复杂度有冲突，执行时间和执行时间有什么区别？

Answer 1

您真正需要的是如何将大O时间复杂度转换为运行时。这不像一开始看起来那么容易。
因此，先仔细看看复杂性，让它更容易些，让我们使用这个简单的C++示例：

int fact(int n)
 {
 if (n<=1) return 1;
 return n*fact(n-1);
 }

时间与空间复杂性
（对于初学者来说，我假设基本变量，因此所有的复杂性都与基本信息相同，更多信息见下一个子弹），所以这整个事情将做 n迭代，意味着 O(n)时间复杂度。由于它使用堆栈递归和堆作为单个辅助结果，所以时间复杂度也为 O(n)。
基本复杂性与真实复杂性
基本复杂度是所用算法的复杂性。但是，当实现到程序中时，由于变量实现、IO协议等因素，复杂性可能会（更糟）。
例如，如果我们使用bigint来代替 int？程序是相同的，所以基本复杂度保持 O(n)。Bignts的问题是，不是 O(1)空间复杂度（更像 O(log(n))），它们上的操作也不再是 O(1)。例如，如果（ m=log(n)）然后 (+,-,&,|,^)操作是 O(m)，则可变的可以变化到 O(m^2)。因此，当集合在一起时，时间复杂度将是 O(n.log(n).log(n))如果使用 O(m^2)乘法。空间复杂度也更差 O(n.log(n))。
问题是大多数新手只使用基本的算法复杂性，而不是整个实现的复杂性，导致模糊的结果。现在的另一个问题是在没有任何背景知识的情况下滥用libs和框架。
计算运行时
这种程序设计中的therm有时被认为是一种矛盾修饰法对于任意实现，没有可靠的方法将复杂度转换为运行时。为什么？因为运行时依赖的东西太多了，比如：
展位空间与时间复杂性
现代体系结构使用流水线、超级缩放、缓存等，因此当遇到空间障碍时，性能通常会发生多次变化，甚至更差。
硬件平台
每个平台都不同。流水线/缓存大小的配置、管理策略、延迟等，甚至与同类功率CPU相比，都有着巨大的差异，在硬件平台上，不仅仅是CPU每个模块使用的计数（内存、硬盘、DMA、gfx…）
编译程序
每个编译器都有自己的特性、优化等，导致不同的程序集输出这可能导致在不同编译器上编译的同一源代码的可执行文件之间存在巨大差异。
操作系统
操作系统比你的应用运行得更多。有服务、中断、维护任务和其他进程，所有这些都会影响运行时。
编程风格
这也可以做到。大多数编程风格的差异通常由编译器优化来抵消，但并非全部。例如，迭代前的递归首选项会对运行时产生巨大（通常是负面的）影响。
优化
如果您在程序集中查看未优化的代码和优化的代码，您将经常无法识别这些代码这不应影响程序的基本复杂度，但如果可能的话，常常会改变真正的复杂性。
而且我编码了几十年，所以我习惯自己优化我的代码。这种偏好有时会误导现代编译器，并在极少数情况下导致生成代码的速度减慢。
那么如何计算运行时呢？
你不能只做测量+估计。
测量任务开始时的时间 t0
测量任务期间的时间（有时）
例如，每一秒，或每一次 1000th迭代记住时间 t和开始 i。这有时被称为消耗时间。
预测剩余时间。
所以如果我们有时间复杂性 O(n)那么（如果我没有错的话）：

t(0) = t0
t(i) = ti ~= t0 + T*i -> T ~= (ti-t0)/i
t(n) = t0+T*n ~= t0 + (ti-t0)*n/i

您可以在计算期间平均或更新此时间，以便每次新测量都会越来越精确。有时从最后几次测量中评估运行时会更好，因为处理能力会在时间内发生变化。
在高精度测量时间时注意操作系统的粒度参见
wrong clock cycle measurements with rdtsc
如果不加以考虑，可能会误导你的计算。但这只在你想测量非常快的过程时才重要，我认为不是这样。
附言。
这一切都只适用于足够大的 ，否则复杂的废弃热仍然是重要的，并且会影响结果的准确性。
编译时
如另一个答案所述，编译器需要处理源代码这与程序复杂性无关。这主要受递归级别、源代码长度、宏用法和递归、模板用法等的影响。
通常通过对 t(i)顺序进行简单的重新排序并避免多个包含，可以显著提高编译时间。很好的例子是来自atmel的avr32框架…调整后，编译时间可以提高100倍甚至更多有一次我看到（过去10年多）一个打印机固件，它有300MB的源代码（当时），由于包含的滥用，编译时间比一小时稍微短一些…这是疯狂的考虑到这是一个单片机的代码。。。
希望有帮助