Сложность этого алгоритма?

-1

В чем сложность func1, если func2 = O (n) и func3 = O (n^2)?Сложность этого алгоритма?

void func1 (int n) { 
    int i, j, k; 
    for (k=0;k<n;k++)   // O(n) 
     printf("%d",k); 
    i=0; 
    while (i<2*n) {   // O(n) 
     for (j=i;j>1;j--) // Not executed 
      for (k=15;k>0;k--) 
       func2(n); 
     for (j=n;j>1;j--) // O(n) 
      func3(n);  // O(n^2) 
     i++; 
    } 
}

Так что это O (N^2) О (п) О (п) + О (п) = тах (О (п^4), О (п)) = O (N^4) ?

Спасибо!

источник

2016-04-11 Trapezera Buscando

Что вы думаете и почему? –

Я получил O (n^4), так как func2 не выполняется, а func3 находится под двумя циклами: большинство стажеров от 2 до n, а другое от 0 до 2n-1. –

'printf ("% d ", k)" is O (log (k)), а не O (1), что делает первый цикл O (log (n!)) = O (n log n), хотя это не имеет никакого значения для общей сложности func1 на этот раз, поскольку в этом первом цикле доминирует второе. –

void func1 (int n) { 
    int i, j, k; 
    for (k=0;k<n;k++)  
     printf("%d",k); 
    i=0; 
    while (i<2*n) {    // O(2*n) = O(n) 
    for (j=i;j>1;j--)   // O(n) 
     for (k=15;k>0;k--)  // O(15) = O(1) 
      func2(n);    // O(n) 
    for (j=n;j>1;j--)   // O(n) 
     func3(n);     // O(n^2) 
    i++; 
    } 
}

Для последовательности найдите максимальное количество шагов.

Как правило, вложенные циклы умножаются, но вам может потребоваться тщательное изучение диапазонов, если они не являются независимыми, убедитесь, что это так (см. Комментарий Пола к примеру).

источник

2016-04-11 00:54:42

O (n^2) O (n) O (n) = O (n^4)? Книга awnser была O (n^3) –

Действительно, какую книгу? @TrapezeraBuscand и как эта книга объясняет ее результат? –

Сложность вложенных циклов не размножается вообще, хотя этот псевдо-метод дает правильный результат. Например, если вы заменили 'i = 0' на' i = 1' и 'i ++' на 'i * = 2', вычисления общей стоимости func2 равны O (n^2), хотя внешний цикл работает' O (log n) 'раз. –

Сложность этого алгоритма?

ответ

Смежные вопросы