算法分析

算法分析是關(guān)于計(jì)算機(jī)程序性能和資源利用的理論研究；性能研究主要是學(xué)習(xí)如何讓算法或者應(yīng)用程序 運(yùn)行的更快； 資源利用主要指的是諸如通信、存儲器（無論是RAM Memory還是disk Memory）等的使用情況。
算法是關(guān)注性能問題的學(xué)科，因此這部分內(nèi)容很重要。

設(shè)想，如果你在一家公司從事軟件開發(fā)工程的從事編程工作，有那些比性能更重要的東西？

• 代碼簡潔
• 可維護(hù)性
• 開發(fā)的時(shí)間成本
• 崩潰率
• 安全性
• 用戶友好

佷明顯，真實(shí)的軟件開發(fā)場景中有諸多的方面都比性能重要。但是算法是關(guān)注性能的科學(xué)，如果算法和性能都不重要，我們?yōu)槭裁催€要學(xué)習(xí)這樣一個(gè)課程。

1. 性能的好壞可以決定解決方案可行性。

2. 算法是一種描述程序行為的語言，業(yè)已廣泛應(yīng)用于計(jì)算機(jī)科學(xué)領(lǐng)域，且已經(jīng)被所有的實(shí)踐者所采用的理論語言，它是思考程序最為簡潔的一種方式。
   性能為什么處于程序開發(fā)中的最底層。這里有一個(gè)很好的類比，性能在程序中扮演的角色就如同經(jīng)濟(jì)中的貨幣一樣，貨幣可以購買人基本生活中所需的一切東西，如，食物，衣服，房子和水?？赡芩畬δ愕纳员儒X重要，但是你能買下這些商品的前提是有錢。同樣，性能是確保良好用戶體驗(yàn)的前提。

3. 追求運(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í)間的方式

1. 最壞情況-Worst-case（usually）
   T(n) = max time on any input of size n
2. 平均情況-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í)間
3. 最好情況Best_Case（假象）
   假設(shè)，用已經(jīng)做好排序的序列檢驗(yàn)"低速"算法，得到的運(yùn)行時(shí)間可以的到最好情況。

最壞情況的運(yùn)行時(shí)間分析：

• 依賴使用的計(jì)算機(jī)、
  相對運(yùn)行時(shí)間（在相同計(jì)算機(jī)上運(yùn)行）
  絕對運(yùn)行時(shí)間（在不同計(jì)算機(jī)上運(yùn)行）

漸進(jìn)分析（Asymptotic Analysis）

1. 忽略那些依賴于機(jī)器的常量
2. 當(dāng)n趨近于∞過程中，忽略機(jī)器實(shí)際的運(yùn)行時(shí)間，而是T(n)的增長
   漸進(jìn)符號

• Θ 標(biāo)記
  漸進(jìn)緊確界
  舍棄低階項(xiàng)，并忽略前面的常數(shù)因子
  例如，如果公式為3n3+90n2-5n+6046=Θ（n3）
  當(dāng)n->∞時(shí)Θ（n2）的算法總是能戰(zhàn)勝一個(gè)Θ（n3）的算法，其他項(xiàng)不會動搖這個(gè)結(jié)果，假設(shè)在一臺性能好的機(jī)器上運(yùn)行Θ（n3）的算法，在一臺性能差的機(jī)器上運(yùn)行Θ（n2）的算法，只要n足夠大，Θ（n2）的算法總是能戰(zhàn)勝一個(gè)Θ（n3）的算法，這個(gè)結(jié)論依然成立，這就是漸進(jìn)符號的偉大之處（它能一舉滿足我們對相對和絕對速度的雙重比較要求）。

image.png

從工程視角來看有時(shí)臨界值n0的過大，大到計(jì)算機(jī)無法運(yùn)行，這就是我們?yōu)槭裁磿Φ退俚乃惴^興趣的原因，有一些算法盡管用漸進(jìn)的觀點(diǎn)來看，他們有可能比較慢，但是在合理規(guī)模輸入的情況下運(yùn)行的更快，所以我們要從數(shù)學(xué)的理解和工程的直覺之間尋找平衡，這樣我們才能寫出更好的程序。僅僅會做算法分析，并不能是你成為一個(gè)編程高手。
老司機(jī)講段子，“如果你想成為編程高手，你可以在兩年中每天編程；如果你想成為世界級的編程高手，你可以每天編程，然后上一門算法課”。

插入排序的算法分析
內(nèi)存引用計(jì)數(shù)。
最壞情況：T（n）=

image.png

• O 標(biāo)記
  Θ 標(biāo)記漸進(jìn)的給出了一個(gè)函數(shù)的上界和下界，當(dāng)只有一個(gè)漸進(jìn)上界時(shí)，使用O 記號。

• Ω 標(biāo)記
  正如O標(biāo)記提供了一個(gè)函數(shù)的漸近上界，Ω 記號提供了漸近下界。

算法設(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ī)削弱其勢力。

許多算法結(jié)構(gòu)上的遞歸的：為了解決一個(gè)給定的問題，算法一次或多次的遞歸調(diào)用其自身以解決相關(guān)的若干子問題。將原問題分解為幾個(gè)規(guī)模較小但是類似原問題的子問題，遞歸地求解這些子問題，然后再合并這些子問題的解來建立原問題的解。
分治模式在每層遞歸時(shí)的三個(gè)步驟：

1. 分解
2. 解決
3. 合并

歸并排序

1. 分解
   分解待排序的n個(gè)元素的序列成n/2個(gè)元素的兩個(gè)子序列。
2. 解決
   使用歸并排序遞歸的排序兩個(gè)子序列。
3. 合并
   合并兩個(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ì)、中值
動態(tài)規(guī)劃算法