Сложность времени для цикла?

Question

p = 0
for(i=1;p<=n;i++){
 p = p+i;
}

Как я могу проанализировать временную сложность этого цикла? Я читал, что это O (n ^ (1/2)). Но как?

Answer 1

p = 0
for(i=1;p<=n;i++){
 p = p+i;
}

Для каждой итерации вы добавляете 1 нет. выше предыдущего

step 1 : p = p + 1;
step 2 : p = p + 2;
step 3 : p = p + 3;
step 4 : p = p + 4;
.....
.....
step m : p = p + m;

Ваше состояние сравните с n

p<=n

Сумма значений, которые вы добавляете в p, будет равна

1+2+3+.....+m <= n

В математике, уравнение для решения выше суммы будет как

(m * (m + 1))/2 <= n

Итак, окончательная сложность достигает

Answer 2

Как увеличивается р? Сначала мы добавляем 1, затем 2, затем 3 ... затем k.

Итак, на шаге k p = 1 + 2 + 3 + ... + k. формула для этого равна k * (k + 1) / 2. Теперь, сколько шагов необходимо, чтобы достичь n?

Давайте попробуем заменить k на sqrt (2n). Из формулы имеем sqrt (2n) * (sqrt (2n) + 1) / 2. Это равно 2n + sqrt (2n) / 2. Это равно n + некоторой константе. Таким образом, в sqrt (2n) итерациях мы уже достигли p> n. Это дает нам верхнюю границу O (sqrt (2n)), которая совпадает с O (sqrt (n)).