Определение скорости роста Big-O этой функции

Я не могу определить, как определить скорость роста функций такого типа.

void A(int n){
 int i=1, s=1;
 while(s<=n){
   i++;
   s=s+i;
   cout<<"hi";
   }
}

Дано, что это O (sqrt (n)), но я не могу понять, как это сделать?


math time-complexity big-o asymptotic-complexity
person conquester    schedule 02.03.2016    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Если вы посмотрите на значения s на каждой итерации, вы увидите, что они равны 1, 3, 6, 10, 15 и т. д. Эти числа называются треугольными числами и представляют собой числа вида k(k+1) /2 (это обычно доказывается как упражнение по индукции.)

Цикл останавливается, как только s превышает n. На итерации k значение s равно k(k+1)/2, поэтому вы можете подсчитать количество итераций, найдя k в k(k+1)/2. Попробуйте сделать это и посмотреть, что вы найдете. Это объясняет квадратный корень?

person templatetypedef    schedule 02.03.2016
comment
Спасибо. Это помогло. - person conquester; 02.03.2016