algorithm - 大哦符号

Question

我好像被一个问题搞糊涂了

这是问题，然后是我的假设:

Al 和 Bob 正在争论他们的算法。 Al 声称他的 O(n log n) 时间方法总是比 Bob 的 O(n^2) 时间方法快。为了解决这个问题，他们进行了一系列实验。令 Al 沮丧的是，他们发现如果 n<100，O(n^2)-time 算法运行得更快，只有当 n>=100 时 O(n log n)-time 算法才更好。解释这是怎么可能的。

据我了解，用 O(n^2) 时间方法编写的算法仅对少量输入 n 有效。随着输入的增加，效率会随着运行时间的急剧增加而降低，因为运行时间与输入的平方成正比。 O(n^2)-time 方法比 O(n log n)-time 方法更有效，仅适用于非常少量的输入(在这种情况下输入小于 100)，但随着输入变大(在本例为 100 或更大)，O(n log n) 成为更有效的方法。

我只是在陈述问题中显而易见的内容，还是答案似乎满足了问题？

Answer 1

您在回答中指出，为 O(N^2)，运行时间与输入大小的平方成正比。跟进 - 存在一个比例常数，但没有用大 O 符号描述。对于实际时间，常数的大小很重要。

Big-O 也忽略了低阶项，因为它们渐近地被最高阶项支配，但这些低阶项仍然对实际时间有贡献。

由于其中一个(或两个)问题，具有较高增长率的函数对于有限范围的输入可能会产生较小的结果。