Big O для петель - PullRequest
Новая
       8

Big O для петель

6 голосов
/ 03 октября 2011

У меня был этот вопрос для моего задания на днях, но я все еще не был уверен, прав ли я. 

for(int i =1; i <n; i++)   //n is some size
{             
    for(j=1; j<i; j++)
    {
        int k=1;

        while (k<n)
        {
           k=k+C;   //where C is a constant and >=2
        }
    }
}

Я знаю, что вложенные циклы for - это O (n ^ 2), но я не был уверен с циклом while. Я предполагал, что весь код будет O (n ^ 3).

Ответы [ 4 ]

2 голосов
/ 03 октября 2011

Внутренний цикл буквально O(n/C)=O(n), так что да, в целом это O(n^3) (второй цикл имеет верхнюю границу O(n))

2 голосов
/ 03 октября 2011 
    int k=1;

    while (k<n){
       k=k+C                    //where C is a constant and >=2
    }

Это займет (n-1)/C шагов: напишите u = (k-1) / C. Тогда k = Cu + 1 и утверждение становится 

u=0;
while(u < (n-1)/C) {
    u=u+1
}

Следовательно, цикл while равен O(n) (поскольку C является константой)

РЕДАКТИРОВАТЬ: позвольте мне попытаться объяснить это с другой стороны.

Начните с фиктивной переменной u. Петля 

u=0;
while(u < MAX) {
    u = u+1
}

работает MAX раз.

Когда вы разрешите MAX = (n-1) / C, цикл будет 

u=0;
while(u < (n-1)/C) {
    u=u+1
}

И это работает (n-1)/C раз.

Теперь проверка u < (n-1)/C эквивалентна C*u < n-1 или C*u + 1 < n, поэтому цикл эквивалентен 

u=0;
while(C*u + 1 < n) {
    u=u+1
}

Теперь предположим, что мы переписали этот цикл в терминах переменной k = C * u + 1. Тогда, 

u=0;
k=1; // C * 0 + 1 = 1

Петля выглядит как 

while(C*u + 1 < n) {
while(k < n) {

и внутреннее состояние 

    u=u+1
    k=k+C //C * (u+1) + 1 = C * u + 1 + C = old_k + C

Собираем все вместе: 

    int k=1;

    while (k<n){
       k=k+C
    }

делает (n-1)/C шагов.

1 голос
/ 31 марта 2014

Формально вы можете продолжить, используя следующую методологию (сигма-нотация):

enter image description here

Где a обозначает количество постоянных операций внутри самого внутреннего цикла (a = 1если вы хотите посчитать точное количество итераций).

0 голосов
/ 03 октября 2011

Что ж, вам нужно посмотреть, сколько раз тело цикла while запускается для заданных значений n и C. Например, n равно 10, а C равно 3. Тело будет работать 3 раза: k = 1, k = 4, k = 7. Для n = 100 и C = 2 тело будет бегать 50 раз: k = 1,3,5,7,9, ..., 91,93,95,97,99. Это вопрос подсчета C до n. Вы должны быть в состоянии рассчитать сложность Big-O по этой подсказке.

...