Запутался в обозначении Big-O - PullRequest
Новая
       11

Запутался в обозначении Big-O

2 голосов
/ 10 февраля 2012

Хорошо, у меня есть быстрый вопрос ко всем программистам, которые предпочитают простой вопрос.

Для моего класса по информатике II мы перебираем нотацию Big-Oh, и я получил большую ее частьвниз, но я все еще путаюсь с некоторыми из семантики примеров.

Все здесь написано на Java.

Мой профессор дал нам эти примеры в классе, но моя удача, я нене запишите ответы.

а) 

int count = 0; 
    for (int i = 1; i <= n; i++) 
        for (int j = n; j > 1; j-­--­-) 
            for (int k = 1; k < n; k = k + 2) 
                count++;

б) 

int count = 0; 
for (int i = 1; i <= n; i++) 
    for (int j = n; j > 1; j-­--­-) 
        for (int k = 1; k < 1000; k = k + 2) 
            count++;

в) 

int count = 0; 
    for (int i = 1; i <= 1000000; i++) 
        for (int j = i; j > 500; j-­--­-) 
            for (int k = 1; k < 10500; k = k + 2) 
                count++;

г) 

int count = 0; 
int j = 1; 
for (int i = 1; i < n; i++) { 
        while (j < n) { 
            j++;
            count++; 
        } 
        j = 1; 
    }

e) 

int count = 0; 
int i = n; 
while (i > 1) 
{ 
    count++; i = i / 2; 
}

Хорошо, вот мои ответы / мыслительные процессы:

a) N * N * (N / 2) = N ^ 3 /2, Все упрощается до O (N ^ 3) нотации

b) N * N * 500, Все упрощается до O (N ^ 2)

c) Это тот, который яЯ запутался в том, что у вас есть три цикла for, но все повторяются точное количество раз.Мое предположение здесь O (1), но я понятия не имею ...

d) N * N = N ^ 2, поэтому O (N ^ 2)

e) Делится нанаполовину каждый раз, так что log (n) = O (log (n)) [оба основания 2]

Так может ли кто-нибудь проверить мой мыслительный процесс и посмотреть, пропускаю ли я что-нибудь?Заранее большое спасибо!

Ответы [ 2 ]

1 голос
/ 10 февраля 2012

Да (C) это O (1), потому что это все константы.

0 голосов
/ 10 февраля 2012

Во всех этих примерах count увеличивается один раз для каждой рабочей единицы. Если вы можете выяснить отношения между count и n, то вы знаете асимптотический порядок программы.

Хорошо, что ты все уладил. Следующим шагом является проверка ваших расчетов в реальности. Запустите код для различных значений n, распечатайте count и проверьте свою работу на предмет реальных данных.

...