我们今天在课堂上做了一个关于大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.我在正确的轨道上吗？
解决方法
如果你所提供的代码正是您教授评论的代码,那么他错了.如所写的,它输出每个数字从1到大小*大小,这绝对是O(n ^ 2),因为n =大小是理想的选择.
是的,你是对的,认为你可以说“O(n)”,其中n是数组大小的平方“,但这是没有目的的复杂性.
如其他人所说,如果cout < max被删除,编译器可以将循环优化为单个O(1)赋值,这意味着函数的其他O(n)操作决定了整体的大O效率,但可能不会 - 谁表示你甚至能够进行优化？因此,描述大O效率的最佳方法是说“如果优化踢在O(n)else O(n ^ 2)” - 这是无用的一个或另一个然后隐藏你的假设,而后果如果错了,在脚注中.