好的,所以我今天晚些时候有一个期中考试,我正在审查的项目之一是 big-O。现在,我在当天完成了家庭作业,并获得了 100%....但我现在找不到它,我不确定我在做什么。Sooo 有人可以解释一下我做错了什么……如果我做对了……也许你知道我为什么怀疑自己?谢谢!
另外,我记得我以前在做作业时使用求和,我会从内到外工作。当我完成每个求和时,我使用一些“公式”来计算最高的 n,然后保留该值并继续进行下一个求和,依此类推,直到求和全部完成。
问题1。
sum = 0;
for (i = 0; i < n; i++)
sum++;
所以,由于我忘记了整个求和方面,我的直觉告诉我这是 O(N),因为最大运行时间是 N 次......因为它只是一个 for 循环。
问题 2。
sum = 0;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
sum++;
对于这个,我“认为”最高运行时间是 O(N^2),因为两个循环都依赖于 n,并且每个 if 循环可以在 N * N 处最大化。
问题 3。
sum = 0;
for (i = 0; i < n; i++)
for (j = 0; j < n * n; j++)
sum++;
这就是我卡住的地方......我觉得我实际上需要使用求和布局以及将它们相加的公式。最里面的循环可以在 n*n 处最大化,所以 n^2。最重要的是,对于最外层的循环,它可以再次在 N 处最大化……所以我猜是 0(N^3)。
问题 4。
sum = 0;
for (i = 0; i < n; i++)
for (j = 0; j < i; j++)
sum++;
再一次,我对这个更迷失了。内部循环可以最大化 i 次...这取决于 i 然而,这取决于 N...所以...我看到三个最大化的变量,我真的不确定如何比较它们以找到最大化运行。(我真的需要记住求和设置和公式)。
下一个问题也是如此,不知道从哪里开始,我宁愿不尝试,因为我不想在脑海中产生错误的想法。我很肯定,一旦我再次看到公式,它会立即点击,因为我之前得到它......我只是以某种方式丢失了它。任何帮助表示赞赏!
问题 5:
sum = 0;
for (i = 0; i < n; i++)
for (j = 0; j < i * i; j++)
for (k = 0; k < j; k++)
sum++;
问题6:
sum = 0;
for (i = 1; i < n; i++)
for (j = 1; j < i * i; j++)
if (j % i == 0)
for (k = 0; k < j; k++)
sum++;