大O符号运行 [英] Big O notation runtime

问题描述

我一直在考虑一些code对他们的工作进行大O字运行时，可能会有人告诉我，如果我在正确的轨道上或不？

I have been given some code to work out big O runtimes on them, could someone tell me if I am on the right track or not?

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

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

是为O（n ^ 2）？

Is that O(n^2)?

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

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

是这个O（N）？

is this one O(n)?

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

为O（n ^ 2）？

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）？

Is that 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）？

Is that one 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）??

Very confused about this one 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）？ （我得到更多的失去了，因为他们会更加困难）

O(n)? (I get more lost as they get harder)

//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）？

O(n^2)?

更多我没有看到和完全不知道一个
{

one more i didn't see and have absolutely no idea with {

    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;
}

如果任何人都可以澄清这些，帮助我更好地理解他们，我将非常感激。

If anyone could clarify these and help me understand them better I would be very grateful.

推荐答案

• number5为O（N ^ 2）


• number6是O（N ^ 6）


• number7为O（N * logN）的


• number8为O（logN）的

剩下的似乎是正确的。

试着去了解有多少业务为N，所有的不断运行，功能完成，如

Try to understand how many operations are done as function of N, all the constant operation, such as

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

其实都是O（1）

are in fact O(1)

这篇关于大O符号运行的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！