Какова временная сложность этого вопроса? - PullRequest
Новая
       61

Какова временная сложность этого вопроса?

0 голосов
/ 21 февраля 2020

Какова временная сложность этого кода? 

int count=0;

for(int I=N;I>0;I=I/2)

{

for(int j=0;j<I;j++)

   {

      count=count+1;

    }

}

Пожалуйста, объясните это ясно

1 Ответ

2 голосов
/ 21 февраля 2020

Внутренний l oop делает n итераций, затем n / 2, затем n / 4 и т. Д. c. 

i =n   n/2      n/4    n/8  ....................logn times

j=n     n/2     n/4    n/8 ...........logn tmes

T(n) = n+ n/2 + n/4 + n/8 + ...........logn time
       = n(1+ 1/2 + 1/4 + .............logn times) Decreasing GP
     =O(n)

Следовательно,

Сложность времени составляет O(n)

Чтобы узнать больше о серии Geometri c, см. Этот документ

Здесь можно взять, например:

LET n = 10

изначально: i = 10 (первый l oop) 

           j = 0 < 10(i) so it will loop from 0 to 9 times

СЕЙЧАС ПОСЛЕ ГЛАВНОГО L OOP ПРОХОДИТ НА ЭТОМ МЕСТО 

i /= 2

SO значение i = 5 (первая l oop) 2 итерации.

на этот раз j будет работать с j = 0 <5 (i), поэтому будет l oop от 0 до 5 раз </p>

каждый раз, когда значение i будет делиться на 2, и аналогично для соответствующего значения j будет повторяться от 0 до i / 2 раза.

, поэтому T(n) = O(n + n/2 + n/4 + … 1) = O(n) для j (это только для итерации j) 

i               j

10           0-9 times

5              0 - 4 times

2             0 - 1 times

аналогично значение j, которое изначально было n, т.е. 10 уменьшается на порядок при n / 2, образуя GP, и, таким образом, мы получаем O (n)

...