为什么程序运行时间不是衡量标准？

Question

我已经了解到，一个程序是由它的复杂性来衡量的 - 我的意思是通过Big O Notation。 为什么我们不衡量它的绝对运行时间？ 谢谢:)

Answer 1

由于程序的绝对运行时间不仅取决于使用的算法和输入的大小，而是使用算法的复杂度而不是绝对运行时间来推理算法。它还取决于它运行的机器，各种实现细节以及其他程序当前使用的系统资源。即使您在同一台计算机上使用相同的输入运行相同的应用程序两次，也不会得到完全相同的时间。

因此，当给定一个程序时，不能只是做一个像“这个程序在输入大小为n时运行需要20 * n秒”的语句，因为程序的运行时间取决于比输入多得多的因素尺寸。然而，你可以做一个像“这个程序的运行时间在O（n）”这样的语句，所以这更有用。

Answer 2

绝对运行时间不是一个指示算法如何增长与不同的输入集。对于所有实际数据集，O（n * log（n））算法可能比O（n^2）算法慢得多。

Answer 3

运行时间不测量复杂性，它只测量性能或执行任务所需的时间。一个MP3播放器将运行需要播放歌曲的时间。在这种情况下，经过的CPU时间可能更有用。

复杂性的一个衡量标准是它如何适应更大的输入。这对规划需要的硬件很有用。在所有条件相同的情况下，相对线性缩放的东西优于缩放较差的东西。事情很少平等。

复杂性的另一种衡量标准是衡量代码的简单程度。对于具有相对线性的性能复杂性的程序来说，代码复杂度通常较高复杂的代码可能会造成代价高昂的维护，并且更改可能会导致错误。

所有三个（或四个）措施都很有用，而且它们都不是很有用。三者在一起可能非常有用。

Answer 4

这个问题可以使用更多的上下文。

在编程一个真正的程序时，我们可能会测量程序的运行时间。这有多个潜在的问题，但 1.运行程序的硬件是什么？比较运行在不同硬件上的两个程序实际上并没有给出有意义的比较。 2.其他软件正在运行？如果其他任何东西在运行，它将窃取CPU周期（或者其他运行程序的其他资源）。 3.什么是输入？正如已经说过的，对于一小组来说，解决方案可能看起来非常快，但可扩展性不足。另外，一些输入比其他输入更容易。如果作为一个人，你递给我一本字典并要求我排序，我会马上回传，并说完成。以随机顺序给我一套50张卡片（比字典小得多）将花费我更多的时间去做。 4.什么是起始条件？如果你的程序第一次运行，那么很有可能，将它从硬盘上拆下将占用现代系统中最大的时间。比较两个小输入的实现可能会掩盖其差异。

大O表示法涵盖了很多这些问题。 1.硬件无关紧要，因为所有事情都通过1个操作O（1）的速度进行归一化。 2.大O谈论没有其他算法的算法。3.大O谈论输入如何改变运行时间，而不是输入需要多长时间。它告诉你算法会执行得越差，而不是它在平均或简单输入上的表现如何。 4.再次，Big O处理算法，而不是在物理系统中运行的程序。