搜索
首页 电脑/网络 程序设计

算法时间复杂度

为什么int i=-1,s=0;while(s<n){i=i+2;s=s+i;}空间复杂度为 n的开平

全部回答

2012-09-09

0 0

i是一等差数列,s为等差数列和,若数列有m项,则s=m^2,因s<n,所以循环要重复sqrt(n)次

2012-09-09

113 0

    本算法只有一个循环,要求出其时间复杂度,只要求出这个循环的循环体的执行次数就行了。 第1次循环,i更新为1,s更新为1。 第2次循环,i更新为3,s更新为1+3=4。
   第3次循环,i更新为5,s更新为1+3+5=9。 。。。。。。 假设一共执行了x次循环,那么第x次循环,i更新为(2x-1),s更新为1+3+5+。  。。+(2x-1)=x^2。
  
   执行完x次循环后,循环条件不再成立,即s>=n,即x^2>=n。注意x是满足该不等式的最小整数,则x为n^(1/2)向上取整。 因此,该算法的时间复杂度为O(n^(1/2))。

类似问题换一批

热点推荐

热度TOP

相关推荐
加载中...

热点搜索 换一换

电脑/网络
程序设计
电脑装机
操作系统/系统故障
硬件
笔记本电脑
百度
互联网
反病毒
软件
程序设计
程序设计
数据库
C/C++
VB
JAVA相关
C#/.NET
VC++
汇编语言
其他编程语言
举报
举报原因(必选):
取消确定举报