function - 给定函数的复杂度

Question

当我分析下面代码段的复杂度时，我发现它是O(n/2)。但是在搜索互联网时，我发现它可能是O(n)。我想知道谁是正确的。

void function(int n) {
    int i = 1, k = 100;
    while (i < n) {
        k++;
        i += 2;
    }
}

Answer 1

上述方法中变量 k 的意义何在？不管大 O 表示法谈论极限中的行为（当 n 的值接近无穷大时）。因此，big-O 表示法对比例因子和常数都是不可知的。也就是说，对于任何常数“c”和比例因子“s”

O(f(n)) 等价于 O(s*f(n) + c)

在您的情况下，f(n) = n，s = 1/2，c = 0。所以...

O(n) = O(n/2)

Answer 2

O(n) 与 O(n/2) 相同

big-O 表示法的想法是了解当您给它更大的输入时算法将运行多快。因此，例如，如果您将输入的大小加倍，程序将花费两倍还是将花费 4 倍。

由于当您改变 N 的值时，n 和 n/2 的行为相同（即，如果您将 N 增加 10 倍，则 N 本身和 N/2 的缩放比例相同）。

Answer 3

O(n/2) = O(0.5n) = O(n)。有关此内容的更多信息，请参见Wikipedia。

如果f是O(g)，那么存在一些c和n使得对于所有x > n，|f(x)| <= c * |g(x)| . 也就是说，从输入n开始，c * g(x)支配f(x)。

它遵循O(n/2) = O(n)，因为，

• 如果f(x) = x/2和g(x) = x，那么我们设置c = 0.5和n = 0。
• 如果f(x) = x和g(x) = x/2，那么我们设置c = 2和n = 0。

请注意，有无数个c和n值可以用来证明这一点。（在上面我将它们最小化，但这不是必需的。）