Mus*_*afa 1 algorithm time-complexity
在分析算法时间效率时不考虑乘法常数，因为
A）它们在计算效率函数时相互抵消
B）常数函数随着输入大小的增长而增长非常缓慢
C）当输入大小较小时它们的影响很小
D）它们可以被克服由更快的机器
E）它们不会影响算法的实际运行时间
我的猜测是“B”，但我不知道正确答案。所有选项都是错误的吗？
所以这是我的评论扩展为答案：
B）常数函数随着输入大小的增长而增长非常缓慢
这甚至没有意义。常数函数根本不增长；然而，这里我们讨论的不是常数运行时函数，而是在考虑到算法的渐近复杂性的情况下估计实际“步骤”数时可能出现的常数系数。
然而，在渐近分析中，我们并不关心确切的步数，只关心当输入大小趋于无穷大时，运行时间比率作为输入大小的函数的限制。
例如 O(n ^ 2)意味着如果你将输入大小加倍，运行时间将大约是原来的 4 倍，如果你将输入大小增加三倍，它将是原来的 9 倍，等等。它并没有说执行将恰好需要“4 个步骤” ”或“9步”。
C）当输入尺寸较小时，它们的影响较小
不，当输入量较小时，它们的影响相当显着。同样，当输入大小接近无穷大时，我们正在考虑极限。与任何非常数单调增长函数相比，任何常数都渐近可以忽略不n计n。
当n很小时，常量会对执行时间产生巨大影响。例如，有各种有趣且聪明的数据结构，但如果我们只有少量数据，我们通常更喜欢数组而不是二叉树或链表，即使是频繁插入，因为数组具有良好的缓存局部性属性数组使其常数因子如此之小，理论上插入可能比插入树O(n)快得多。O(log n)
D）它们可以被更快的机器克服
这个答案完全没有抓住重点，算法的渐近分析与物理机器的速度无关。是的，随着时间的推移，机器变得越来越快，但这只是一个恒定因素。如果您在更快的机器上运行算法程序O(n ^ 2)，则在输入大小加倍的情况下执行它仍然需要 4 倍的 CPU 时间。
E）它们不影响算法的实际运行时间
这也是错误的，他们绝对是这样做的。
所以剩下的唯一答案是 A，如果按照我上面的解释（与执行时间的比率有关）解释，这可能是正确的，但我肯定会以完全不同的方式表达它。