麻省理工學院公開課：算法導論。B站地址，網易公開課也有對應的資源。https://www.bilibili.com/video/av1149902/
本節(jié)課的主要內容是，課程準備和插入排序、歸并排序的算法分析。

課程準備（講了約17分鐘）

預備知識：離散數學、概率論。都是大學計算機專業(yè)的必修課程。
考勤之類的：不能缺勤，要按時按成習題集之類的。

算法分析是理論研究，關于計算機程序性能和資源利用的研究。計算機資源，包括通信、存儲器、內存、磁盤存儲等。

這是一門關注性能的課程。對于程序員來說，有很多比性能重要的東西。如安全性、正確、簡潔、可維護性、健壯性、可擴展、用戶友好、功能性、模塊化等等。但是性能也非常重要，對于實時應用，如果性能不好，影響了實時性，那就失去了實時的功能。對于占用大量內存的應用，如果性能不好，也是會直接崩潰無法使用的。

排序問題

關于排序問題的算法有很多種。課程中講了兩種：插入排序、歸并排序

插入排序

偽代碼如下：（數組為A[]）

for j <- 2 to n
    do key <- A[j]
        i <- j-1
        while i>0 and A[i]>key
            do A[i+1] <- A[i]
        i <- i-1
    A[i+1] <- key

用JavaScript語言描述如下：

var key;
for(var i=1;i<n;i++){
    key = A[i];  //保存當前項為常量key
    for(var j=i-1;j>=0;j--){  //遍歷當前項前面的值，找到合適的位置插入
        if(A[j] > key){
            A[j+1] = A[j];
        }
    }
    A[j+1] = key;  //找到當前項合適的位置，插入
}

現在對以上算法進行分析，從三個方面進行：最壞的情況（全部逆序），平均情況（涉及到概率論相關知識，每種輸入的情況對應的概率），最好的情況（全部正序）。
運用漸近分析。

漸近分析：忽略依賴于機器的常量，不檢查實際的運行時間，而是關注運行時間的增長。

漸近符號之一——θ符號（這門課程中常用的符號）：棄去低階項，忽略常數因子。θ是一個弱符號，是一個描述符號，而不是運算符號。
例如：

3n^3+90n^2-5n+6046
可以表示為θ(n^3)

最壞的情況，就是數組中的數字都是倒序，這種情況下的時間消耗為θ(n^2)。

歸并排序

一個思路，沒有列出具體的代碼

• if n=1，done. 時間復雜度為θ(1)
• 將數組A分成兩個數組，分別是[a1,a2,...,a(n/2)],[a(n/2+1),...an]，分別對其進行排序，時間復雜度為2T(n/2)。T(n)表示對一個長度為n的數組進行排序所需要的時間復雜度。
• 將兩個排好序的數組進行合并。對比兩個數組的第一個元素，將小的那個push進新的數組內，然后繼續(xù)對比。時間復雜度為θ(n)。

時間復雜度T(n)有兩種情況：
1、if n=1, T(n) = θ(1)
2、if n>1, T(n) = 2T(n/2)+θ(n)

T(n) = 2T(n/2)+cn（n是大于0的常數）
下面使用遞歸樹的方法來對T(n)進行分析：

T(n) = 2T(n/2)+cn
     = 4T(n/4)+cn+2c(n/2)
     = 8T(n/8)+cn+2c(n/2)+4c(n/4)
     = nT(1)+cn+cn+cn+...+cn
     = nT(1) + cn*lgn
     = θ(n)+θ(nlgn)
     = θ(nlgn)

每次都將數組一分為二，直到最后T(1)=θ(1)（理想情況下，假設n為2的指數倍），一共需要進行lgn次分解，每次都會分解出一個cn，共lgn次，故為cnlgn，忽略常量，即為nlgn。

分析結果其時間復雜度為θ(nlgn)。
也就是：
1、if n=1, T(n) = θ(1)
2、if n>1, T(n) = 2T(n/2)+θ(n) = θ(nlgn)
在n比較大的情況下，優(yōu)于插入排序算法。