算法的时间复杂度如何计算?
来源:百度知道 编辑:UC知道 时间:2024/09/13 02:56:15
Sum1( int n )
{ int p=1, sum=0, m ;
for (m=1; m<=n; m++)
{ p*=m ; sum+=p ; }
return (sum) ;
}
⑵
Sum2( int n )
{ int sum=0, m, t ;
for (m=1; m<=n; m++)
{ p=1 ;
for (t=1; t<=m; t++) p*=t ;
sum+=p ;
}
return (sum) ;
}
⑶ 递归函数
fact( int n )
{ if (n<=1) return(1) ;
else return( n*fact(n-1)) ;
}
老师出的题,实在是不知从何下手!另,请大大们介绍一些关于算法的书,现在在上《数据结构与算法》,老师讲得飞快,一些细节根本没弄懂,在线等!谢谢!
关于时间复杂度的计算是按照运算次数来进行的,比如1题:
Sum1( int n )
{ int p=1, sum=0, m ; //1次
for (m=1; m<=n; m++) //n+1次
{ p*=m ; //n次
sum+=p ; } //n次
return (sum) ; //1次
}
最后总的次数为
1+(n+1)+n+n+1+1=3n+3
所以时间复杂度f(o)=n;(时间复杂度只管n的最高次方,不管他的系数和表达式中的常量)
其余的一样,不明白的可以来问我
一个算法花费的时间与算法中语句的执行次数成正比例,时间复杂度一般用O(f(x))表示.
f(x)在简单程序中就是看有几个for循环,然后看看再它的判断语句,就是看看它执行了几次,f(x)=“执行的次数”。
像题中的(1)有一个for循环执行次数为n次,所以f(x)=n,时间复杂度就为O(n)
(2)有两个for循环执行次数为n*n,即n的平方,所以f(x)=n的平方,时间复杂度就是O(n的平方)。
(3)是递归,它也执行了n次所以它的时间复杂度就是O(n).
不过要注意时间复杂度的f(x)在有限次时就用具体数值表示,无限次时就用n,n的平方,log以2为底n的对数,其实很简单就是看n的最高次方,看n的最高次方等于几,f(x)就等于几。
求解算法的时间复杂度的具体步骤是:
⑴ 找出算法中的基本语句;
算法中执行次数最多的那条语句就是基本语句,通常是最内层循环的循环体。
⑵ 计算基本语句的执行次数的数量级;
只需计算基本语句执行次数的数量级,这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可,可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析,并且使注意力集中在最重要的一点上:增长率。
⑶ 用大Ο记号表示算法的时间性能。
将基本语句执行次数的数量级放入大Ο记号中。
如果算法中包含嵌套的循环,则基本语句通常是最内层的循环体,如果算法中包含并列的循环,则将并列循环的时间复杂度相加。例如: