空白目錄 · 算法設計分析

[TOC] # 第一章(算法設計基礎) # ## 知識點 ## ``` 1、算法的性質：正確性、健壯性、可理解性、抽象分級、高效性。 2、算法的描述方法：自然語言、流程圖、程序設計語言、偽代碼。 3、算法的重要特性：輸入，輸出，有窮，確定，可行。 4、算法：對特定問題求解 ``` ## 課后題 ## ### 習題四 ### ```c++ //設數組a[n]中的元素均不相等，設計算法找出a[n]中一個既不是最大也不是最小的元素，并說明最壞情況下的比較次數。要求分別給出偽代碼和C++描述。 #include<iostream> using namespace std; int main() { int a[]={1,2,3,6,4,9,0}; int mid_value=0;//將“既不是最大也不是最小的元素”的值賦值給它 for(int i=0;i!=4;++i) { if(a[i+1]>a[i]&&a[i+1]<a[i+2]) { mid_value=a[i+1]; cout<<mid_value<<endl; break; } else if(a[i+1]<a[i]&&a[i+1]>a[i+2]) { mid_value=a[i+1]; cout<<mid_value<<endl; break; } }//for return 0; } ``` # 第二章(算法分析基礎) # ## 知識點 ## ### 輸入規模與基本語句 ### ``` 輸入規模: 輸入量的多少。基本語句: 執行次數與整個算法的執行次數成正比的語句。非遞歸算法分析的一般步驟: 1、確定文題的輸入規模。 2、找出算法中基本語句。 3、檢查基本語句的執行次數是否只依賴與輸入規模。 4、建立基本語句執行次數的求和表達式。 5、用漸進符號表示這個求和表達式。 ``` # 第三章（蠻力法） # ## 知識點 ## ``` 蠻力法是一種簡單而直接地解決問題的方法,常常直接基于問題的描述,所以, 蠻力法也是最容易應用的方法。例如,對于給定的整數 a 和非負整數 n, 計算 a^n的值,最直接最簡單的想法就是把 1 和 a相乘 n 次,即:a^n = a× a× ... × a n次 ``` ## 選擇排序 ## ### 動態演示 ### <img src="https://upload.wikimedia.org/wikipedia/commons/9/94/Selection-Sort-Animation.gif"> ### 偽代碼 ### ``` // 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置， // 然后，再從剩余未排序元素中繼續尋找最小（大）元素，然后放到已 // 排序序列的末尾。以此類推，直到所有元素均排序完畢。 // ------------------------------------------------------------- function selection_sort(array, length) { var i, j, min, temp; for (i from 0 to length-1) { min = i; for (j from i+1 to length) if (array[min] > array[j]) min = j; temp = arr[min]; array[min] = array[i]; array[i] = temp; } } // ------------------------------------------------------------- // 分類排序算法 // 數據結構數組 // 最差時間復雜度 О(n2) // 最優時間復雜度 О(n2) // 平均時間復雜度 О(n2) // 最差空間復雜度 ``` ## 起泡排序 ## ### 動態演示 ### <img src="https://upload.wikimedia.org/wikipedia/commons/3/37/Bubble_sort_animation.gif" > ### 偽代碼 ### ``` // 兩兩比較相鄰記錄，如果反序則交換。 // -------------------------------------------------------------- function bubble_sort (array, length) { var i, j; for(i from 0 to length-1){ for(j from 0 to length-1-i){ if (array[j] > array[j+1]) swap(array[j], array[j+1]) } } } // -------------------------------------------------------------- // 分類排序算法 // 數據結構數組 // 最差時間復雜度 O(n^2) // 最優時間復雜度 O(n) // 平均時間復雜度 O(n^2) // 最差空間復雜度總共O(n)，需要輔助空間O(1) ``` # 第四章(分治法) # ## 知識點 ## ``` 基本思想： 1、將一個難以解決的大問題劃分成一些規模較小的子問題。 2、分別求解子問題 3、合并 ``` ## 歸并排序 ## ### 動態演示 ### <img src="https://upload.wikimedia.org/wikipedia/commons/c/cc/Merge-sort-example-300px.gif"> ### 偽代碼 ### ``` // 歸并操作（merge），也叫歸并算法，指的是將兩個已經排序的序列合并成一個序列的操作。歸并排序算法依賴歸并操作。 // -------------------------------------------------------------- int min(int x, int y) { return x < y ? x : y; } void merge_sort(int arr[], int len) { int* a = arr; int* b = (int*) malloc(len * sizeof(int*)); int seg, start; for (seg = 1; seg < len; seg += seg) { for (start = 0; start < len; start += seg + seg) { int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len); int k = low; int start1 = low, end1 = mid; int start2 = mid, end2 = high; while (start1 < end1 && start2 < end2) b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++]; while (start1 < end1) b[k++] = a[start1++]; while (start2 < end2) b[k++] = a[start2++]; } int* temp = a; a = b; b = temp; } if (a != arr) { int i; for (i = 0; i < len; i++) b[i] = a[i]; b = a; } free(b); } // -------------------------------------------------------------- // 分類排序算法 // 數據結構數組 // 最差時間復雜度 \Theta(n\log n) // 最優時間復雜度 \Theta(n) // 平均時間復雜度 \Theta(n\log n) // 最差空間復雜度 \Theta(n) ``` ## 快速排序 ## ### 動態演示 ### <img src="https://upload.wikimedia.org/wikipedia/commons/6/6a/Sorting_quicksort_anim.gif"> ### 偽代碼 ### ``` // 基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小， // 然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。 // -------------------------------------------------------------- function quicksort(q) var list less, pivotList, greater if length(q) ≤ 1 { return q } else { select a pivot value pivot from q for each x in q except the pivot element if x < pivot then add x to less if x ≥ pivot then add x to greater add pivot to pivotList return concatenate(quicksort(less), pivotList, quicksort(greater)) } void Qsort(int a[], int low, int high) { if(low >= high) { return; } int first = low; int last = high; int key = a[first];/*用字表的第一個記錄作為樞軸*/ while(first < last) { while(first < last && a[last] >= key) { --last; } a[first] = a[last];/*將比第一個小的移到低端*/ while(first < last && a[first] <= key) { ++first; } a[last] = a[first];/*將比第一個大的移到高端*/ } a[first] = key;/*樞軸記錄到位*/ Qsort(a, low, first-1); Qsort(a, first+1, high); } // -------------------------------------------------------------- // 分類排序算法 // 數據結構不定 // 最差時間復雜度 \Theta(n^2) // 最優時間復雜度 \Theta(n\log n) // 平均時間復雜度 \Theta(n\log n) // 最差空間復雜度根據實現的方式不同而不同 ``` # 第五章(減治法) # ## 知識點 ## ``` 減治法 ( reduce and conquer method)同樣是把一個大問題劃分為若干個子問題,但是這些子問題不需要分別求解,只需求解其中的一個子問題, 因而也無需對子問題的解進行合并。 (1) 原問題的解只存在于其中一個較小規模的子問題中; (2) 原問題的解與其中一個較小規模的解之間存在某種對應關系。 ``` ## 插入排序 ## ### 動態演示 ### <img src="https://upload.wikimedia.org/wikipedia/commons/thumb/0/0f/Insertion-sort-example-300px.gif/220px-Insertion-sort-example-300px.gif"> ### 偽代碼 ### ``` void insertion_sort(int arr[], int len) { int i, j; int temp; for (i = 1; i < len; i++) { temp = arr[i]; //與已排序的數逐一比較，大於temp時，該數向後移 //j循環到-1時，由于[[短路求值]](http://zh.wikipedia.org/wiki/短路求值)，不會運算array[-1] for (j = i - 1; j >= 0 && arr[j] > temp; j--) arr[j + 1] = arr[j]; arr[j+1] = temp; //被排序數放到正確的位置 } } // -------------------------------------------------------------- // 分類排序算法 // 數據結構數組 // 最差時間復雜度 O(n^2) // 最優時間復雜度 O(n) // 平均時間復雜度 O(n^2) // 最差空間復雜度總共O(n) ，需要輔助空間O(1) ``` ## 堆排序 ## ### 動態演示 ### <img src="https://upload.wikimedia.org/wikipedia/commons/1/1b/Sorting_heapsort_anim.gif"> ### 偽代碼 ### ``` #include <stdio.h> #include <stdlib.h> void swap(int* a, int* b) { int temp = *b; *b = *a; *a = temp; } void max_heapify(int arr[], int start, int end) { //建立父節點指標和子節點指標 int dad = start; int son = dad * 2 + 1; while (son < end) { //若子節點指標在範圍內才做比較 if (son + 1 < end && arr[son] < arr[son + 1]) //先比較兩個子節點大小，選擇最大的 son++; if (arr[dad] > arr[son]) //如果父節點大於子節點代表調整完畢，直接跳出函數 return; else { //否則交換父子內容再繼續子節點和孫節點比較 swap(&arr[dad], &arr[son]); dad = son; son = dad * 2 + 1; } } } void heap_sort(int arr[], int len) { int i; //初始化，i從最後一個父節點開始調整 for (i = len / 2 - 1; i >= 0; i--) max_heapify(arr, i, len); //先將第一個元素和已排好元素前一位做交換，再從新調整，直到排序完畢 for (i = len - 1; i > 0; i--) { swap(&arr[0], &arr[i]); max_heapify(arr, 0, i); } } int main() { int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 }; int len = (int) sizeof(arr) / sizeof(*arr); heap_sort(arr, len); int i; for (i = 0; i < len; i++) printf("%d ", arr[i]); printf("\n"); return 0; } // -------------------------------------------------------------- // 分類排序算法 // 數據結構數組 // 最差時間復雜度 O(n \log n) // 最優時間復雜度 O(n \log n)[1] // 平均時間復雜度 \Theta(n \log n) // 最差空間復雜度 O(n) total, O(1) auxiliary ``` # 第六章（動態規劃法） # ## 知識點 ## ``` 動態規劃法將待求解問題分解成若干個相互重疊的子問題, 每個子問題對應決策過程的一個階段, 一般來說,子問題的重疊關系表現在對給定問題求解的遞推關系(也就是動態規劃函數)中,將子問題的解求解一次并填入表中, 當需要再次求解此子問題時,可以通過查表獲得該子問題的解而不用再次求解, 從而避免了大量的重復計算。為了達到這個目的, 可以用一個表來記錄所有已解決的子問題的解, 這就是動態規劃法的設計思想。 ``` ## 0/1 背包問題 ## ### 問題描述 ### <img src="https://upload.wikimedia.org/wikipedia/commons/thumb/f/fd/Knapsack.svg/250px-Knapsack.svg.png"> 背包問題的一個例子：應該選擇哪些盒子，才能使價格盡可能地大，而保持重量小于或等于15 kg？ ### 實例 ### 動態規劃函數: <img src="img/03.png"> <img src="img/02.png"> 有 5 個物品,其重量分別是{2, 2, 6, 5, 4}, 價值分別為{6, 3, 5, 4, 6}, 背包的容量為 10, 求裝入背包的物品和獲得的最大價值。 <img src="img/01.png"> ``` // 0/1 背包問題 int KnapSack(int n , int w[ ] , int v[ ]) { for (i= 0; i < = n; i++ ) / / 初始化第 0 列 V[i][0] = 0; for (j = 0; j < = C; j ++ ) / / 初始化第 0 行 V[0][j] = 0; for (i= 1; i < = n; i++ ) / / 計算第 i 行 ,進行第 i次迭代 for (j= 1; j < = C; j ++ ) if (j< w[i] ) V[i] [j] = V[i - 1][j] ; else V[i] [j] = max( V[i - 1][j] , V[i - 1][j - w[i]] + v[i]) ; j= C; / / 求裝入背包的物品 for (i= n; i > 0; i - - ) { if (V[i] [j] > V[i - 1][j]) { x[i] = 1; j = j - w[i] ; } else x[i] = 0; } return V[n][C]; / / 返回背包取得的最大價值 } ``` ## 多段圖最短路徑問題 ## <img src="img/4.png"> ``` d(0,{1,2,3}) = min { c01+d(1,{2,3}) c12+d(2,{1,3}) c23+d(3,{1,2}) } ------------------ d(1,(2,3) = min { c12+d(2,{3}) c13+d(3,{2}) } ------------------ d(2,{3})= min { c23+d(3,{}) } ------------------ d(3,{}) = c(3,0) = 3 ``` <img src="img/05.png"> ``` //多段圖的最短路徑 1 . 初始化: 數組 cost[n]初始化為最大值 ,數組 path[n]初始化為 - 1; 2 . for (i= n - 2; i> = 0; i - - ) 2 .1 對頂點 i 的每一個鄰接點 j, 根據式(6 .7)計算 cost[i]; 2 .2 根據式(6 .8)計算 path[i]; 3 . 輸出最短路徑長度 cost[0] ; 4 . 輸出最短路徑經過的頂點: 4 .1 i = 0; 4 .2 循環直到 path[i] = n - 1 4 .2 .1 輸出 path[i]; 4 .2 .2 i = path[i] ; ``` ## TSP問題 ## # 第七章（貪心法） # ## 知識點 ## ``` 為了解決一個復雜的問題, 人們總是要把它分解為若干個類似的子問題。分治法是把一個復雜問題分解為若干個相互獨立的子問題, 通過求解子問題并將子問題的解合并得到原問題的解; 動態規劃法是把一個復雜問題分解為若干個相互重疊的子問題,通過求解子問題形成的一系列決策得到原問題的解; 而貪心法(greedy method)是把一個復雜問題分解為一系列較為簡單的局部最優選擇, 每一步選擇都是對當前解的一個擴展, 直到獲得問題的完整解。貪心法的典型應用是求解最優化問題,而且對許多問題都能得到整體最優解, 即使不能得到整體最優解, 通常也是最優解的很好近似。 ``` ## TSP問題 ## ## 背包問題 ## # 第八章（回溯法） # ## 知識點 ## ``` 解空間：就是進行窮舉的搜索空間,所以, 解空間中應該包括所有的可能解。 ``` ## 圖著色問題 ## <img src="img/06.png"> ``` 1 . 將數組 color[n]初始化為 0; 2 . k = 1; 3 . while (k > = 1) 3 .1 依次考察每一種顏色 ,若頂點 k 的著色與其他頂點的著色不發生沖突 ,則轉步驟 3 .2; 否則 ,搜索下一個顏色; 3 .2 若頂點已全部著色 , 則輸出數組 color[n] , 返回; 3 .3 否則 , 3 .3 .1 若頂點 k 是一個合法著色 ,則 k = k + 1, 轉步驟 3 處理下一個頂點; 3 .3 .2 否則, 重置頂點 k 的著色情況 , k = k - 1 ,轉步驟 3 回溯; ``` ## 八皇后問題 ## <img src="http://img.blog.csdn.net/20141025214359265?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvbGhjMTEwNQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast"> ``` void Queue(int n) { for (i = 1; i< = n; i ++ ) // 初始化 x[i] = 0; k = 1; while (k > = 1) { x[k] = x[k] + 1; // 在下一列放置第 k 個皇后 while (x[k] < = n && !Place(k)) x[k] = x[k] + 1; // 搜索下一列 if (x[k] < = n && k = = n) // 得到一個解 ,輸出 { for (i = 1; i< = n; i ++ ) cout < < x[i] ; return; } else if (x[k] < = n && k < n) k = k + 1; // 放置下一個皇后 else { x[k] = 0; // 重置 x[k] , 回溯 k = k - 1; } } } bool Place(int k) // 考察皇后 k 放置在 x[k]列是否發生沖突 { for (i = 1; i< k; i++ ) if (x[k] = = x[i] | | abs(k - i) = = abs(x[k] - x[i] )) return false; return true; } ``` # 第九章（分支限界法） # ## 知識點 ## ``` 回溯法按深度優先策略遍歷問題的解空間樹, 在遍歷過程中, 應用約束條件、目標函數等剪枝函數實行剪枝。分支限界法 ( branch and boundmethod)按廣度優先策略遍歷問題的解空間樹, 在遍歷過程中, 對已經處理的每一個結點根據限界函數估算目標函數的可能取值,從中選取使目標函數取得極值(極大或極小)的結點優先進行廣度優先搜索, 從而不斷調整搜索方向,盡快找到問題的解。因為限界函數常常是基于問題的目標函數而確定的,所以, 分支限界法適用于求解最優化問題。 ``` ## 0/1 背包問題 ##