Время выполнения обозначений Big O - PullRequest
Новая
       15

Время выполнения обозначений Big O

3 голосов
/ 18 марта 2010

Мне дали какой-то код для обработки больших 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++);
     }
}

На)?(Я становлюсь все более и более потерянным по мере того, как они становятся все труднее) 

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

Если бы кто-нибудь смог прояснить это и помочь мне лучше понять их, я был бы очень благодарен.

Ответы [ 3 ]

8 голосов
/ 18 марта 2010
  • число5 - это O (N ^ 2)
  • число 6 - это O (N ^ 6)
  • число 7 - это O (N * logN) * ​​1006 *
  • число 8 - это O (logN) * ​​1008 *

остальное кажется правильным.

Попытайтесь понять, сколько операций выполняется как функция N, все постоянные операции, например 

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

на самом деле O (1)

3 голосов
/ 18 марта 2010

number5 = O (n ^ 2) - 2-й цикл идет от 1 до числа, меньшего, чем n, включая n, так что в основном это 1..n или O (n).

number6 = O (n ^ 6) - 2-й цикл - n ^ 2, а третий - n ^ 3 (n * n ^ 2). Четвёртый, внутренний цикл - O (1), поэтому он не считается.

number7 = O (n log n) - первый цикл O (log2 (n)) (потому что вы продолжаете делить индекс на 2), а 2-й цикл O (n) 1..n, и внутренний цикл снова O (1), потому что он не зависит от n.

number8 = O (log n) - та же причина, что и выше.

остальное в порядке.

1 голос
/ 18 марта 2010

Ваши ответы на 5, 6, 7 и 8 неверны, если мои быстрые следы верны.
ниже след 8 

1: int i, j, pseudo_inner_count = 0, n = 1073741824;
2: 
3: for(i = n; i > 1; i /= 2)
4: {
5:     pseudo_inner_count++;
6:     for(j = 0; j < 50000000; j++);
7: }

Итак, строка 5 является первичной операцией и, следовательно, O (1) совпадает с проверкой и назначением в строке 3. Строка 6 выглядит так, как будто она будет чем-то большим, но поскольку она всегда будет 50000000, это константа время операции O (1), что оставляет нас с этой оболочкой для рассмотрения: 

1: int i, j, pseudo_inner_count = 0, n = 1073741824;
2: 
3: for(i = n; i > 1; i /= 2)
4: {
5: }

Я не делаю чью-то домашнюю работу бесплатно, но на этом я закончу, метод сокращения i - это метод деления на два, означающий, что для выполнения операции log_2 потребуется 1, что даст время выполнения O (log (n))

...