Какова сложность этих трех циклов?

Question

Наличие:

• входной массив A[1...n]
• N длина A

Алгоритм:

for(int i=N; i>0; i--) { // Loop 1 
    for(int j=1; j<N; j=j*2) { // Loop 2 
     for(int k=0; k<j; k++) { // Loop 3 
      // constant number of operations 
     } 
    } 
} 

Я знаю, что петля 1 имеет O(N) временную сложность.

For loop 2 Я бы сказал, что временная сложность O(logN).

В чем сложность для цикла и 3 (и 2, если я ошибаюсь) и для алгоритма?

Answer 1

O (N^2)

Из-за взаимозависимостью j и k (в k<j) вы не можете рассмотреть loop2 и Loop3 отдельно. Пусть N=2^m, для простоты расчета. Итак, j будет 1, 2, 4, ..., 2^(m-1), а loop3 выполняет j раз каждый раз, когда он будет достигнут. Таким образом, комбинированный loop2 и Loop3 выполняет

1 + 2 + 4 + ... + 2^(m-1) 
= 2^0 + 2^1 + 2^2 + ... + 2^(m-1) 

Это Geometric Progression, и равно 2^m - 1 = N - 1, который является O (N). Теперь, бросая в loop1, O (N), и получим O (N^2).

Edit:

Вот Perl код, который я побежал, чтобы проверить эту

print "N\tExpected\tCounted\n"; 

for my $N (10, 100, 1024, 8192) 
{ 
    my $count = 0; 
    for(my $i=$N; $i>0; $i--) 
    { 
     for(my $j=1; $j<$N; $j*=2) 
     { 
      for(my $k=0; $k<$j; $k++) 
      { 
       $count++; 
      } 
     } 
    } 
    my $expected_count = $N*$N - $N; 
    print "$N\t$expected_count\t$count\n"; 
} 

И вывод:

N  Expected  Counted 
10  90    150 
100  9900   12700 
1024 1047552   1047552 
8192 67100672  67100672 

Обратите внимание, что мы не попали в ожидаемой точности, если только N=2^m ,

Answer 2

Для к, цикл выполняется 2, 4, ..., N или N-1 раз, в зависимости от того, N является четным или нечетным, так что временная сложность для трех циклов представляет собой О (п LOGN п).

Редактировать: Thanks for Degustaf. Я испортил его и обнаружил, что цикл k зависит от цикла j, поэтому сложность времени для цикла (j) - max (O (n), O (logn)) = O (n).

Edit Again: Рассмотрим цикл j и цикл k в целом, он выполняет 2 + 4 + ... + N раз, а количество элементов - logN. Сложность времени для цикла j и цикла k - это то, что пишет Degustaf: O (N).

Причина, по которой я думаю, max (O (n), O (logn)): При достижении точки, где цикл k выполняется N раз, цикл for j выполнил logN-1 раз. Во время предыдущих исполнений время выполнения k можно считать намного меньшим, как константа, такая как N/2, N/4 .., 2. Таким образом, последний цикл N-times k считается исполняемым после того, как цикл j выполнен для (logN-1) раз.