第1周绪论第6讲-其他情况的算法分析.pdf

《第1周绪论第6讲-其他情况的算法分析.pdf》由会员分享，可在线阅读，更多相关《第1周绪论第6讲-其他情况的算法分析.pdf（14页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、定义：定义：设设一个算法的输入规模为一个算法的输入规模为n，Dn是所有输入的集合，任一是所有输入的集合，任一 输入输入I Dn，P(I)是是I出现出现的概率，有的概率，有，T(I)是算法在输入是算法在输入I 下的执行时间，则算法的下的执行时间，则算法的平均时间复杂平均时间复杂度度为：为： n DI ITIPnA)()()( n DI IP1)( 例如，例如，10个个110的的整数序列递增整数序列递增排序：排序： n=10 I1=1,2,3,4,5,6,7,8,9,10 I2=2,1,3,4,5,6,7,8,9,10 Im=10,9,8,7,6,5,4,3,2,1 构成构成Dn，P(I)=1/m

2、 所有可能的初始序列有所有可能的初始序列有m个，个，m=10! I Dn 算法的算法的最坏时间复杂最坏时间复杂度度为：为：W(n)=MAXT(I) I Dn 算法的算法的最好时间复杂最好时间复杂度度为：为：B(n)=MINT(I) 一种或几种特殊情况一种或几种特殊情况 【例例1- -6】设计一个算法，求含设计一个算法，求含n个整数元素的序列中前个整数元素的序列中前i （1in）个元素的最大值。并分析算法的平均时间复杂度。）个元素的最大值。并分析算法的平均时间复杂度。 解解：整数序列用数组整数序列用数组a表示表示，前，前i（1in）个个元素为元素为a0.i- -1。 int fun(int a,

3、int n,int i) int j, max=a0; for (j=1;jmax) max=aj; return(max); 解：解：i的取值范围为的取值范围为1n（共（共n种情况），对于种情况），对于求前求前i个元素的个元素的 最大值时，需要元素比较最大值时，需要元素比较(i- -1)- -1+1=i- -1次。在次。在等等概率情况（每种概率情况（每种 情况的概率为情况的概率为1/n）：）： 该算法的该算法的最坏复杂度最坏复杂度：W(n)=O(n)（当（当i=n时）时） 该算法的该算法的最好复杂度最好复杂度：B(n)=O(1)（当（当i=1时）时） = O(n)平均时间复杂度平均时间复杂度

4、 递归算法是指算法中出现调用自己的成分。递归算法是指算法中出现调用自己的成分。 递归算法分析也称为递归算法分析也称为变长时空分析变长时空分析。 非递归算法分析也称为非递归算法分析也称为定长时空分析定长时空分析。 【例例1- -7】 有有如下递归算法如下递归算法： 调用上述算法的语句为调用上述算法的语句为fun(a,n,0)，求其时间复杂度。，求其时间复杂度。 void fun(int a,int n,int k) /数组数组a共有共有n个元素个元素 int i; if (k=n-1) for (i=0;in;i+) /n次次 printf(%dn,ai); else for (i=k;in;i

5、+)/n-k次次 ai=ai+i*i; fun(a,n,k+1); 递归算法递归算法： 错误错误fun(a,n,0)的时间复杂度为的时间复杂度为O(n)。 含一重循环含一重循环 void fun(int a,int n,int k) /数组数组a共有共有n个元素个元素 int i; if (k=n-1) for (i=0;in;i+) /n次次 printf(%dn,ai); else for (i=k;in;i+)/n-k次次 ai=ai+i*i; fun(a,n,k+1); 则则 T(n) = T1(n,0) = n+T1(n,1) = n+(n- -1)+T1(n,2) = = n+(n

6、- -1)+2+T1(n,n- -1) = n+(n- -1)+ +2+n = O(n2) 解：解：设设fun(a,n,0)的执行时间为的执行时间为T(n)，fun(a,n,k)的执行时间为的执行时间为 T1(n,k) T(n) = T1(n,0)。 所以调用所以调用fun(a,n,0)的时间复杂度为的时间复杂度为O(n2)。 T1(n,k) = n当当k=n- -1时时 T1(n,k) = (n- -k)+T1(n,k+1) 其他情况其他情况 由由fun()递归算法可知：递归算法可知： 【例例1-8】有如下递归算法有如下递归算法，分析调用分析调用fun(a,n,0)的空间复杂度的空间复杂度。

7、 void fun(int a,int n,int k) /数组数组a共有共有n个元素个元素 int i; if (k=n-1) for (i=0;in;i+) /n次次 printf(%dn,ai); else for (i=k;in;i+)/n-k次次 ai=ai+i*i; fun(a,n,k+1); 递归算法：递归算法： 错误错误fun(a,n,0)的空间复杂度为的空间复杂度为O(1)。 仅仅定义了一个临时变量仅仅定义了一个临时变量i void fun(int a,int n,int k) /数组数组a共有共有n个元素个元素 int i; if (k=n-1) for (i=0;in;i

8、+) /n次次 printf(%dn,ai); else for (i=k;in;i+)/n-k次次 ai=ai+i*i; fun(a,n,k+1); 解：解：设设fun(a,n,0)的空间为的空间为S(n)，fun(a,n,k)的空间为的空间为S1(n,k) S(n) = S1(n,0)。 则：则： S(n) = S1(n,0) = 1+S1(n,1) = 1+1+S1(n,2) = = 1 + 1 + + 1 = O(n) 所以调用所以调用fun(a,n,0)的空间复杂的空间复杂度度为为O(n)。 S1(n,k) = 1当当k=n- -1时时 S1(k) = 1+S1(n,k+1)其他其他情况情况 由由fun()递归算法可知：递归算法可知： n个1 本章完本章完