1算法概述.ppt

（4）指数函数 对于正整数m,n和实数a0: a0=1; a1=a ; a-1=1/a ; (am)n = amn ; (am)n = (an)m ; aman = am+n ; a1 ? an为单调递增函数; a1 ? ? nb = o(an) ex ? 1+x; |x| ?1 ? 1+x ? ex ? 1+x+x2 ; ex = 1+x+ ?(x2), as x?0; （5）对数函数 log n = log2n; lg n = log10n; ln n = logen; logkn = (log n)kl; log log n = log(log n); for a0,b0,c0 （5）对数函数 |x| ?1 ? for x -1, for any a 0, , ? logbn = o(na) （5）对数函数 （6）阶层函数 Stirling’s approximation （6）阶层函数 算法分析中常见的复杂性函数 小规模数据 中等规模数据 算法分析示例（一） 例1-8：顺序有哪些信誉好的足球投注网站算法 templateclass Type int seqSearch(Type *a, int n, Type k) { for (int i=1;i=n;i++) if (a[i]==k) return i; return 0; } （1）Tmax(n) = max{ T(I) | size(I)=n }=O(n) （2）Tmin(n) = min{ T(I) | size(I)=n }=O(1) （3）在平均情况下，假设： 有哪些信誉好的足球投注网站成功的概率为p ( 0 ? p ? 1 )； 在数组的每个位置i ( 0 ? i n )有哪些信誉好的足球投注网站成功的概率相同，均为p/n 算法分析的基本法则 非递归算法： （1）for / while 循环 循环体内计算时间*循环次数； （2）嵌套循环 循环体内计算时间*所有循环次数； （3）顺序语句 各语句计算时间相加； （4）if-else语句 if语句计算时间和else语句计算时间的较大者。 算法分析的基本法则 递归算法： （1）展开法 （2）母函数法 令G(x)=a0+a1x+a2x2+…… 称G(x)为a0、a1、a2、……的母函数。 递归算法分析示例 例1-9 int fact (int n) { if (n == 0) return 1; return n*fact(n-1); } 递归算法分析示例 用展开法求解 T(n)=T(n-1)+1 =(T(n-2)+1)+1=T(n-2)+2 =(T(n-3)+1)+2=T(n-3)+3 …………………… =(T(n-n)+1)+(n-1)=T(0)+n=n 所以， 例1-10 templateclass Type int BinarySearch(Type a[], const Type x, int l, int h){ if (l h) return o; else { int m = (l+h)/2; if (x == a[m]) return m; else if (x a[m]) return BinarySearch(a,x,l, m-1); elser BinarySearch( a, x, m+1, h); } } 递归算法分析示例 其中， n:判定树的深度, 树中的结点数为 N=2n f0=1 fn=1+fn-1 令G(x)=f0+f1x+f2x2+…… (1-x)G(x)= f0+f1x+f2x2+…… - (f0x+f1x2+f2x3+…… ) = f0+(f1-f0)x+(f2-f1)x2+…… =1+x+x2+…….. =1/(1-x) G(x)=1/(1-x)2=1+2x+3x2+……(n+1)xn+…… fn=n+1=log2N+1=O(log2N) （n:判定树的深度, 树中的结点数为 N=2n , 则 n=log