【正文】 循環(huán)賽日程表 2021年 11月 12日 106 循環(huán)賽日程表 ?算法復(fù)雜性分析 遞歸算法： )4()1(4)( kOkTkT ??? 非遞歸算法： ? ? ? ?? ? ? ????ks t i jksk s sOkT1212222)4(2)(。 (b) 2k(k=2)個(gè)選手比賽 2021年 11月 12日 105 2k個(gè)選手的比賽日程是在 2k1個(gè)選手的比賽日程的基礎(chǔ)上通過迭代的方法求得的 。 } 2021年 11月 12日 103 循環(huán)賽日程表 設(shè)有 n=2k個(gè)選手要進(jìn)行循環(huán)賽 ， 要求設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表： （ 1） 每個(gè)選手必須與其他 n1個(gè)選手各賽一次； （ 2） 每個(gè)選手一天只能賽一次 。ji。in1。 2021年 11月 12日 102 ?算法 : void bubblesort(ElemType a[ ],int n) { int i,j。不考慮數(shù)組中記錄的排列情況，冒泡排序的比較次數(shù)總將是 i，因此冒泡排序的時(shí)間復(fù)雜性為： O(n2) 一個(gè)記錄比它前一記錄的關(guān)鍵字小的概率有多大決定了記錄交換的次數(shù)。就象水底的“水泡”冒到水面上一樣，因此稱為冒泡排序。然后再對(duì) n2個(gè)記錄重復(fù)上述過程， … ，直到某一趟排序過程中不出現(xiàn)記錄交換位臵，排序結(jié)束。經(jīng)過如此一趟的比較與交換， n個(gè)記錄中關(guān)鍵字值最小的記錄就會(huì)被交換到數(shù)組的第 0個(gè)位臵。其基本思想是先將數(shù)組中的第n1個(gè)記錄與第 n2個(gè)記錄的關(guān)鍵字值進(jìn)行比較，如果第n1個(gè)記錄的關(guān)鍵字值小于第 n2個(gè)記錄的關(guān)鍵字值，則兩個(gè)記錄交換位臵，否則不交換。 )()()1()(2nOnOnTnT????2021年 11月 12日 96 快速排序 ? 在 最好情況 下，每次劃分對(duì)一個(gè)記錄定位后，該記錄的左側(cè)子序列與右側(cè)子序列的長度相同。 //對(duì)左半段排序 RandomizedQuickSort (a,q+1,r)。 2021年 11月 12日 94 templateclass Type void RandomizedQuickSort (Type a[], int p, int r) { if (pr) { int q=RandomizedPartition(a,p,r)。通過修改算法 partition，可以設(shè)計(jì)出采用隨機(jī)選擇策略的快速排序算法。 return Partition (a, p, r)。 2021年 11月 12日 93 templateclass Type int RandomizedPartition (Type a[], int p, int r) { int i = Random(p,r)。但是，如 果輸入的數(shù)組是正序或者是逆序的，就會(huì)將所有的記錄分到“基準(zhǔn)值”的一邊。 2021年 11月 12日 89 13 65 27 50 38 49 55 j i i i 13 65 27 50 38 49 55 i j j 快速排序一次劃分示例 j 13 65 27 50 38 49 55 i j 2021年 11月 12日 90 13 65 27 50 38 49 55 j i i j j 13 65 27 50 38 49 55 i 13 65 27 50 38 49 55 快速排序一次劃分示例 j 2021年 11月 12日 91 按照快速排序的思想排下列序列 初始序列： {6, 7, 5, 2, 5, 8} 2021年 11月 12日 92 ?“基準(zhǔn)值”的選擇有多種方法。 a[j] = x。 Swap(a[i], a[j])。 while (a[ j] x)。amp。 Type x=a[p]。 //對(duì)左半段排序 QuickSort (a,q+1,r)。 templateclass Type void QuickSort (Type a[], int p, int r) { if (pr) { int q=Partition(a,p,r)。 快速排序的分治策略是： （ 1） 劃分 ：選定一個(gè)記錄作為軸值 ， 以軸值為基準(zhǔn)將整個(gè)序列劃分為兩個(gè)子序列 ap … aq1和 aq+1 … ar，前一個(gè)子序列中記錄的值均小于或等于軸值 ， 后一個(gè)子序列中記錄的值均大于或等于軸值； 2021年 11月 12日 86 快速排序 [ ap … … aq1 ] aq [ aq+1 … … ar ] 均 ≤aq 軸值 均 ≥aq 位于最終位置 ?合并排序按照記錄在序列中的位置對(duì)序列進(jìn)行劃分； ?快速排序按照記錄的值對(duì)序列進(jìn)行劃分。 // 合并到數(shù)組 a ? s += s。 // 合并到數(shù)組 b ? s += s。 ? int s = 1。 j++) ? y[j] = x[j]。 ? } else { // 剩下的元素個(gè)數(shù)少于 S ? for (int j = i。 ? i += (2*s)。 ? } // Merge 2021年 11月 12日 82 ? template class Type ? void MergePass (Type x[], Type y[], int s, int n) { ? // 合并大小為 s的相鄰 2段子數(shù)組 ? int i = 0。 q = mid。 q++) d[ k++ ] = c[ q++ ]。 // 右邊的數(shù)入列 ? if (i mid) // 右邊剩余的數(shù)入列 ? for (int q = j。 j = right) ? if (c[i] = c[j]) d[ k++ ] = c[ i++ ]。 // 計(jì)數(shù)器 ? while (i = mid amp。 ?非遞歸排序先將相鄰元素排序，構(gòu)成 n/2組，然后兩兩合并，直至整個(gè)數(shù)組排好序。 //復(fù)制回?cái)?shù)組 a } } 復(fù)雜度分析 T(n)=O(nlogn) 漸進(jìn)意義下的最優(yōu)算法 ??????? 11)()2/(2)1()(nnnOnTOnT2021年 11月 12日 79 ?思想： 因?yàn)檫f歸法的合并排序?qū)嶋H上是將待排序的無序序列一分為二，直至分解到只剩下一個(gè)元素為止，然后不斷合并二個(gè)排好序的子序列，按此思想可以寫出消除遞歸的合并排序。 merge(a, b, left, i, right)。 //取中點(diǎn) mergeSort(a, left, i)。39。39。39。39。 2021年 11月 12日 76 合并排序 ?合并排序的分治策略： （ 1） 劃分 ：將待排序序列 a0, a1, …, an1劃分為兩個(gè)長度相等的子序列 a0, …, an/21和 an/2, …, an1； （ 2） 遞歸 求解子問題 ：分別對(duì)這兩個(gè)子序列遞歸地進(jìn)行合并排序，得到兩個(gè)有序子序列； （ 3） 合并 ：將這兩個(gè)有序子序列合并成一個(gè)有序序列。若將兩個(gè)有序表合并成一個(gè)有序表，稱為 2路歸并。然后再把有序子序列合并為整體有序序列。該算法是采用 分治法 （ Divide and Conquer）的一個(gè)非常典型的應(yīng)用。 // 覆蓋其余方格 chessBoard(tr+s, tc+s, tr+s, tc+s, s)。 dc = tc + s) // 特殊方格在此棋盤中 chessBoard(tr+s, tc+s, dr, dc, s)。} // 覆蓋右下角子棋盤 if (dr = tr + s amp。 else {// 用 t 號(hào) L型骨牌覆蓋右上角 board[tr + s][tc + s 1] = t。amp。 // 覆蓋其余方格 chessBoard(tr, tc+s, tr+s1, tc+s, s)。 dc = tc + s) // 特殊方格在此棋盤中 chessBoard(tr, tc+s, dr, dc, s)。} // 覆蓋右上角子棋盤 if (dr tr + s amp。 else {// 此棋盤中無特殊方格 // 用 t 號(hào) L型骨牌覆蓋右下角 board[tr + s 1][tc + s 1] = t。amp。 int t = tile++, // L型骨牌號(hào) s = size/2。遞歸地使用這種分割，直至棋盤簡化為棋盤 1 1。 特殊方格必位于 4個(gè)較小子棋盤之一中，其余 3個(gè)子棋盤中無特殊方格。在棋盤覆蓋問題中，要用圖示的 4種不同形態(tài)的 L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何 2個(gè) L型骨牌不得重疊覆蓋。 ?如果 n不是 2的冪，應(yīng)該如何修改 strassen算法，求出兩個(gè) n n矩陣的乘積？并證明修改后的算法時(shí)間復(fù)雜度為O(nlog7)。 ?在 Strassen之后又有許多算法改進(jìn)了矩陣乘法的計(jì)算時(shí)間復(fù)雜性。因此，要想進(jìn)一步改進(jìn)矩陣乘法的時(shí)間復(fù)雜性，就不能再基于計(jì)算2 2矩陣的 7次乘法這樣的方法了。由此可將方程 C=AB重寫為： ?傳統(tǒng)方法 ： O(n3) ?分治法 : ???????????????????222112112221121122211211BBBBAAAACCCC由此可得： 2112111111 BABAC ??2212121112 BABAC ??2122112121 BABAC ??2222122122 BABAC ??復(fù)雜度分析 T(n)=O(n3) 22)()2/(8)1()(2 ??????? nnnOnTOnT Strassen矩陣乘法 2021年 11月 12日 69 ?傳統(tǒng)方法 ： O(n3) ?分治法 : 為了降低時(shí)間復(fù)雜度，必須減少乘法的次數(shù)。 2021年 11月 12日 67 A和 B的乘積矩陣 C中的元素 C[i,j]定義為 : ??? nkjkBkiAjiC1]][[]][[]][[若依此定義來計(jì)算 A和 B的乘積矩陣 C，則每計(jì)算 C的一個(gè)元素 C[i][j]，需要做 n次乘法和 n1次加法。 ?最終的，這個(gè)思想導(dǎo)致了 快速傅利葉變換 (Fast Fourier Transform)的產(chǎn)生。 2021年 11月 12日 65 ?用解遞歸方程的迭代公式法，不妨設(shè) n=2^k： T(n)=3T(n