算法分析
算法分析是關(guān)于計(jì)算機(jī)程序性能和資源利用的理論研究禽炬；性能研究主要是學(xué)習(xí)如何讓算法或者應(yīng)用程序 運(yùn)行的更快； 資源利用主要指的是諸如通信、存儲(chǔ)器（無論是RAM Memory還是disk Memory）等的使用情況暑塑。
算法是關(guān)注性能問題的學(xué)科，因此這部分內(nèi)容很重要锅必。
設(shè)想梯投，如果你在一家公司從事軟件開發(fā)工程的從事編程工作，有那些比性能更重要的東西况毅？
- 代碼簡潔
- 可維護(hù)性
- 開發(fā)的時(shí)間成本
- 崩潰率
- 安全性
- 用戶友好
佷明顯分蓖，真實(shí)的軟件開發(fā)場景中有諸多的方面都比性能重要。但是算法是關(guān)注性能的科學(xué)尔许，如果算法和性能都不重要么鹤，我們?yōu)槭裁催€要學(xué)習(xí)這樣一個(gè)課程。
性能的好壞可以決定解決方案可行性味廊。
算法是一種描述程序行為的語言蒸甜，業(yè)已廣泛應(yīng)用于計(jì)算機(jī)科學(xué)領(lǐng)域棠耕，且已經(jīng)被所有的實(shí)踐者所采用的理論語言柠新，它是思考程序最為簡潔的一種方式。
性能為什么處于程序開發(fā)中的最底層蕊退。這里有一個(gè)很好的類比憔恳，性能在程序中扮演的角色就如同經(jīng)濟(jì)中的貨幣一樣，貨幣可以購買人基本生活中所需的一切東西输硝，如点把，食物屿附，衣服拿撩，房子和水⊙购悖可能水對(duì)你的生命而言比錢重要探赫，但是你能買下這些商品的前提是有錢伦吠。同樣毛仪，性能是確保良好用戶體驗(yàn)的前提。追求運(yùn)行速度腺逛，是算法研究最讓人興奮的地方衡怀。
排序問題
通過排序問題，進(jìn)行算法分析够委。
插入排序
插入排序的偽代碼如下：
INSERTION-SORT(A)
1 for j=2 to A.length
2 key=A[j]
3 //將A[j]插入到有序的子數(shù)組A[1..j-1]。
4 i=j-1
5 while i>0 and A[i]>key
6 A[i+1]=A[i]
7 i=i-1
8 A[i+1]=key
Java 版本代碼實(shí)現(xiàn)如下：
void insertSort(int[] arr){
if(arr==null||arr.length<2) return;
for(int i=1;i<arr.length;i++){
int key=arr[i];
int j=i-1;
while (j>=0 && arr[j]>key){
arr[j+1]=arr[j];
j--;
}
arr[j+1]=key;
}
}
運(yùn)行時(shí)間分析
運(yùn)行時(shí)間依賴于下面的因素
- 輸入項(xiàng)
- 輸入項(xiàng)的規(guī)模
分析運(yùn)行時(shí)間的方式
- 最壞情況-Worst-case（usually）
T(n) = max time on any input of size n - 平均情況-Average-Case（somtimes）
T(n) =excepted time all input size n
前提是，需要一個(gè)有關(guān)輸入統(tǒng)計(jì)分布的假設(shè)
每種輸入的運(yùn)行時(shí)間乘以該輸入出現(xiàn)的概率進(jìn)行加權(quán)平均所得到的時(shí)間，就是期望運(yùn)行時(shí)間 - 最好情況Best_Case（假象）
假設(shè)恢共，用已經(jīng)做好排序的序列檢驗(yàn)"低速"算法讨韭，得到的運(yùn)行時(shí)間可以的到最好情況。
最壞情況的運(yùn)行時(shí)間分析：
- 依賴使用的計(jì)算機(jī)狰闪、
相對(duì)運(yùn)行時(shí)間（在相同計(jì)算機(jī)上運(yùn)行）
絕對(duì)運(yùn)行時(shí)間（在不同計(jì)算機(jī)上運(yùn)行）
漸進(jìn)分析（Asymptotic Analysis）
- 忽略那些依賴于機(jī)器的常量
- 當(dāng)n趨近于∞過程中埋泵，忽略機(jī)器實(shí)際的運(yùn)行時(shí)間罪治，而是T(n)的增長
漸進(jìn)符號(hào)
- Θ 標(biāo)記
漸進(jìn)緊確界
舍棄低階項(xiàng)觉义，并忽略前面的常數(shù)因子
例如晒骇，如果公式為3n3+90n2-5n+6046=Θ（n3）
當(dāng)n->∞時(shí)Θ（n2）的算法總是能戰(zhàn)勝一個(gè)Θ（n3）的算法洪囤，其他項(xiàng)不會(huì)動(dòng)搖這個(gè)結(jié)果，假設(shè)在一臺(tái)性能好的機(jī)器上運(yùn)行Θ（n3）的算法崭参，在一臺(tái)性能差的機(jī)器上運(yùn)行Θ（n2）的算法何暮，只要n足夠大，Θ（n2）的算法總是能戰(zhàn)勝一個(gè)Θ（n3）的算法海洼，這個(gè)結(jié)論依然成立坏逢，這就是漸進(jìn)符號(hào)的偉大之處（它能一舉滿足我們對(duì)相對(duì)和絕對(duì)速度的雙重比較要求）是整。
從工程視角來看有時(shí)臨界值n0的過大，大到計(jì)算機(jī)無法運(yùn)行浮入，這就是我們?yōu)槭裁磿?huì)對(duì)低速的算法館興趣的原因事秀，有一些算法盡管用漸進(jìn)的觀點(diǎn)來看，他們有可能比較慢宰衙，但是在合理規(guī)模輸入的情況下運(yùn)行的更快供炼，所以我們要從數(shù)學(xué)的理解和工程的直覺之間尋找平衡劲蜻，這樣我們才能寫出更好的程序先嬉。僅僅會(huì)做算法分析楚堤，并不能是你成為一個(gè)編程高手身冬。
老司機(jī)講段子，“如果你想成為編程高手滚躯，你可以在兩年中每天編程茁影；如果你想成為世界級(jí)的編程高手丧凤，你可以每天編程愿待，然后上一門算法課”仍侥。
插入排序的算法分析
內(nèi)存引用計(jì)數(shù)农渊。
最壞情況：T（n）=
O 標(biāo)記
Θ 標(biāo)記漸進(jìn)的給出了一個(gè)函數(shù)的上界和下界腿时，當(dāng)只有一個(gè)漸進(jìn)上界時(shí)饭宾，使用O 記號(hào)看铆。Ω 標(biāo)記
正如O標(biāo)記提供了一個(gè)函數(shù)的漸近上界弹惦，Ω 記號(hào)提供了漸近下界。
算法設(shè)計(jì)
我們可以選擇使用的算法設(shè)計(jì)技術(shù)有很多石抡。插入排序使用了增量方法：在排序子數(shù)組A[1..j-1]后啰扛，將單個(gè)元素A[j] 插入子數(shù)組的適當(dāng)位置隐解，產(chǎn)生排序好的子數(shù)組A[1..j]诫睬。
下面考查一種“分治法”的設(shè)計(jì)方法，我們將用分治法來設(shè)計(jì)一種排序算法蚓曼，該算法的最壞情況的運(yùn)行時(shí)間比插入排序要少得多辟躏。分鐘算法的優(yōu)點(diǎn)之一是捎琐，通過算法分析技術(shù)很容易確定其運(yùn)行時(shí)間瑞凑。
分治法
早在中國漢代就有使用籽御。中國歷史版本"分治法"之推恩令惰匙。
推恩令是漢武帝為了鞏固中央集權(quán)而頒布的一項(xiàng)重要政令哑梳。這項(xiàng)政令要求諸侯王將自己的封地分給自己的子弟鸠真。后來根據(jù)這項(xiàng)政令，諸侯國被越分越小龄毡，漢武帝再趁機(jī)削弱其勢(shì)力吠卷。
許多算法結(jié)構(gòu)上的遞歸的：為了解決一個(gè)給定的問題，算法一次或多次的遞歸調(diào)用其自身以解決相關(guān)的若干子問題沦零。將原問題分解為幾個(gè)規(guī)模較小但是類似原問題的子問題祭隔，遞歸地求解這些子問題，然后再合并這些子問題的解來建立原問題的解路操。
分治模式在每層遞歸時(shí)的三個(gè)步驟：
- 分解
- 解決
- 合并
歸并排序
- 分解
分解待排序的n個(gè)元素的序列成n/2個(gè)元素的兩個(gè)子序列疾渴。 - 解決
使用歸并排序遞歸的排序兩個(gè)子序列。 - 合并
合并兩個(gè)已經(jīng)排序的的子序列以產(chǎn)生一排序的答案寻拂。
插入排序的偽代碼如下：
MERGE-SORT(A)
1 for j=2 to A.length
2 key=A[j]
3 //將A[j]插入到有序的子數(shù)組A[1..j-1]程奠。
4 i=j-1
5 while i>0 and A[i]>key
6 A[i+1]=A[i]
7 i=i-1
8 A[i+1]=key
Java 版本代碼實(shí)現(xiàn)如下：
/**
* 前提[l,mid]有序并且(mid,r]有序 目標(biāo)：通過
*
* @param src
* i:{6,9,10,2,8,11} out:[2,6,8,9,10,11]
* @param tmp
* 臨時(shí)存放順序的數(shù)組
* @param left
* @param mid
* @param right
*/
public static void mergeArray(int[] src, int[] tmp, int left, int mid,
int right) {
int tmpIndex = left;
int leftStart = left;
int rightStart = mid + 1;
while (tmpIndex <= right) {// 臨時(shí)數(shù)組為填滿表明合并未完成
if (leftStart <= mid && rightStart <= right) {// 這種情況是兩個(gè)subarray都未合并結(jié)束
tmp[tmpIndex++] = src[leftStart] < src[rightStart] ? src[leftStart++]
: src[rightStart++];// 條件成立者賦值給臨時(shí)數(shù)組后索引右移（+1）
} else if (leftStart <= mid) {// 這種情況證明右側(cè)的subArray合并結(jié)束
tmp[tmpIndex++] = src[leftStart++];
} else if (rightStart <= right) {// 這種情況表明左側(cè)的subArray合并結(jié)束
tmp[tmpIndex++] = src[rightStart++];
}
}// 臨時(shí)數(shù)組保存了 [left,right]的合并結(jié)果
System.arraycopy(tmp, left, src, left, right - left + 1);
}
/**
* 二路歸并實(shí)現(xiàn)
* @param src
* @param tmp
* @param left
* @param right
*/
public static void mergeSort(int[] src, int[] tmp, int left, int right) {
if (left >= right)
return;
int mid = (right + left) / 2;
mergeSort(src, tmp, left, mid);
mergeSort(src, tmp, mid + 1, right);
mergeArray(src, tmp, left, mid, right);
}
歸并排序的時(shí)間復(fù)雜度為 Θ（nlgn）祭钉，隨著規(guī)模n的增大申尼，歸并排序的運(yùn)行時(shí)間達(dá)到了漸進(jìn)最優(yōu)诬滩，但是歸并排序的一個(gè)缺點(diǎn)是需要開辟一個(gè)同等長度的內(nèi)存空間才能正常運(yùn)行后控。
以上吴攒，謝謝閱讀，希望你有所收獲泽台！
算法導(dǎo)論公開課筆記（一）算法分析與設(shè)計(jì)
算法導(dǎo)論公開課筆記（二）快速排序和隨機(jī)化算法
算法導(dǎo)論公開課筆記（三）線性時(shí)間排序
算法導(dǎo)論公開課筆記（四）順序統(tǒng)計(jì)、中值
動(dòng)態(tài)規(guī)劃算法
