章绪论讲-其他情况算法分析.pptx

1.4其他情况的算法分析定义：设一个算法的输入规模为n，Dn是所有输入的集合，任一输入I∈Dn，P(I)是I出现的概率，有，T(I)是算法在输入I下的执行时间，则算法的平均时间复杂度为：1.4.1最好、最坏和平均时间复杂度分析1/14

例如，10个1～10的整数序列递增排序：n=10I1={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所有可能的初始序列有m个，m=10!2/14

I∈Dn算法的最坏时间复杂度为：W(n)=MAX{T(I)}I∈Dn算法的最好时间复杂度为：B(n)=MIN{T(I)}一种或几种特殊情况3/14

【例1-8】设计一个算法，求含n个整数元素的序列中前i（1≤i≤n）个元素的最大值。并分析算法的平均时间复杂度。解：整数序列用数组a表示，前i（1≤i≤n）个元素为a[0..i-1]。intfun(inta[]，intn，inti){ intj，max=a[0]; for(j=1;j=i-1;j++) if(a[j]max)max=a[j]; return(max);}4/14

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

1.4.2递归算法的时空复杂度分析递归算法是指算法中出现调用自己的成分。递归算法分析也称为变长时空分析。非递归算法分析也称为定长时空分析。6/14

【例1-9】有如下递归算法：1、递归算法的时间复杂度分析调用上述算法的语句为fun(a，n，0)，求其时间复杂度。voidfun(inta[]，intn，intk)//数组a共有n个元素{inti;if(k==n-1)for(i=0;in;i++)//n次 printf(%d\n，a[i]);else{for(i=k;in;i++)//n-k次 a[i]=a[i]+i*i; fun(a，n，k+1);}}7/14

voidfun(inta[]，intn，intk)//数组a共有n个元素{inti;if(k==n-1)for(i=0;in;i++)//n次 printf(%d\n，a[i]);else{for(i=k;in;i++)//n-k次 a[i]=a[i]+i*i; fun(a，n，k+1);}}递归算法：错误fun(a，n，0)的时间复杂度为O(n)。含一重循环8/14

则T(n)=T1(n，0)=n+T1(n，1)=n+(n-1)+T1(n，2)=…=n+(n-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)。9/14T1(n，k)=n 当k=n-1时T1(n，k)=(n-k)+T1(n，k+1) 其他情况由fun()递归算法可知：

voidfun(inta[]，intn，intk)//数组a共有n个元素{inti;if(k==n-1) for(i=0;in;i++)//n次 printf(%d\n，a[i]);else{for(i=k;in;i++)//n-k次 a[i]=a[i]+i*i; fun(a，n，k+1);}}【例1-11】有如下递归算法，分析调用fun(a，n，0)的空间复杂度。2、递归算法的空间复杂度分析10/14

voidfun(inta[]，