Найти время работы алгоритма

Question

Я смотрел видео на YouTube по анализу сложности итеративных программ по времени: https://www.youtube.com/watch?v=FEnwM-iDb2g

И я не могу понять, как он рассчитал, что происходит со строкой 5. Ответ k (k + 1) /2.Просто интересно, есть ли определенные шаги, которым я могу следовать, или способы мышления, чтобы понять эту формулу.Я знаю, что s это сумма предыдущих чисел i.Например, i = 1, 2. Тогда s = 3. Или, если i = 1, 2, 3, то s = 6.

Но я просто не знаю, как составить формулу для этогосамостоятельно.

A(){  
i=1;          //1
s=1;          //2
while(s<=n){  //3 Value of n could be any positive integer.
  i++;        //4
  s=s+i;      //5
  print("hello");  //6
  }
}

Answer 1

Вопрос в следующем: когда цикл while завершится.Скажем, это закончится на k й итерации.То есть когда i=k оно прекратится.Как вы сказали, s - это сумма всех i s, с которыми столкнулась итерация.То есть, когда i=k, s равно 1+2+...+k.Эта сумма равна k(k+1)/2.

. После этого шага нужно связать это количество с n и выразить k в терминах n, чтобы получить окончательную сложность.

Это отвечает на ваш вопрос?Пожалуйста, прокомментируйте, на каком шаге вы хотите больше деталей.

PS Вот действительно классное анимированное доказательство суммирования арифметической прогрессии: https://upload.wikimedia.org/wikipedia/commons/2/28/Animated_proof_for_the_formula_giving_the_sum_of_the_first_integers_1%2B2%2B...%2Bn.gif