10

We did an exercise in class today dealing with big-O notation. Here is one of the problems:

void modifyArray(int a[], int size)
{   
    int max = a[0];
    for (int i = 1; i < size / 2; ++i)
    {
        if (max < a[i])
        max = a[i];
    }
    for (int j = 1; j <= size * size; ++j)
    {
        ++max;
        cout << max;
    }
}

My intuition tells me that f(n) = n/2 + n2 = O(n2) but according to my professor the answer is simply O(n). Could anyone explain to me why and when we just change what we consider to be the input size?

I understand that it is not a nested loop -- that is not what is confusing me. I don't understand why for a given input size, the second loop is only considered to be O(n). The only way I can make sense of this is if we isolate the second loop and then redefine the input size to simply being n = size^2. Am I on the right track?

4

3 回答 3

4

如果您提供的代码正是您的教授正在评论的代码，那么他就错了。如所写，它输出从 1 到 的每个数字size * size，这绝对是 O(n^2)，因为 n = size 是明智的选择。

是的，您认为您可以说“O(n)，其中 n 是数组大小的平方”是对的，但这是没有目的的复杂化。

正如其他人所说，如果cout << max将你甚至启用优化？因此，描述 big-O 效率的最佳方式是说“如果开始优化，则 O(n) 否则 O(n^2)”——断言一个或另一个然后隐藏你的假设是没有用的，并且如果他们错了后果，在脚注中。

于 2013-11-06T06:12:41.357 回答
3

考虑这个例子：

for (i = 0; i < N; i++) {
    sequence of statements
}
for (j = 0; j < M; j++) {
    sequence of statements
}

第一个循环是 O(N)，第二个循环是 O(M)。因为你不知道哪个更大，所以你说这是 O(max(N,M))。

在您的情况下，N=size/2 和 M=size*size。

O(max(N,M)) 变为 O(max(size/2,size*size))，即 O(size*size)。所以 f(n)=O(size^2)=O(n^2)

对于您要问的问题；是的，我认为，你认为是正确的。将输入大小重新定义为 n = size^2。这应该是将其视为 O(n) 的方式。

于 2013-11-06T07:24:06.723 回答
1

实际上可以取消第二个循环。

如果不考虑输出中间项，那么

It is equivalent to max += size*size.

那么代码复杂度将降低到O(size/2) ~ O(size).

于 2013-11-06T05:59:22.060 回答