Временная сложность вложенности при изменении условия - PullRequest
Новая
       6

Временная сложность вложенности при изменении условия

0 голосов
/ 07 ноября 2018

Я пытаюсь решить сложность этого цикла 

for(int i= 0; i < n; i++) {    
 c = i;    
 while(c > 1){     
  O(1);     
  c = c / 2;     
 }    
}

так как условие while изменяется в каждом цикле, я не знаю, как рассчитать этот странный ряд.

Я имею в виду, если цикл где 

for(int i= 0; i < n; i++) {     
 c = n;     
 while(c > 1){     
  O(1);     
  c = c / 2;     
 }
}

Я знаю, что while имеет сложность O (logn) и повторяется n раз, поэтому сложность будет O (nlogn).

Проблема с предыдущим циклом - "c = i". Поскольку c = i, в первый раз (c = 0) цикл будет воспроизводиться 0 раз, когда c = 1 он будет воспроизводиться снова 0 раз, когда c = 2 будет воспроизводиться 1 раз, затем будет следовать ряд, и это 0, 0, 1, 2, 2, 3, 3 ... (при каждом воспроизведении цикла for)

O (logn) не повторяется n раз, повторяется несколько раз, что я не могу придумать, поэтому я не знаю, как это решить.

1 Ответ

0 голосов
/ 07 ноября 2018

Это требует немного математики. Учитывая, что журнал хорошо определен для a и b: 

log(a) + log(b) = log(ab)

Здесь у вас есть 

log(1) + log(2) +....+ log(n) = log(1*....*n) = log(n!)

Существует математическое приближение для log (n!), А именно 

 log(n!) ~ nlog(n) - n + 1

которые раскрывают O(log(n!)= O(nlog(n))

...