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

Question

对于家庭作业,我给了以下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)

Answer 1

我认为片段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.对不起,我之前没有抓到这个.

Answer 2

片段7是O(n ^ 5),而不是当前接受的评论声明的O(n ^ 4).否则,这是正确的.