Продолжительность сложность фрагмента кода

Question

Вот фрагмент:

sum1=0; 
    for(i=1;i<=n;i++) 
     for(j=1;j<=n;j++) 
     sum1++ 
sum2=0 
    for(k=1;k<=n;k*=2) 
     for(j=1;j<=k;j++) 
     sum2++ 

Ниже ответ:

2 операторы присваивания - O (1), каждый первый вложенный цикл - O (n2) 2-й вложенный цикл - O (n) Сложность времени выполнения фрагмента кода = O (1) + O (n^2) + O (1) + O (n) = O (n2)

Но вот как Я разработал его:

2 задания: - O (1). Первый вложенный цикл: О (п * п) = O (N^2) Второй вложенный цикл:

Внешние запускает цикл п раз .. Теперь внутренний цикл будет выполнен (1 + 2 + 3 +. .... + (n-1) + n) раз , который дает n (n + 1)/2 = O (n^2)

Общее время работы = O (n^2) + O (n^2) + O (1) = O (N^2)

и да, я сделал некоторые исследования, и я наткнулся на следующее:

в цикле, если индекс прыжков с увеличением количества в каждая итерация имеет сложность l og n.

В этом случае я предполагаю, что второй цикл будет иметь сложность (n-1)/2 * logn ..., которая будет равна O (n * log n).

Я действительно путают со вторым контуром, должен ли он быть O (N) .. O (N^2) или O (NlogN) ..

HELP PLEASE

Answer 1

Поскольку вы K увеличились дважды каждый раз. ваш расчет неверен. Она должна быть (1 + 2 + 4 + .... N/2 + п)

 for(k=1;k<=n;k*=2) 

Таким образом, О (NlogN) является правильным.