查找算法的运行时间
查找算法的运行时间
提问于 2019-02-12 03:10:47
我在youtube上看了一个关于迭代程序的时间复杂性分析的视频：https://www.youtube.com/watch?v=FEnwM-iDb2g
我不知道他是如何计算出第五行发生了什么。答案是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
}
}回答 1
Stack Overflow用户
回答已采纳
发布于 2019-02-12 03:35:15
问题是：while循环什么时候会终止。假设它将在第k次迭代时终止。也就是说，当使用i=k时，它将终止。正如您所说，s是迭代遇到的所有is的总和。也就是说，当i=k，s等于1+2+...+k。这个和等于k(k+1)/2。
在这一步之后，需要将这个量链接到n，并用n表示k，以获得最终的复杂度。
这回答了你的问题吗？请在您想要更多详细信息的步骤中提出意见。
附注:这是一个非常酷的算术级数求和的动画证明：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
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/54637484
复制相关文章
相似问题
腾讯云开发者
