我们今天在课堂上做了一个关于大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 n2 = O(n2),但根据我的教授,答案只是O(n).有没有人可以向我解释为什么,当我们只是改变我们认为是输入大小的时候？
我明白这不是一个嵌套循环 – 这不是令我困惑的.我不明白为什么给定的输入大小,第二个循环只被认为是O(n).我可以理解这一点的唯一方法是如果我们隔离第二个循环,然后将输入大小重新定义为简单的n = size ^ 2.我在正确的轨道上吗？
