对于小输入大小，常数在时间复杂度上是否重要？如何？

Question

我正在听一些关于时间复杂度的讲座，link https://www.youtube.com/watch?v=__vX2sjlpXU 作者在 4:50 解释说，当输入量较小时，常量在很多情况下都很重要.请解释

Answer 1

假设有两种算法，实际复杂度分别为100n和2n²，所以它们分别是O(n)和O(n²).对于 n = 2，它们将分别执行 200 和 8 CPU 个周期。但是当 n 的值大于 50 时，100n 算法总是比 2n² 算法表现更好。

这样我们就可以看到，对于较小的输入，Big O 可能无法很好地判断算法，常数起着重要作用，尤其是当它们与输入相比相当大时。

同理，处理100+n和2+n²等时间复杂度时的结果也可以理解。对于不够大的 n 值无法超过常量的影响，实际执行时间可能最终由常量而不是输入值 n 决定。

Answer 2

对于时间复杂度的数学术语，它无关紧要。

但是，如果您的程序有很大的常量，即使它具有良好的复杂性，也可能比复杂性较差的程序慢。这很明显，想象一下 1 hour 的睡眠，您的程序需要很长的一个大常量。但它的复杂性 class 可能很好，因为常数无关紧要。

为什么它们不重要？因为对于每个复杂性较差的程序，都会有一个输入（大输入），它们有时会变慢。

这是一个例子：

良好的复杂性O(1)，无论如何都很慢：

void method() {
    sleep(60 * 60 * 1_000); // 1 hour
}

更复杂 O(n)，小输入更快：

void method(int n) {
    for (int i = 0; i < n; i++) {
        sleep(1_000); // 1 second
    }
}

但是如果你输入 n > 60 * 60 第二种方法会变慢。

你不应该混淆时间复杂度和实际可测量的运行时间，它是巨大的差异.

时间复杂度大约是渐近边界，参见f in O(g)的定义：

Answer 3

好吧，当我研究算法及其复杂性时，我们的教授简要解释了常量很重要。在复杂性理论中，有两种主要的符号来解释复杂性。第一个是 BigO，第二个是 tild 符号。

假设你实现了一个优先级队列（使用堆），它需要 2lgN 比较来删除最大元素，1 + logN 来插入每个项目。现在人们实际上做了什么，他们删除 2logN 并将其写为 O(logN) 但这是不对的，因为 1+logN 只需要插入一个元素，当你删除一个元素时，你需要重新平衡队列（下沉和游泳）功能。

如果您将 ~2logN 写成 O(logN) 那么这意味着您只计算一个函数的复杂性，游泳或下沉。

作为参考，我要补充一点，在一些排名靠前的大学中，大多数教授使用 ~ 符号。

BigO 可能有害。 Robert sedgewick and Kevin Wayne 写的一本书使用 ~ 并解释了为什么他更喜欢它。

对于小输入大小，常数在时间复杂度上是否重要？如何？

Do constants matter in time complexity for small input sizes? How?

algorithm

complexity-theory

big-o

time-complexity