c++ - 用 C++ 学习大 O 表示法，对这是 O(n) 还是 O(n2) 感到困惑

Question

我正在使用 YouTube 和任何我能找到的东西学习编程。我偶然发现了一些 Big O 问题，我对其中一个问题感到很困惑。

for (int i = 0; i < n; i++)
    for (int j = 0; j < 2; j++)
        cout << i << " " << j << endl;

我的第一个想法是它是 O(n²) 因为有 2 个 for 循环。然后我仔细观察，发现内部 for 循环只从 0 到 2。

据我了解，Big O 会考虑最坏的情况。我的想法是，如果 n = 2 那么它会导致 O(n²) 但是所有其他情况都会导致 O(n) 这让我很困惑。

谁能解释一下为什么这是 O(n²) 或 O(n)？

Answer 1

它是O(n)。当一个函数 f(n) 是 O(n) 时，它基本上意味着有一些常量 A 和 B 这样对于每个 n(至少对于足够大的 n):

f(n) <= A * n + B

换句话说，常量(乘法和加法)不影响大 O 表示法。由于 2 是一个常量(它不依赖于 n)，因此它不会反射(reflect)在大 O 表示法中。

在您的情况下，函数 f 是时间复杂度 - 即程序对大小为 n 的输入需要多少个恒定时间步。