第1章 演算法引論
1、 概念：
1??演算法：演算法是解決特定問題的方法或程序。嚴格的說是滿足下述性質的指令序列。
·輸入：有零個或多個外部量作為演算法的輸入。
·輸出：演算法產生至少一個量作為輸出。
·確定性：組成演算法的每條指令清晰、無歧義。
·有限性：演算法中每條指令的執行次數有限，執行每條指令的時間也有限
2??程式：是演算法用某種程式設計語言的具體實作
3??資料結構：相互之間存在的一種或多種特定關系的資料元素的集合。 資料元素之間的關系稱為結構
4??資料型別：一個值的集合和定義在這個值集上的一組操作
5??演算法的復雜性
時間復雜性：T=T(N,I)
空間復雜性：S=S(N,I)
三種情況的時間復雜性
漸進運算式、漸進上界記號O、漸進確界記號Θ
2、 漸近階的高低
第2章 遞回與分治策略
1??分治法的基本思想
將一個規模為n的問題分解為k個規模較小的子問題，這些子問題互相獨立且與原問題相同。遞回地解這些子問題，然后將各子問題的解合并得到原問題的解。
2??分治模式在每一層遞回上的三個步驟
分解：將原問題分解成 一系列子問題；
解決：遞回地解各子問題。若子問題足夠小，則直接求解；
合并：將子問題的結果合并成原問題的解。
3.分治法所能解決的問題一般具有的4個特征
1??該問題的規模縮小到一定的程度就可以容易地解決；
2??該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質
3??利用該問題分解出的子問題的解可以合并為該問題的解；
4??該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。
4、 二分搜索技術（折半查找）
最壞情況時間復雜性為O(logn)
1.問題描述：給定已經排好序的n個元素a[0:n-1]的一個序列，要在其中找到一個特定的元素x。
2.基本思想
二分搜索法是運用分治策略的典型例子
1??搜索規模縮小到一定的程度就容易找到；
2??在小范圍內搜索是規模較小的相同問題；
3??分解出的子問題的解可以合并為原問題的解；
4??分解出的各個子問題是相互獨立的。
演算法描述ppt50、演算法的實作細節ppt50、時間復雜度ppt50、給定例子根據演算法的思想分析求解程序ppt48）
public static int binarySearch(int [] a, int x, int n)
{
// 在 a[0] <= a[1] <= ... <= a[n-1] 中搜索 x
// 找到x時回傳其在陣列中的位置，否則回傳-1
int left = 0; int right = n - 1;
while (left <= right) {
int middle = (left + right)/2;
if (x == a[middle]) return middle;
if (x > a[middle]) left = middle + 1;
else right = middle - 1;
}
return -1; // 未找到x
}
演算法復雜度分析：
每執行一次演算法的while回圈， 待搜索陣列的大小減少一半。因此，在最壞情況下，while回圈被執行了O(logn) 次。回圈體內運算需要O(1) 時間，因此整個演算法在最壞情況下的計算時間復雜性為O(logn) 。
5、 大整數相乘問題（降低時間復雜度的思路：為了降低時間復雜度，必須減少乘法的次數）時間復雜度為O(n2)。
6、 Strassen矩陣乘法（降低時間復雜度的思路：為了降低時間復雜度，必須減少乘法的次數）矩陣相乘的時間復雜度為O(n3)。
7、 快速排序（
1??基本思想：一趟快速排序的程序：選擇一個元素作為樞軸（或支點）（pivot），將所有小于它的元素安置在其位置之前，所有大于它的元素安置在其之后。
對樞軸兩邊的子序列遞回地進行快速排序，直至順序完成。
2??演算法描述
public static int Partition (int a[], int low, int high) {
int left,right,pivotkey;
left=low;
right=high;
pivotkey=a[low];//取第一個元素為樞軸
while (left<right) {
//在陣列的右端掃描
while(left<right&&a[right]>=pivotkey)right--;
if(left<right){
a[left]=a[right];
left++;
}
//在陣列的左端掃描
while(left<right&&a[left]<pivotkey)left++;
if(left<right){
a[right]=a[left];
right--;
}
}
a[left]=pivotkey;
return left;
}
public static void QuickSort(int a[], int low,
int high)
{
int pivotLoc:
if (low<high)
{
pivotLoc=Partition(a,low,high);
QuickSort(a,low,pivotLoc-1);
QuickSort(a,pivotLoc+1,high);
}
}
3??快速排序的性能主要取決于劃分的對稱性，因此改進劃分演算法Patition是關鍵。
4??
快速排序的性能改進的思路
三者取中間值的劃分方法應用在哪種情況比較好ppt88）
三者中取中間值的劃分方法
通過從第一個、最后一個和中間元素三者中取中間值的方法來選取樞軸元素。
易于操作，劃分代價低。
對于排好序或者近似排好序的序列，是一個比較好的策略。
時間復雜度是O(nlogn)。
8、 最接近點對問題（一維空間最接近點對問題，問題描述）
平面上的最接近點對問題：
給定平面上的n個點，找其中的一對點，使得在n個點組成的所有點對中，該點對的距離最小。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/25984.html
標籤：語言基礎/算法/系統設計
上一篇：nginx