c++ - 对big-O表示法感到困惑(具体示例)

Question

我们今天在类里面做了一个关于大 O 表示法的练习。这是其中一个问题:

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;
    }
}

我的直觉告诉我 f(n) = n/2 + n² = O(n²) 但根据我的教授，答案很简单 O( n).谁能向我解释为什么以及何时我们只更改我们认为是输入大小的内容？

我知道这不是嵌套循环——这不是让我感到困惑的地方。我不明白为什么对于给定的输入 size，第二个循环只被认为是 O(n)。我能理解这一点的唯一方法是，如果我们隔离第二个循环，然后将输入大小重新定义为简单的 n = size^2。我在正确的轨道上吗？

Answer 1

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

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

正如其他人所说，如果 cout << max被删除后，编译器可能将循环优化为单个 O(1) 赋值，这意味着该函数的其他 O(n) 操作决定了整体大 O 效率，但它可能不会 - 谁说您甚至启用了优化？因此，描述大 O 效率的最佳方式是说“如果优化开始，则 O(n) 否则 O(n^2)”——断言一个或另一个然后隐藏你的假设是没有用的，并且如果他们错了，后果在脚注中。