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

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

2、頁(yè)/共48頁(yè)第十頁(yè)，共48頁(yè)。)()(ngnT（3） “平均情況(qngkung)”限界函數(shù)第10頁(yè)/共48頁(yè)第十一頁(yè)，共48頁(yè)。第11頁(yè)/共48頁(yè)第十二頁(yè)，共48頁(yè)。法運(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頁(yè)/共48頁(yè)第十三頁(yè)，共48頁(yè)。第13頁(yè)/共48頁(yè)第十四頁(yè)，共48頁(yè)。第14頁(yè)/共48頁(yè)第十五頁(yè)，共48頁(yè)。始條件中。第二，用數(shù)學(xué)歸納法來證明。第15頁(yè)/共48頁(yè)第十六頁(yè)

3、，共48頁(yè)。第16頁(yè)/共48頁(yè)第十七頁(yè)，共48頁(yè)。（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頁(yè)/共48頁(yè)第十八頁(yè)，共48頁(yè)。bknfnf)/()( 上面形式的在遞推關(guān)系式，一個(gè)規(guī)模為n的問題，每一次遞歸調(diào)用后，都簡(jiǎn)化為n/k規(guī)模的問題，為了方便(fngbin)求解，我們通常設(shè)定：n=km，則，上面的求解過程可簡(jiǎn)化為： f(n)= f(km-1)

4、+b = f(km-2)+2b = = f(k0)+mb = f(1) + blog n 第18頁(yè)/共48頁(yè)第十九頁(yè)，共48頁(yè)。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頁(yè)/共48頁(yè)第二十頁(yè)，共48頁(yè)。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頁(yè)/共48頁(yè)第二十一頁(yè)，共48頁(yè)。39 17 21 34 57 69 84 92 1039 17 2157 69 84 92 10317 2157 6992 10691021第21頁(yè)/共48頁(yè)第二十二頁(yè)，共48頁(yè)。第22頁(yè)/共48頁(yè)第二十三頁(yè)，共48頁(yè)。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頁(yè)/共48頁(yè)第二十四頁(yè)，共48頁(yè)。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頁(yè)/共48頁(yè)第二十五頁(yè)，共48頁(yè)。1)1()2/(11)(nnnTnnT算法的復(fù)雜度有兩部分決定(judng)：遞歸和合并，遞歸的復(fù)雜度是：logn，合并的復(fù)雜度是 n。第25頁(yè)/共48頁(yè)第二十六頁(yè)，共48頁(yè)。)()2/(2)(1)2(nOnTnTT第26頁(yè)/共48頁(yè)第二十七頁(yè)，共48頁(yè)。第27頁(yè)/共48頁(yè)第二十八頁(yè)，共48頁(yè)。不失一般性，設(shè)規(guī)模(gum)為n的問題，每一次有分解為m個(gè)子問題，設(shè)n =mk，則：)()/()(1

8、) 1 (nOmnmTnTT第28頁(yè)/共48頁(yè)第二十九頁(yè)，共48頁(yè)。第29頁(yè)/共48頁(yè)第三十頁(yè)，共48頁(yè)。算法(sun f)的復(fù)雜度有兩部分決定：遞歸和合并，遞歸的復(fù)雜度是：n，合并的復(fù)雜度是 nlogn。)()/()(1)1 (nOmnmTnTT第30頁(yè)/共48頁(yè)第三十一頁(yè)，共48頁(yè)。1) 2/(*3) 2/(11)(2nnnTnnT第31頁(yè)/共48頁(yè)第三十二頁(yè)，共48頁(yè)。所以(suy)：O(n2)第32頁(yè)/共48頁(yè)第三十三頁(yè)，共48頁(yè)。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頁(yè)/共48頁(yè)第三十四頁(yè)，共48頁(yè)。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頁(yè)/共48頁(yè)第三十五頁(yè)，共48頁(yè)。11)()2/(3) 1 ()(nnnOnTOnT第35頁(yè)/共48頁(yè)第三十六頁(yè)，共48頁(yè)。=O(n2)=O(2n)=O(1)=O(logn)=O(n)第36頁(yè)/共48頁(yè)第三十七頁(yè)，共48頁(yè)。定義1 如果存在兩個(gè)正常數(shù)c和n0，對(duì)于所有的nn0，有 |f(n)| c|g(n)| 則記作f(n) = (g(n)O(1) = O(2) 相差的只是(zhsh)常數(shù)因子第37頁(yè)/共48頁(yè)第三十八頁(yè)，共48頁(yè)。設(shè)新機(jī)器用統(tǒng)一算法能解輸入規(guī)模為n1的問題(wnt)，則： t=3*2n1/64=3*2n1-6 所以，n1=n+6第38頁(yè)/共48頁(yè)第三十九頁(yè)，共48頁(yè)。n12=64n2=(8n)2能解規(guī)模(gum)為8n的問題第39頁(yè)/共48頁(yè)第四十頁(yè)，共48頁(yè)。由于(yuy)T(n)是常數(shù)，所以可以解任意規(guī)模的問題。第40頁(yè)/共48頁(yè)第四十一頁(yè)，共48頁(yè)。n第41頁(yè)/共48頁(yè)第四十二頁(yè)，共48頁(yè)。