(9)--第1章绪论第5讲-计算时间复杂度示例.pdf

【示例-1】分析以下算法的时间复杂度。

voidMATMulti(intn,a[][N],b[][N],intc[][N])

{R

inti,j;Z

for(i=0;in;i++)L//①

for(j=0;jn;j++)//②

-

{c[i][j]=0;U//③

for(k=0;kn;k++)//④

D

c[i][j]=c[i][j]+a[i][k]*b[k][j];//⑤

}Q

}

解法1：从求算法中所有语句的频度来分析算

法时间复杂度。

语句①的执行频度为n+1（注意in判断语句需执行

n+1次R

语句②的执行频度为n(n+1)Z

语句③的执行频度为n2L

2

语句④的执行频度为n(n+1)-

语句⑤的执行频度为n3

U

32

f(n)=2n+3n+2n+1

D

3

T(n)=O(n)Q

解法2：从算法中基本运算的频度来分析算法

时间复杂度。R

基本运算是语句⑤

其频度为n3Z

L

3

T(n)=O(n)-

U

结论：从中看到，两种方法的结果相同，而第二种

D

方法更加简洁。Q

【示例-2】给出以下算法的时间复杂度。

voidfunc(intn)

{R

inti=1,k=100;Z

while(i=n)L

{k++;-