В чем сложность следующего кода?

Question

В соответствии с этим кодом:

for (int i=1; i<=N; i*=2) 
{ 
    for (int j=1;j<=i;j++) 
    { 
    System.out.println("The value for i is "+i+" and the value for j is "+j); 
    } 
} 

Первый for-loop будет работать log(n) раз, сначала я подумал о 2n-1 для второго for-loop, но он не работает для нечетных чисел.

Любые идеи? :)

Answer 1

Ваш первый цикл получил i как серии:

Первый цикл останавливается, когда последний элемент из этой серии Biger или равно N:

x стенды за сколько раз выполняется первый цикл. Сейчас мы пытаемся найти x:

где

Да, это, как вы говорите:

Первый для цикла будет выполняться журнал (п) раз

Вторые для тела цикла выполняется в виде суммы:

Это является доказательством того, что ваш алгоритм имеет O (п) сложность

Ваша печать происходит 2N-1 раз, если N является одним из: 1, 2, 4, 8, ... , 2^n

---

это поверхностно анализ, но это делает работу.

Answer 2

• Когда i = 1, внутренний цикл будет выполняться 1 раз
• Когда i = 2, внутренний цикл будет выполняться 2 раза
• Когда i = 4, внутренний цикл будет работать в 4 раза
• ...
• Когда i = N, внутренний цикл будет работать N раз

Оператор печати выполняется 1 + ... + N/4 + N/2 + N раз, что является O (n).