Question

分析以下程序段的时间复杂度，请说明分析的理由或原因。

⑴
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)) ;
}

Answer 1

一、O(n) : n次循环内执行两条命令， 总计2*n忽略常数则O(n)
二、O(n^2) : n次循环内， 第i次循环执行i条命令， 则时间复杂度为O(1+2+3..+n)， 则为O(n*(n+1)/2)忽略常数为O(n^2)
三、O(n) : 在栈内从n递归到1需要递归n层， 每层执行一次乘法则为O(n)

程序设计是给出解决特定问题程序的过程，是软件构造活动中的重要组成部分。程序设计往往以某种程序设计语言为工具，给出这种语言下的程序。程序设计过程应当包括分析、设计、编码、测试、排错等不同阶段。专业的程序设计人员常被称为程序员。
任何设计活动都是在各种约束条件和相互矛盾的需求之间寻求一种平衡，程序设计也不例外。在计算机技术发展的早期，由于机器资源比较昂贵，程序的时间和空间代价往往是设计关心的主要因素;随着硬件技术的飞速发展和软件规模的日益庞大，程序的结构、可维护性、复用性、可扩展性等因素日益重要。

Answer 2

一、O(n) : n次循环内执行两条命令， 总计2*n忽略常数则O(n)
二、O(n^2) : n次循环内， 第i次循环执行i条命令， 则时间复杂度为O(1+2+3..+n)， 则为O(n*(n+1)/2)忽略常数为O(n^2)
三、O(n) : 在栈内从n递归到1需要递归n层， 每层执行一次乘法则为O(n)