performance - 当预期输入大小很小时，Big Theta Notation 是算法效率的有效度量吗？

Question

我四处寻找有关 Big-Theta 的信息，我想我已经对它有了一个不错的理解。然而，问题仍然存在：当预期输入大小较小时，Big Theta Notation 是否是算法效率的有效衡量标准？

我认为当预期输入大小很小时，Big Theta Notation 不是算法效率的有效度量。首先是我对 Big Theta 的部分理解：如果函数 f(n) 是 O(n) 和 Big Omega(n)，那么它就是 Big Theta(n)。所有这些值的数学定义要求 n>n0。因此，根据我的推理，小输入大小有可能（并且很可能）小于 n0。因此，我的推理是，对于 n< n0 的值，Big Theta Notation 不是算法效率的有效度量。

Answer 1

那是对的。对于小的输入大小，运行时间可以是任何东西。例如，当对一小部分数字列表（大约 10 个元素）进行排序时，尽管运行时间是二次渐近的，但插入排序实际上是最快的算法之一。