Big O表示法作业 – 代码片段算法分析？

对于家庭作业，我给了以下8个代码片段来分析并给出运行时间的Big-Oh表示法。如果我走在正确的轨道上，有人可以告诉我吗？

//Fragment 1 for(int i = 0; i < n; i++) sum++;

我想O（N）代表片段1

 //Fragment 2 for(int i = 0; i < n; i+=2) sum++;

对于片段2也是O（N）

 //Fragment 3 for(int i = 0; i < n; i++) for( int j = 0; j < n; j++) sum++;

片段3的O（N ^ 2）

 //Fragment 4 for(int i = 0; i < n; i+=2) sum++; for(int j = 0; j < n; j++) sum++;

片段4的O（N）

 //Fragment 5 for(int i = 0; i < n; i++) for( int j = 0; j < n * n; j++) sum++;

片段5的O（N ^ 2）但是n * n让我失去了一点所以我不太确定

 //Fragment 6 for(int i = 0; i < n; i++) for( int j = 0; j < i; j++) sum++;

对于片段6也是O（N ^ 2）

 //Fragment 7 for(int i = 0; i < n; i++) for( int j = 0; j < n * n; j++) for(int k = 0; k < j; k++) sum++;

片段7的O（N ^ 3）但是n * n再一次让我失望

 //Fragment 8 for(int i = 1; i < n; i = i * 2) sum++;

片段8的O（N）

我认为片段5是O（n ^ 3），类似地片段7是O（n ^ 5）*。对于片段8，它看起来也像O（log（n））。

对于n * n问题，你必须执行循环体n * n次，所以它将是O（n ^ 2），然后你用其他代码的顺序复合它。片段8实际上是计数器的两倍而不是递增它，所以问题越大，你需要做的额外工作就越少，所以它是O（log（n））

*编辑：片段7是O（n ^ 5），而不是我之前认为的O（n ^ 4）。这是因为j 和k都从1到n * n。对不起我之前没有抓到这个。

片段7是O（n ^ 5），而不是当前接受的评论声明的O（n ^ 4）。否则，这是正确的。

对于案例8，尝试写出一些N值的迭代次数，看看模式是什么样的……它不是O（N）

你似乎走在了正确的轨道上。关于N * N，您认为它会产生什么影响？它是N的另一个因素，因此可能是更高的顺序。

只是一个警告，我看到这样的另一个post，它被投票了。小心。这是post。

你走在正确的轨道上，但这里有一个关于如何在这一过程中更清晰的提示。假设你有一些代码：

 for(i = 0; i < n; i++) { for(j = 0; j < 100; j++){....} }

是的，请考虑您拥有不同级别的代码。在此示例中，到目前为止您只能看到3个级别：

在任何时候你都不应该尝试一次性地计算它。这是大多数初学者产生某种算术错误的地方。为每个级别单独计算它，然后将它们相乘。

祝你好运！