求一个算法的运行次

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 是迭代遇到的所有 is 的总和。即当i=k时，s等于1+2+...+k。此总和等于 k(k+1)/2.

在这一步之后需要link这个数量到n并用n表示k得到最终的复杂度。

这是否回答了您的问题？请评论您在哪一步需要更多详细信息。

P.S。这是等差级数求和的一个非常酷的动画证明：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

求一个算法的运行次

Find the running time of an algorithm

iteration

performance

formula

time-complexity