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

1、會(huì)計(jì)學(xué)1時(shí)間時(shí)間(shjin)復(fù)雜解說復(fù)雜解說第一頁，共48頁。小，我們總是假設(shè)算法的輸小，我們總是假設(shè)算法的輸入規(guī)模是用大于零的整數(shù)表入規(guī)模是用大于零的整數(shù)表示的，即示的，即n=1,2,3,k, 第1頁/共48頁第二頁，共48頁。第2頁/共48頁第三頁，共48頁。2/2/)1(6/)12)(1(2/)1(1111111 nnnnniijniijjkniniij第3頁/共48頁第四頁，共48頁。第4頁/共48頁第五頁，共48頁。第5頁/共48頁第六頁，共48頁。第6頁/共48頁第七頁，共48頁。第7頁/共48頁第八頁，共48頁。第8頁/共48頁第九頁，共48頁。（2）下界(xi ji)函數(shù)第9

2、頁/共48頁第十頁，共48頁。)()(ngnT（3） “平均情況(qngkung)”限界函數(shù)第10頁/共48頁第十一頁，共48頁。第11頁/共48頁第十二頁，共48頁。法運(yùn)算法運(yùn)算O(2n): 求具有求具有(jyu)n個(gè)元個(gè)元素集合的所有子集的算法素集合的所有子集的算法O(n!): 求具有求具有(jyu)N個(gè)元個(gè)元素的全排列的算法素的全排列的算法優(yōu)優(yōu)-劣劣 O(1)O(2n)O(n) O(n2n): O(n2)O(2n)第12頁/共48頁第十三頁，共48頁。第13頁/共48頁第十四頁，共48頁。第14頁/共48頁第十五頁，共48頁。始條件中。第二，用數(shù)學(xué)歸納法來證明。第15頁/共48頁第十六頁

3、，共48頁。第16頁/共48頁第十七頁，共48頁。（2）反向替換法例如：X(n)=x(n-1)+n 使用所討論的遞推關(guān)系，將x(n-1)表示為x(n-2)得函數(shù)，然后把這個(gè)結(jié)果代入原始(yunsh)方程，來把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頁第十八頁，共48頁。bknfnf)/()( 上面形式的在遞推關(guān)系式，一個(gè)規(guī)模為n的問題，每一次遞歸調(diào)用后，都簡化為n/k規(guī)模的問題，為了方便(fngbin)求解，我們通常設(shè)定：n=km，則，上面的求解過程可簡化為： f(n)= f(km-1)

4、+b = f(km-2)+2b = = f(k0)+mb = f(1) + blog n 第18頁/共48頁第十九頁，共48頁。int BinSrch(Type A,int i, int n, Type x)/Ai.n是非遞減排列(pili) 且 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頁第二十頁，共48頁。11nn1)2

5、/(1)(nCnC因?yàn)橐?guī)模每一次遞歸調(diào)用后，縮減為原來(yunli)的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第20頁/共48頁第二十一頁，共48頁。39 17 21 34 57 69 84 92 1039 17 2157 69 84 92 10317 2157 6992 10691021第21頁/共48頁第二十二頁，共48頁。第22頁/共48頁第二十三頁，共48頁。int Select(int data,int p,int r,int k) if(

6、pr) return -1; /p不能大于r if(p=r) return datap; /pk) int r1= Select(data,p,s-1,k);-遞歸調(diào)用(dioyng) return r1; else /sk int r1=Select(data,s+1,r,k-s);-遞歸調(diào)用(dioyng) return r1; 第23頁/共48頁第二十四頁，共48頁。1)1()2/(11)(nnnTnnT因?yàn)槊恳淮我?guī)模(gum)都減到原來的1/2，所以用換名的方法設(shè) n = 2k：T(n) = T(n/2) + (n-1) = T(2k-1) + (2k-1) =T(2k-2) + (2

7、k-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頁第二十五頁，共48頁。1)1()2/(11)(nnnTnnT算法的復(fù)雜度有兩部分決定(judng)：遞歸和合并，遞歸的復(fù)雜度是：logn，合并的復(fù)雜度是 n。第25頁/共48頁第二十六頁，共48頁。)()2/(2)(1)2(nOnTnTT第26頁/共48頁第二十七頁，共48頁。第27頁/共48頁第二十八頁，共48頁。不失一般性，設(shè)規(guī)模(gum)為n的問題，每一次有分解為m個(gè)子問題，設(shè)n =mk，則：)()/()(1

8、) 1 (nOmnmTnTT第28頁/共48頁第二十九頁，共48頁。第29頁/共48頁第三十頁，共48頁。算法(sun f)的復(fù)雜度有兩部分決定：遞歸和合并，遞歸的復(fù)雜度是：n，合并的復(fù)雜度是 nlogn。)()/()(1)1 (nOmnmTnTT第30頁/共48頁第三十一頁，共48頁。1) 2/(*3) 2/(11)(2nnnTnnT第31頁/共48頁第三十二頁，共48頁。所以(suy)：O(n2)第32頁/共48頁第三十三頁，共48頁。Recursive_Miltiply(x,y)if n=1if (X=1)and(Y=1) return(1) else return(0) x1 =X的左

9、邊(zu bian)n/2位; x0 =X的右邊n/2位; y1 =Y的左邊(zu bian)n/2位; y0 =Y的右邊n/2位; p = Recursive_Miltiply(x1+x0,y1+y0);遞歸調(diào)用x1y1 = Recursive_Miltiply(x1,y1);遞歸調(diào)用x0y0 = Recursive_Miltiply(x0,y0);遞歸調(diào)用return x1y1*2n + (p-x1y1-x0y0)*2n/2+x0y0;基本操作第33頁/共48頁第三十四頁，共48頁。11)()2/(3) 1 ()(nnnOnTOnTkkkkikikkkTTTTT3)2(3)2(3)2(3)

10、2(3)2(221設(shè)，n=2k, 用反向(fn xin)替換法對(duì)它求解：585.13loglog223)(nnnTn第34頁/共48頁第三十五頁，共48頁。11)()2/(3) 1 ()(nnnOnTOnT第35頁/共48頁第三十六頁，共48頁。=O(n2)=O(2n)=O(1)=O(logn)=O(n)第36頁/共48頁第三十七頁，共48頁。定義1 如果存在兩個(gè)正常數(shù)c和n0，對(duì)于所有的nn0，有 |f(n)| c|g(n)| 則記作f(n) = (g(n)O(1) = O(2) 相差的只是(zhsh)常數(shù)因子第37頁/共48頁第三十八頁，共48頁。設(shè)新機(jī)器用統(tǒng)一算法能解輸入規(guī)模為n1的問題(wnt)，則： t=3*2n1/64=3*2n1-6 所以，n1=n+6第38頁/共48頁第三十九頁，共48頁。n12=64n2=(8n)2能解規(guī)模(gum)為8n的問題第39頁/共48頁第四十頁，共48頁。由于(yuy)T(n)是常數(shù)，所以可以解任意規(guī)模的問題。第40頁/共48頁第四十一頁，共48頁。n第41頁/共48頁第四十二頁，共48頁。