Анализ сложности метода printParty - PullRequest
Новая
       8

Анализ сложности метода printParty

1 голос
/ 09 апреля 2020 
void printParty(int N) {
   for (int i = 1; i <= N; i *= 2) {
      for (int j = 0; j < i; j += 1) {
         System.out.println("hello");
      }
   }
}

Я вроде получаю, что сложность этого кода равна N, но хотелось бы получить больше разъяснений.

Также у меня была еще одна мысль, которая была 

void printParty(int N) {
   for (int i = 1; i <= N; i++) {
      for (int j = 0; j < i; j *= 2) {
          System.out.println("hello");
      }
   }
}

Я думаю, что последний код фрагмент будет иметь сложность NlogN .... Мой друг говорит, что это то же самое, что и выше.

Можете ли вы помочь мне визуализировать это.

1 Ответ

0 голосов
/ 09 апреля 2020

tl; dr: Вы правы в обоих случаях. Первый код O(n). Второй - O(nlogn).

Ваш друг ошибается, потому что он не понимает, что первый код имеет экспоненциальный спад, а второй - нет, что очень важно при анализе сложности.

Подробные объяснения ниже.

Первый код: 

For i = 1  -> j runs 1 times
For i = 2 -> j runs 2 times
For i = 4 -> j runs 4 times
...
for i = 2^k -> j runs 2^k times.

Это означает, что сложность первого кода: 

1 + 2 + 4 + ... + 2^k + ... + 2^(logn)

Это Geometri c серия с: 

a = 1
r = 2
N = logn + 1

Сумма геометрии c серии задается как: 

a(1-r^N)/(1-r) =
1 * (1-2^(logn+1))/(1-2) = 1*(2^(logn+1) - 1) = 2*2^logn - 1 = 2n - 1

И это легко увидеть, что это в O(n).

Второй код: 

For i = 1 -> j runs log(1) times
For i = 2 -> j runs log(2) times
For i = 3 -> j runs log(3) times
....
For i = k -> j runs log(k) times

Если мы сложим это, мы получим 

log(1) + log(2) + log(3) + ... + log(k) + log(n)

Это совершенно другое от предыдущего. Нет распада геометрии c, поэтому сложность не линейна.

Простой способ увидеть это: 

log(1) + log(2) + log(3) + ... + log(k) + log(n) >
> log(n/2) + log(n/2 + 1) + log(n/2 + 2) + ... + log(n/2 + n/2) >
> n/2 * log(n/2) >=
>= n/2 * log(n) - n/2*log(2)

Поскольку это O(nlogn), сложность этого кода в O(nlogn)

(Другой способ показать это, перейдя к log(n!), который известен O(nlogn))

...