Сложность алгоритма с изменением вложенного цикла каждый раз - PullRequest
Новая
       17

Сложность алгоритма с изменением вложенного цикла каждый раз

1 голос
/ 22 октября 2019

Я должен рассказать о сложности обоих следующих алгоритмов: 

for ( i=1; i < n; i *= 2 ) {
  for ( j = n; j > 0; j /= 2 ) {
    for ( k = j; k < n; k += 2 ) {
      sum += (i + j * k );
    }
  }
}

for( int i = n; i > 0; i-- ) {
  for( int j = 1; j < n; j *= 2 ) {
    for( int k = 0; k < j; k++ ) {
       ... // some operation
    }
  }
}

В первом примере я знаю, что сложность внешнего и среднего циклов - log (n), но яне знаю, как вычислить сложность для внутренней, как инициализация изменения k на итерации

Для второй, очевидно, сложность равна n ^ 2, но я действительно не понимаю, почему

1 Ответ

3 голосов
/ 22 октября 2019

Как вы сказали, внешний цикл равен log(n), а его параметр i не используется во внутренних циклах. Для двух других внутренних циклов: 

 value of j    iteration number of the most inner loop
 j = n;        k: 0 
 j = n/2;      k: (n - n/2)/2
 j = n/4;      k: (n-n/4)/2

Следовательно, сумма равна ((1-1/2) + (1-1/4) + (1-1/8) + ... + (1-1/2^log(n)))n/2 = (log(n) - c) * n/2 = Theta(n log(n)). Следовательно, общая сложность составляет n (log(n))^2.

...