時間復(fù)雜解說PPT學(xué)習(xí)教案

1、會計(jì)學(xué)1時間復(fù)雜解說時間復(fù)雜解說第1頁/共48頁第2頁/共48頁2/2/)1(6/)12)(1(2/)1(1111111 nnnnniijniijjkniniij第3頁/共48頁第4頁/共48頁往往是我們最關(guān)注的。第5頁/共48頁第6頁/共48頁第7頁/共48頁第8頁/共48頁（2）下界函數(shù)第9頁/共48頁)()(ngnT（3） “平均情況”限界函數(shù)第10頁/共48頁第11頁/共48頁第12頁/共48頁第13頁/共48頁第14頁/共48頁用數(shù)學(xué)歸納法來證明。第15頁/共48頁第16頁/共48頁（2）反向替換法例如：X(n)=x(n-1)+n 使用所討論的遞推關(guān)系，將x(n-1)表示為x(n-2

2、)得函數(shù)，然后把這個結(jié)果代入原始方程，來把x(n)表示為x(n-2)的函數(shù)。重復(fù)這一過程。X(n)=x(0)+1+2+3+4+5+n=0+1+2+3=4 = n(n+1)/2第17頁/共48頁bknfnf)/()( 上面形式的在遞推關(guān)系式，一個規(guī)模為n的問題，每一次遞歸調(diào)用后，都簡化為n/k規(guī)模的問題，為了方便求解，我們通常設(shè)定：n=km，則，上面的求解過程可簡化為： f(n)= f(km-1)+b = f(km-2)+2b = = f(k0)+mb = f(1) + blog n 第18頁/共48頁int BinSrch(Type A,int i, int n, Type x)/Ai.n是非

3、遞減排列 且 1=i=n; if(n=i) if(x=Ai) return i; else return 0; else int mid=(i+n)/2; if(x=Amid) return mid; -基本操作基本操作 else if(xAmid) return BinSrh(A, mid+1, n, x);遞歸調(diào)用 第19頁/共48頁11nn1)2/(1)(nCnC因?yàn)橐?guī)模每一次遞歸調(diào)用后，縮減為原來的1/2，所以采用換名方法求解，設(shè) n = 2k：C(n) = C(2k)= C(2k-1)+1 = C(2k-2) + 2 = =C(2k-k)+k =C(1) + k = logn+1第2

4、0頁/共48頁39 17 21 34 57 69 84 92 1039 17 2157 69 84 92 10317 2157 6992 10691021第21頁/共48頁第22頁/共48頁int Select(int data,int p,int r,int k) if(pr) return -1; /p不能大于r if(p=r) return datap; /pk) int r1= Select(data,p,s-1,k);-遞歸調(diào)用遞歸調(diào)用 return r1; else /sk int r1=Select(data,s+1,r,k-s);-遞歸調(diào)用遞歸調(diào)用 return r1; 第23

5、頁/共48頁1)1()2/(11)(nnnTnnT因?yàn)槊恳淮我?guī)模都減到原來的1/2，所以用換名的方法設(shè) n = 2k：T(n) = T(n/2) + (n-1) = T(2k-1) + (2k-1) =T(2k-2) + (2k-1-1)+ (2k-1) = =T(2k-k) + (21-1) + +(2k-1-1) +(2k-1) =T(1)+(2k+1-2)-k =2n-logn-1第24頁/共48頁1)1()2/(11)(nnnTnnT算法的復(fù)雜度有兩部分決定：遞歸和合并，遞歸的復(fù)雜度是：logn，合并的復(fù)雜度是 n。第25頁/共48頁)()2/(2)(1)2(nOnTnTT第26頁/共

6、48頁第27頁/共48頁不失一般性，設(shè)規(guī)模為n的問題，每一次有分解為m個子問題，設(shè)n =mk，則：)()/()(1) 1 (nOmnmTnTT第28頁/共48頁第29頁/共48頁算法的復(fù)雜度有兩部分決定：遞歸和合并，遞歸的復(fù)雜度是：n，合并的復(fù)雜度是 nlogn。)()/()(1)1 (nOmnmTnTT第30頁/共48頁1) 2/(*3) 2/(11)(2nnnTnnT第31頁/共48頁所以：O(n2)第32頁/共48頁Recursive_Miltiply(x,y)if n=1if (X=1)and(Y=1) return(1) else return(0) x1 =X的左邊n/2位; x0

7、 =X的右邊n/2位; y1 =Y的左邊n/2位; y0 =Y的右邊n/2位; p = Recursive_Miltiply(x1+x0,y1+y0);遞歸調(diào)用遞歸調(diào)用x1y1 = Recursive_Miltiply(x1,y1);遞歸調(diào)用遞歸調(diào)用x0y0 = Recursive_Miltiply(x0,y0);遞歸調(diào)用遞歸調(diào)用return x1y1*2n + (p-x1y1-x0y0)*2n/2+x0y0;基本操作基本操作第33頁/共48頁11)()2/(3) 1 ()(nnnOnTOnTkkkkikikkkTTTTT3)2(3)2(3)2(3)2(3)2(221設(shè)，n=2k, 用反向替換法對它求解：585.13loglog223)(nnnTn第34頁/共48頁11)()2/(3) 1 ()(nnnOnTOnT第35頁/共48頁=O(n2)=O(2n)=O(1)=O(logn)=O(n)第36頁/共48頁定義1 如果存在兩個正常數(shù)c和n0，對于所有的nn0，有 |f(n)| c|g(n)| 則記作f(n) = (g(n)O(1) = O(2) 相差的只是常數(shù)因子第37頁/共48頁設(shè)新機(jī)器用統(tǒng)一算法能解輸入規(guī)模為n1的問題，則： t=3*2n1/64=3*2n1-6 所以，n1=n+6第38頁/共48頁n12=64n2=(8n)2能解規(guī)模為8n的問題第39頁/共48頁由于T