计算大O符号

Question

sum = 0;
for (i=0;i<n/2;i++)
    for (j=i; j<n/4; j++)
        sum++;

上面代码的大O是什么？我计算了大O，但我不确定它是否正确。

这就是我的答案

外部循环将运行n/2时间

内部循环将运行(n/4 - 1) = ((n-4)/4 )

T(n) = (n/2) * ((n-4)/4 )
     = (n^2 -4n + 16)/8
     = 1/8 n^2 - 1/2 n +2

所以大O是O(n^2)，这是正确的吗？

Answer 1

是的，在大的O计算中，前导系数和子导引项被丢弃。

是f(x)是O(g(x))，如果f(x) <= M g(x)对于x超出了一些x0和一些常量M。在本例中为M = 1/8和x0 = 4。

Answer 2

检查简单for循环中相互嵌套的大O的一个非常简单的方法是：O(n ^ (number of loops))

请注意，仅当循环的所有限制都是n的实数倍时，上述技术才有效。

在你的问题中，内部循环是n/2，外部循环是n/4。两者都是n的实数倍。所以大O将是：O(n ^ 2)。

希望这能帮上忙。

Answer 3

好吧，它是O(n^2)，如果这就是你所关心的(通常应该是)，那么你是对的。但我不认为常数是1/8。

如果你想说得准确些，我认为应该是：

n/4 + n/4 -1 + n/4 - 2 + ... 3 + 2 + 1 = n/4 *(n/4 + 1)/2 = n^2/32 + n/8

当i大于或等于n/4时，内部循环将不会运行。所以你不应该把这部分算进去。