编辑：
谢谢你的回复.我想通过“运行时和输入大小之间的关系”来澄清我的意思,因为它有点模糊.
据我所知,增长率是运行时与输入的梯度.因此,n ^ 2的增长率将给出形式t = k(n ^ 3)常数的等式.鉴于该等式更具信息性(因为它包括常数)并显示与所需时间的直接关系,我认为这将是首选.
我明白随着n的增加,常数很快变得无关紧要,并且根据不同的计算配置,k将会不同.也许这就是为什么仅仅适应增长率就足够了.
该算法不是影响实际运行时间的唯一因素编程语言,优化,分支预测,I / O速度,分页,处理速度等等都会发挥作用.
一种语言/机器/其他任何东西都可能具有优势,因此每种算法都需要在完全相同的条件下执行.
除此之外,当考虑驻留在RAM中的输入和输出时,一种算法可能在C中优于另一种算法,但是当考虑驻留在磁盘上的输入和输出时,另一种算法可能优于Python中的第一种算法.
毫无疑问几乎没有机会就应该用于执行所有基准测试的确切条件达成一致,即使可以达成这样的协议,今天使用5年的基准测试结果肯定是不负责任的.在计算领域,所以需要定期为所有算法重新创建这些结果 – 这将是一项庞大,非常耗时的任务.
算法具有不同的常数因子
在极端情况下,某些算法的常数因子如此之高,以至于其他渐近较慢的算法在现代的所有合理输入上都优于它.如果我们仅仅考虑运行时间,那么这些算法在较大输入上优于其他算法的事实可能会丢失.
在不太极端的情况下,由于所涉及的常数因素,我们将获得在其他输入大小上不同的结果 – 我们可能会在所有测试中看到一个算法更快,但是一旦我们达到一些输入大小,另一个可能变得更快.
某些算法的运行时间在很大程度上取决于输入
例如,对已经排序的数据的基本快速排序采用O(n ^ 2),而平均需要O(n log n).
人们当然可以确定最佳和最差的情况并为这些情况运行算法,但平均情况只能通过数学分析来确定 – 你不能为’普通情况’运行它 – 你可以运行它一堆随机输入的时间和得到的平均值,但这是相当不精确的.
所以粗略估计就足够了
由于上述原因,仅仅说一个算法是有意义的,例如,O(n ^ 2),这非常粗略地意味着,如果我们处理足够大的输入大小,如果我们处理足够大的输入大小,则需要4倍的时间.输入大小加倍.如果你一直在关注,你会知道实际花费的时间可能会比4倍长,但它至少给了我们一些想法 – 我们不会期望它需要两倍的时间,也不会超过10倍更长的时间(尽管可能在极端情况下).例如,我们还可以合理地期望O(n log n)算法在大n上优于O(n ^ 2)算法,这是一个有用的比较,并且可能更容易看到发生了什么比一些更确切的表示.