c - 大 O 符号运行时

Question

我得到了一些代码来计算它们的大 O 运行时，有人可以告诉我我是否在正确的轨道上吗？

//program1
 int i, count = 0, n = 20000;

for(i = 0; i < n * n; i++)
{
    count++;
}

是 O(n^2) 吗？

//number2
int i, inner_count = 0, n = 2000000000;

    for(i = 0; i < n; i++)
    {
        inner_count++;
    }

这是一个 O(n) 吗？

//number3
for(i = 0; i < n; i++)
{
    for(j = 0; j < n; j++)
    {
        count++;
    }
}

O(n^2)?

//number4
for(i = 0; i < n; i++)
{
    for(j = 0; j < i; j++)
    {
        for(k = 0; k < j; k++)
        {
            inner_count++;
        }
    }
}

是 O(n^3) 吗？

//number5
int i, j, inner_count = 0, n = 30000;

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

这是一个 O(n^3) 吗？

//number6
int i, j, k, l, pseudo_inner_count = 0, n = 25;

for(i = 0; i < n; i++)
{
    for(j = 0; j < i*i; j++)
    {
        for(k = 0; k < i*j; k++)
        {
            pseudo_inner_count++;
            for(l = 0; l < 10; l++);
        }
    }
}

对这个 O(n^3) 很困惑？？

//number7

int i, j, k, pseudo_inner_count = 0, n = 16;

for(i = n; i > 1; i /= 2)
{
    for(j = 0; j < n; j++)
    {
        pseudo_inner_count++;
        for(k = 0; k < 50000000; k++);
     }
}

O(n)？ (他们越努力，我就越迷路)

//number8
int i, j, pseudo_inner_count = 0, n = 1073741824;

for(i = n; i > 1; i /= 2)
{
    pseudo_inner_count++;
    for(j = 0; j < 50000000; j++);
}

O(n^2)?

还有一个我没有看到，也完全不知道 {

    int i, wrong_count = 0, n = 200;

    for(i = 0; i < square(n); i++)
    {
        wrong_count++;
    }

    printf("%d %d\n", wrong_count, square(wrong_count));

    return 0;
}

int square(int m)
{
    int i, j = 0;

    for(i = 0; i < m * m; i++)
    {
        j++;
    }

    return j;
}

如果有人能澄清这些并帮助我更好地理解它们，我将不胜感激。

Answer 1

• 数字 5 是 O(N^2)
• 数字 6 是 O(N^6)
• 数字 7 是 O(N*logN)
• 数字 8 是 O(logN)

其余的似乎是正确的。

试着理解作为N的函数做了多少操作，都是常量操作，比如

for (int i = 0; i < 333333333; ++i) { j++; } 

实际上是 O(1)