2010-2011-2《算法分析》ppt-5變治法.ppt

變治法,基本思想,變換！ （1）把問題的實(shí)例變得更容易求解。 （2）對實(shí)例進(jìn)行求解。 主要類型： （1）實(shí)例簡化 （2）改變表現(xiàn) （3）問題轉(zhuǎn)化,預(yù)排序,在問題求解之前，先進(jìn)行排序，然后在求解問題。 例1 檢驗(yàn)數(shù)組中元素的唯一性 （1）蠻力法 ，掃描統(tǒng)計，O(n2) （2）先排序，再掃描統(tǒng)計，O(nlogn),預(yù)排序,例2 模式統(tǒng)計 在一個給定的序列中找到出現(xiàn)次數(shù)最多的一個模式。 比如：英文單詞 （1）蠻力法 ，掃描統(tǒng)計，O(n2) （2）先排序，再掃描統(tǒng)計，O(nlogn),預(yù)排序,例3 查找問題： 在一個數(shù)組中是否存在某個給定的數(shù)。 （1）蠻力法，O(n) （2）先排序，后查找， 排序：O(nlogn)，查找：O(log2n) 合計：O(nlogn),高斯消去法,二元聯(lián)立方程： a11x+a12y=b1 a21x+a22y=b2 a11x+a12y=b1 (a21x+a22y)*(a11/a21)=b2*(a11/a21) a11x+a12y=b1 a11x +(a22 * a11/a21) y=b2*(a11/a21),高斯消去法,一般的n個方程的n元聯(lián)立方程組： a11x1+ a12x2 + + a1nxn = b1 a21x1+ a22x2 + + a2nxn = b2 an1x1+ an2x2 + + annxn = bn,高斯消去法,a11x1+ a12x2 + + a1nxn = b1 a22x2 + + a2nxn = b2 annxn = bn,高斯消去法,初等變換： （1）交換方程組中兩個方程的位置 （2）把一個方程替換為它的非零倍。 （3）把一個方程替換為它和另一個方程倍 數(shù)之間的和或差。 舉例：p156,高斯消去法,GaussElimination(A1n,1n,b1n) for j=1 to n Aj,n+1=bj for i=1 to n-1 for j=i+1 to n for k=i to n+1 Aj,k=Aj,k-AI,k*Aj,i/Ai, I ,高斯消去法,上面代碼的問題： （1） 可能有系數(shù)是0 （2）最內(nèi)的循環(huán)存在重復(fù)計算現(xiàn)象，效率低。 （3）誤差累計，有除法，計算機(jī)只能表示小數(shù)點(diǎn)后面的有限位數(shù),BetterGaussElimination(A1n,1n,b1n) for i=1 to n Ai,n+1=bi for i=1 to n-1 pivotrow=i for j=i+1 to n if |Aj,i|Apivotrow,i| pivotrow=j for k=i to n+1 swap(Ai,k,Apivotrow,k) for j=i+1 to n temp=Ai,k/Ai,i for k=i to n+1 Aj,k=Aj,k-Ai,k*temp ,高斯消去法,時間復(fù)雜度：O(n3) 其他應(yīng)用： （1）LU分解 （2）計算矩陣的逆 （3）計算矩陣的行列式,平衡查找樹,AV L樹： G.M.Adelson-Velsky 和E.M.Landis 定義：一棵AVL樹是一棵二叉查找樹，其中每個節(jié)點(diǎn)的平衡因子定義為該節(jié)點(diǎn)左子樹和右子樹的高度差，這個平衡因子要么是0，要么是+1，或者-1 P163,AV L樹的調(diào)整,（1）右單轉(zhuǎn) （2）左單轉(zhuǎn) （3）左右雙轉(zhuǎn) （4）右左雙轉(zhuǎn) P164,排序,分析排序！,排序的時間復(fù)雜度分析,排序的最好復(fù)雜度為什么是：O(n log n)? 有3個互不相等元素組成的序列： k1，k2，k3 對此3個元素進(jìn)行排序，唯一的方法是兩兩進(jìn)行比較。 比較的結(jié)果兩種：大于，小于。,排序的時間復(fù)雜度分析,兩兩比較結(jié)果，形成一顆比較二叉樹，二叉樹的高度就是比較的次數(shù)。,排序的時間復(fù)雜度分析,因?yàn)閗1，k2，k3互不相等，它們之間只可能有下列6種關(guān)系：k1k2k3；k1 k3 k2；k3k1k2；k2k1k3；k2k3 k1；k3k2k1 為什么是6種結(jié)果？N個元素是幾種結(jié)果？,排序的時間復(fù)雜度分析,二叉樹的性質(zhì)：葉子數(shù)量（記為U）和樹高度(記為H)的關(guān)系。 H=log 2 U 就是說：有U個葉子的二叉樹至少有H 高度。 而比較二叉數(shù)的葉子數(shù)為 : N! 所以它的高度至少是: log 2 N!,排序的時間復(fù)雜度分析,建立一個模型：即有一個含有m= n!個元素的集合A ，甲從中任取一個，讓乙來猜，但允許乙提出k個“是”或“非”問題。問在最壞情況下k應(yīng)該是多少？ 乙提出第1個“是”或“非”問題，可將集合A分為A1（1）和A2（1）兩個子集合，其中必有一個集合（設(shè)為A1（1） ），它包含的元素個數(shù)（用A1（1）來表示）不少于，即 A1（1） m/2,排序的時間復(fù)雜度分析,若甲所取的元素正好在A1（1），乙提出第2個“是”或“非”問題后將集合A1（1）分為A2（1）和A2（2），其中之一設(shè)為A2（1）有 A1（2）A1（1） m /2 2 依此類推有 A1（k） m /2 k k必須足夠大，使得 m / 2 k 1,排序的時間復(fù)雜度分析,則已可在最壞情況下通過k次提問題找到所要尋找的元素，即猜到A取得元素，這里“是”或“非”問題相當(dāng)于作一次比較結(jié)果兩種狀態(tài)。 2k=n! k=log2n! 由此得到下述結(jié)論： 任何一個借助“比較”進(jìn)行分類的算法，在最壞情況下所需的比較次數(shù)至少為log2n!。,排序的時間復(fù)雜度分析,根據(jù)Stirling公式: n!=(2n)1/2(n/e)n log2n!= log2(2n)1/2(n/e)n= n(log2 n-log2e)+1/2log2 n+1/2log22) =O(n log2 n),排序的時間復(fù)雜度分析,也就是說任何排序法在最壞情況下所需要的比較次數(shù)不的少于O(n log2n)。,堆排序,堆是一個幾乎完全的二叉樹每一個節(jié)點(diǎn)都滿足：如果v和p(v)分別是節(jié)點(diǎn)和它的父節(jié)點(diǎn)，那么p(v)=v. 堆方便如下兩個運(yùn)算：插入元素和尋找最大元素。 堆的特征：沿著每條從根到葉子的路徑，元素的值以非升序排列。 堆可以用數(shù)組這個數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)。,堆排序,H10=15,12,11,7,6,5,4,2,1,0,父節(jié)點(diǎn)在數(shù)組中的下標(biāo)與子節(jié)點(diǎn)下標(biāo)的關(guān)系？,堆排序,假如個節(jié)點(diǎn)的地址入n,則它的“父親”節(jié)點(diǎn)的地址應(yīng)為n/2。它的左”兒子”節(jié)點(diǎn)的地址”兒子”為2n,右“兒子”節(jié)點(diǎn)的地址為2n+1。,堆排序,堆的運(yùn)算： Sift-up 假定對于某個i1,Hi變成了鍵值大于它父節(jié)點(diǎn)鍵值的元素，這樣不符合堆的特性，其他節(jié)點(diǎn)符合堆的條件，需要調(diào)整。 把Hi沿著從Hi到根節(jié)點(diǎn)的唯一一條路徑，把Hi移到合適它的位置上，每次向上移動一步，都把Hi和它當(dāng)前的父節(jié)點(diǎn)比較。 例子：P75,圖 4 .1 -圖4.2,堆排序,C代碼： void Sift-up( int j, int Hn) int done=0,k=j,temp; if( j=1) return ; do if (HkHk/2) temp=Hk/2;Hk/2=Hk; Hk=temp; else done=1; k=k/2; while(k=1| done); ,堆排序,為什么這樣調(diào)整后，滿足堆的條件？,堆排序,Sift-down: 假定對于某個i圖4.3,堆排序,C代碼： void Sift-down( int j, int Hn) int done=0,k=j,temp; if( jn ) return ; do k=k*2; if(k+1Hk ) k=k+1; if (Hk/2n| done); ,堆排序,在堆中插入一個元素x，先把堆的大小假加1，然后將x添加到堆最下面的最右邊，然后調(diào)整堆。 由于堆的元素個數(shù)為n，則堆的高度為log n，所以在堆中插入一個元素的時間是：O( log n),堆排序,C代碼： void insert(int Hn,int x,int NewHn+1) int j; for (j=0;jn;j+) NewHj=Hj; NewHn=x; Sift-up(NewH,n); ,堆排序,要從大小為n的堆中刪除元素Hk，可先用Hn替換Hk，然后將堆大小減1，并利用函數(shù)Sift-up或Sift-down調(diào)整堆。顯然，刪除一個元素的時間是O( log n).,堆排序,void delete(int Hn,int j,int newHn-1) int x=Hj,y=Hn-1,k; for(k=0;k=x) Sift-up(newH,j); else Sift-down(newH,k); ,堆排序,給出一個有n個元素的數(shù)組A1n，要創(chuàng)建一個包含這些元素的堆是：從空的堆開始，不斷插入每一個元素，直到A完全被轉(zhuǎn)移到堆中為止。 因?yàn)椴迦氲趈 個元素用時 O(log j)，因此，用這種方法創(chuàng)建堆的時間復(fù)雜性為： O(n log n) 但是，存在一種能在(n)的時間內(nèi)，用n 個元素建立一個堆。,堆排序,堆排序,堆排序,堆排序,void MakeHeap(int An) int j; for (j=n/2;j0;j-) Sift-down(A,j); ,堆排序,計算算法MakeHeap的運(yùn)行時間： T是一個完全二叉數(shù)，設(shè)它的高是k=log n, 對于數(shù)的第j層的一個節(jié)點(diǎn)，它重復(fù)執(zhí)行Sift-down的次數(shù)最多是k-j。 因此，在第j 層上正好有 2 j 個節(jié)點(diǎn)，所以，循環(huán)執(zhí)行的總次數(shù)上界是：,堆排序,用堆的思想對數(shù)組An進(jìn)行排序，步驟： 1、首先把An變成堆。 2、交換An與A1 3、用Sift-down調(diào)整A1n-1,堆排序,C: Void HeapSort(int An) int j,temp; MakeHeap(A); for(j=n;j=2;j-) temp=A0;A0=Aj;Aj=temp; Sift-down(1,Aj-1); ,堆排序,時間復(fù)雜度： 建立堆用O(n), Sift-down運(yùn)行用O(log n),因此，堆排序時間復(fù)雜度： O(n log n) 空間復(fù)雜度：O(1),多項(xiàng)式求值,假設(shè)有n+2個實(shí)數(shù)，a0,a1,an 和x 的序列，求多項(xiàng)式的值： 直接方法，一項(xiàng)一項(xiàng)求，乘法次數(shù)： n+(n-1)+(n-2)+1=n(n+1)/2,多項(xiàng)式求值,Horner規(guī)則： 假設(shè)已知， 那么，求 ：,多項(xiàng)式求值,double Horner(double x,double an+1) double p=an; int j; for(j=0;jn;j+) p=x*p+an-1-j; return p; 復(fù)雜度：n次乘法，n次加法。,二進(jìn)制冪,求an ? 1）暴力法:a*a*a 2）n=(bkbib0)2 ,其中bi =0/1, bk =1 n= bk *2k+ bk-1 *2k-1+ + b0 *20 如果給定右邊的表達(dá)式，如何求n? P178 3） an = a bk *2k+ bk-1 *2k-1+ + b0 *20,二進(jìn)制冪,a13 =a1*23+1*22+0*21+1 /Horner規(guī)則 =a(1*22+1*21+0 )*21+1 =a(1*21+1)*21+0 )*21+1 =a(1*21+1)*21+0 21 * a /計算過程 =a(1*21+1)*21 *2 * a =a(1*21+1) 22 * a =a2 * a 22 * a /5次乘法,二進(jìn)制冪,LeftRightBinaryExponentiantion(a,b(n) p=a; for(j=k;j=0;j-) p=p*p; if b(j)=1 then p=p*a; ret