algorithm - 为什么在分析算法效率时不考虑常量？

Question

在分析算法时间效率时不考虑乘法常数，因为
A) 它们在计算效率函数时相互抵消
B) 常数函数随着输入大小的增长而增长非常缓慢
C) 它们当输入量较小时影响很小
D)它们可以被更快的机器克服
E)它们不影响算法的实际运行时间

我猜是“B”，但我不知道正确答案。所有选项都不正确吗？

Answer 1

所以这是我的评论扩展到一个答案:

B) constant functions grow very slowly with input size growth

这甚至没有意义。常数函数甚至根本不会增长； 但是，这里我们不是在谈论恒定的运行时函数，而是在估计“步数”的实际数量时可能出现的常数系数 "给定算法的渐近复杂性。

然而，在渐近分析中，我们不关心确切的步数，只关心运行时间的比率作为输入大小的函数的限制，因为输入大小趋于无穷大。

E. G。 O(n ^ 2) 表示如果将输入大小加倍，运行时间将约为原来的 4 倍，如果将输入大小增加三倍，则将是原来的 9 倍，依此类推。它没有说执行将采取恰好“4 步”或“9 步”。

C) they have a small effect when input size is small

不，当输入尺寸较小时，它们的效果相当显着。同样，我们正在考虑输入大小接近无穷大的限制。与 n 的任何非常量单调增长函数相比，随着 n 趋于无穷大，任何常数都可以渐近忽略。

当 n 较小时，常量会对执行时间产生巨大影响。例如，有各种有趣和聪明的数据结构，但如果我们只有少量数据，我们通常更喜欢数组而不是 e。 G。二叉树或链表，即使是频繁插入，因为数组良好的缓存局部性属性使其常数因子非常小，理论上 O(n) 插入可能比O(log n) 插入到树中。

D) they can be overcome by faster machines

这个答案完全没有捕获重点，算法的渐近分析与物理机器的速度无关。是的，机器随着时间的推移变得越来越快，但同样，这只是一个不变的因素。如果您在速度更快的机器上运行用于 O(n ^ 2) 算法的程序，在输入大小加倍的情况下执行它仍需要 4 倍的 CPU 时间。

E) they do not affect the actual run time of the algorithm

那也是错误的，他们绝对是这样。

所以剩下的唯一答案是 A，如果按照我上面的解释(与执行时间的比率相关)进行解释，它可能是正确的，但我肯定会用完全不同的措辞。