为什么在分析算法效率时不考虑常量？
Why constants are not considered in analysis of algorithm efficiency?
在算法时间效率分析中不考虑乘法常数，因为
A) 它们在计算效率函数时相互抵消
B) 常数函数随着输入大小的增长而增长非常缓慢
C) 当输入尺寸较小时，它们的影响很小
D) 它们可以被更快的机器克服
E) 它们不影响算法的实际 运行 时间
我的猜测是 "B"，但我不知道正确答案。所有选项都不正确吗？
所以这是我的评论扩展为答案：
B) constant functions grow very slowly with input size growth
这甚至没有意义。常数函数甚至根本不会增长； 然而，这里我们不是在谈论常数运行时间函数，而是常数系数 在给定算法的渐近复杂度的情况下估计 "steps" 的实际数量时可能会出现这种情况。
然而，在渐近分析中，我们不关心确切的步数，只关心随着输入大小趋于无穷大，运行ning次作为输入大小的函数的比率的极限.
E. G。 O(n ^ 2) 意味着如果你将输入大小加倍，运行ning 时间将大约是原来的 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，如果按照我上面的解释（关于执行时间的比率）解释，可能是正确的，但我会用相当的措辞肯定不同。
我认为答案是D:
Multiplicative constants are not considered in analysis of algorithm time efficiency because
D) they can be overcome by faster machines
机器变得越来越快，给出常数因子加速，这克服了乘法常数，因此我们可以忽略乘法常数进行分析。
我宁愿说我们忽略了乘法常数，因为它们取决于特定的机器，但对于多项选择，我们必须选择提供的最佳答案。
在算法时间效率分析中不考虑乘法常数，因为
A) 它们在计算效率函数时相互抵消
B) 常数函数随着输入大小的增长而增长非常缓慢
C) 当输入尺寸较小时，它们的影响很小
D) 它们可以被更快的机器克服
E) 它们不影响算法的实际 运行 时间
我的猜测是 "B"，但我不知道正确答案。所有选项都不正确吗？
所以这是我的评论扩展为答案：
B) constant functions grow very slowly with input size growth
这甚至没有意义。常数函数甚至根本不会增长； 然而，这里我们不是在谈论常数运行时间函数，而是常数系数 在给定算法的渐近复杂度的情况下估计 "steps" 的实际数量时可能会出现这种情况。
然而，在渐近分析中，我们不关心确切的步数，只关心随着输入大小趋于无穷大，运行ning次作为输入大小的函数的比率的极限.
E. G。 O(n ^ 2) 意味着如果你将输入大小加倍，运行ning 时间将大约是原来的 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，如果按照我上面的解释（关于执行时间的比率）解释，可能是正确的，但我会用相当的措辞肯定不同。
我认为答案是D:
Multiplicative constants are not considered in analysis of algorithm time efficiency because D) they can be overcome by faster machines
机器变得越来越快，给出常数因子加速，这克服了乘法常数，因此我们可以忽略乘法常数进行分析。
我宁愿说我们忽略了乘法常数，因为它们取决于特定的机器，但对于多项选择，我们必须选择提供的最佳答案。