文章目錄

• 1 算法分析及引論
• • 1.1 算法
  • 1.2 排序
  • • 1.2.1 插入排序
    • • 1.2.1.1 插入排序原理
      • 1.2.1.2 時間復雜度
      • 1.2.1.3 漸進時間復雜度
      • 1.2.1.4 回到算法
    • 1.2.2 歸并排序
    • • 1.2.2.1 歸并排序原理
      • 1.2.2.2 歸并排序時間復雜度

1 算法分析及引論

1.1 算法

算法是一門關注性能的學科，也就是說，我們致力于讓我們要做的事變得更快。讓我們提出一個問題，在程序設計中，什么比性能更重要？

成本（程序員的時間成本），可維護性，穩定性（健壯性，是否老崩潰），功能性，安全，可擴展性。

既然這么多因素都比性能更重要，那我們為何還要研究算法，到底是性能重要還是用戶的體驗更重要呢？

可以肯定的是，很多時候性能和用戶體驗是緊密聯系在一起的，很多時候沒有什么東西比干等著更難受了。

我們研究算法的緣由是：很多時候性能的好壞決定其是否可行，如我們對實時的要求，如果算法性能不快，那么就會導致無法追求實時的效果，實時當然就不可行了?；蛘哒f，如果它占用過多的內存，它也是不可行的，因為硬件需求跟不上?？偟膩碚f：算法走在所有因素的最前沿

第二個關鍵是，算法是一種解釋性語言。其通用讓幾乎所有程序員都接收，它是一種讓程序最為簡潔的思考方式。我們有一個很好說明的例子：我們把算法比作貨幣，那么貨幣作為社會最底層的東西，如果你想要買吃的，買住的，都離不開貨幣。

第三個關鍵是，算法決定了一個程序的安全和用戶體驗的好壞。雖然C比Java快很多，java編程性能會損失三倍左右，但是人們還是喜歡用java來編寫程序，因為java的面向對象機制以及異常機制值得人們為之付出。這也是為什么我們要提高性能，因為我們總是把性能分攤給其他的要素。

第四個關鍵是，我們對此樂此不疲。人們總是喜歡快的東西，比如火箭、滑雪，我們總喜歡這些快速的東西。

在某種意義上，上述這些簡單的問題是我們研究下列問題的指路明燈。

1.2 排序

讓我們來看看一個非常古老的問題，排序。排序包含了許多基本的算法。讓我們舉一個排序的例子：我們輸入一組序列$a_1,a_2...a_n$，按照需求排列后作為輸出。排列一般是使得如$a_1<=a_2...<=a_n$一般。按一定順序排序。

1.2.1 插入排序

1.2.1.1 插入排序原理

這里我們介紹第一個算法，即插入排序。通常我們描述算法用的是偽代碼而不是編程語言。偽代碼中包含有一些解釋性語言如英語或者中文，其能夠讓我們更清楚該算法包含的思想。

值得一提的是，用偽代碼描述算法時，我們通常會使用縮進，其相當于大多數語言中標注開始和結束的分隔符。好比Java和C中的大括號。事實上，歷史上還真有一些語言（例如python）是用縮進代表分隔，但是不是一種好的主義，因為在換頁的時候，你很難知道自己在哪一個嵌套的層級，而是用大括號就能夠很好的表示。

讓我們締造一個數組，如下所示：

這個數組通常是無序的，然而我們通過從從左到右指定一個變量，這個變量我們稱為鍵，他會從數組中提取數據，然后和前面已經排好的序列做比較，然后插入前面的序列，這也是為這么這個算法叫做插入排序的原因。

比較經典的例子我認為是斗地主，在發牌時，我們時常會事先排好手中的牌，我們是一張一張拿起來的，然后將亂序的牌提取出來，然后插入前面已經排序好的位置中。無論什么時候，左手的牌都是排好序的，而右手拿的牌都是即將要插入到排好序的牌中，并且插入位置符合其自身順序。

我們來看一下插入排序的偽代碼實現：

INSERTION-SORT(A)for j←2 to length[A]do key←A[j]Insert A[j] into the sorted sequence A[1..j-1]i←j-1while i>0 and A[i]>keydo A[i+1]←A[i]i←i-1A[i+1]←key

看上面的偽代碼似乎有些費勁，可事實上，它與我們上面講述的別無二致。讓我們引入一個具體的例子來體會這個算法。

我們有一個序列：8 2 4 9 3 6

當我們執行插入排序時，我們的首要任務是從第二個元素開始，依次提取鍵key，然后和前面排序好的序列做對比再插入。題意來看首先提取的是2，然后插入8之前。原序列則變為2 8 4 9 3 6。接著我們找到4，4和2 8進行比對，然后插入2和8之間，原序列變為2 4 8 9 3 6，以此類推按照排序規則循環移動。

讓我們借助數學工具來解剖該算法。如果輸入序列之前就有序，那么已排序序列后的排序工作量就大大減少。因為每次遍歷，它都是做上面循環往復的事。最壞的情況是該序列剛好是逆序，那么每個元素都將進行插入排序。

對應在這道題上，這個例子總共有6個數據，我們將其輸入的規模擴大到100000，那么一旦發生逆序，其時間開銷很大。為此在進行算法分析時，我們通常使用漸進時間復雜度，即假設輸入的規模為n，趨于無限，則運行時間可以看做是以n為映射的函數。

1.2.1.2 時間復雜度

上述引入的時間復雜度中，顯然有最好最壞的情況，最壞對應算法時間的上限，其代表著對用戶的一種承諾，（是的尊貴的用戶我的程序是不會超過這個時間的）。而最好的情況對應著算法時間的下限。我們通常關注算法的最壞時間復雜度。即我們要給出用戶保證，我們的程序總能做到這樣，而不是有時能這樣，我們通常會把輸入考慮成最壞的情況，對應上面插入排序的例子，我們最壞的情況是逆序。

當然有時我們也會討論平均時間復雜度，這個時候T(n)就成了我們算法的時間期望值。那不禁有人會問，期望值是啥？

我們希望聽到一些比較數學味道的回答，所謂的期望實際上就是每種輸入的運行時間，乘以那種輸入出現的概率。這是一種連續型的思考方式，我們可以理解為加權平均。

那我們如何知道特定輸入在給定情況下的概率是多少？有時候我們并不知道，所以我們需要給出一個假設了，一個有關輸入的統計分布的假設，否則期望時間無從談起。

最常見的假設是均勻分布，即所有規模為n的輸入情況都是等可能地出現。

最后我們想講講最好時間復雜度，我們稱之為假象！~bogus（我在大聲地笑哈哈），沒啥用！因為最好的情況不可能出現。如果一個序列已經排好序，我們還有必要去排序嗎，哈哈哈。除非你想要cheat！欺騙！在你得到一個特定輸入下，然后你得到一個比較滿意的結果后欺騙自己，對！這就是我想要的效果，那你就可以考慮它。

1.2.1.3 漸進時間復雜度

回到這個算法，我們不禁發問，插入排序的最壞情況時間是多少？

最簡單的回答是，這取決于你的計算機。你用的是超級計算機還是腕表那么大的計算機，算力會大相徑庭。但是通常來說，我們都是比對兩個算法在同一臺機器上的表現，即相對速度。當然也有人關注絕對速度，我們猜想真有某種算法能無論在什么機器上運行都表現得更好嗎？

以上的回答實際上會對我們最開始的問題造成混淆，這不得不提到我們的大局觀（big idea）了，這也是為什么算法涉獵如此廣泛的原因。我們應該使用抽象的眼光來看待事物，從復雜的情況中提取關鍵的因素對其分析。這就是所謂的漸進分析。漸進分析的基本思路是：忽略掉依賴于機器的常量，不去檢查其因素，而是關注算法本身時間的增長。

使用漸進分析，自然要引入相應的數學符號。這里我們使用的是theta$\Theta$來表示漸進時間復雜度。實際上theta寫起來很簡單，你需要做的是，棄去它的低階項，并忽略前面的常數因子。

比如一個算法花費時間是：$3n^3+90n^2?5n+6046$，那我們就要使用高數中采取的抓大頭準則，使的$3n^3$后面的項全部拋棄，然后再把3拋棄掉即可。所得為$\Theta (n^3)$。

上述情況需要知道的是，假設有一個算法的時間復雜度是$\Theta (n^2)$，那么它遲早比$\Theta (n^3)$速度要快。因為當n逐漸增大時，指數會造成指數爆炸，使得比最大項還小的常數項無法動搖這個最終的結果。這對應到計算機的優劣上，即使你的$\Theta (n^2)$算法是在慢速計算機上運行，總有一天它也會超越在快速計算機上運行的$\Theta (n^3)$算法。

當然，站在工程角度上看，n有時候太大沒有節制是不行的，這會導致我們的計算機無法運行該算法，這也是為什么有時候我們對一些慢速算法比較感興趣，因為它們在n較少的時候能夠保持較高的速度。所以僅僅會做算法分析并不能使你成為高手，你需要保持每天編程，并且在實際編程中運用，知道其什么時候相關什么時候不相關。

1.2.1.4 回到算法

這時候我們可以來分析一些剛才的插入排序算法了。就像我們說的我們關注其最壞時間復雜度。即輸入為逆序。

INSERTION-SORT(A)for j←2 to length[A]do key←A[j]Insert A[j] into the sorted sequence A[1..j-1]i←j-1while i>0 and A[i]>keydo A[i+1]←A[i]i←i-1A[i+1]←key

在這其中明顯有嵌套循環，我們實際上關注循環，因為其他常數操作無關緊要，我們是對其漸進分析。第一個循環中是2到j，而內部循環是從無需的抽出元素對前面的有序序列做插入操作，實際上是由2到j次比對。也就是說，時間復雜度是θ($n^2$)。

那這個時間復雜度到底快不快呢？對于小的n它確實挺快，但是對于巨大的n它就不是那么回事了，所以在下面我會給你一個更快的算法。

1.2.2 歸并排序

1.2.2.1 歸并排序原理

讓我們還是用抽象逐步講到具體。我們給出一個對于A[1…n]的歸并排序。

• 如果給定序列是1，自然不用排序，因為序列中只有一個元素。
• 否則進行遞歸，遞歸的每一層都會將序列一分為二，直到分出一個元素為止，然后對其一對一排序。
• 最后將排序后的序列全部重組。

這里我們出現一個新名詞——遞歸，這個知識點實際上有點小難，我推薦你去看一下我寫的博客數據結構雜談番外篇——搞懂遞歸的小文章_弄鵲-CSDN博客。

上述歸并算法關鍵的部分在于歸并。歸并實際上是使用了分治法的思想，先將大問題分解成小問題，然后再將小問題求解后合并結果。

假設我現在有這么一個數組 8 4 5 7 1 3 6 2，如果采用歸并算法，我們是這么做的：

在我們使用遞歸進入最深層次（即不可再分的第三層）時，我們開始進行治，我們治的方式是用兩根數組指針分別指向分開的兩個序列，如下圖所示：

這個操作的時間復雜度是θ(n)，因為我們所花時間都是在合并n次上。實際上分解并不耗費時間，因為每次遞歸分解都是分解一次。而每次合并要移動指針。

1.2.2.2 歸并排序時間復雜度

讓我們來看看整個歸并排序的時間復雜度是多少。實際上歸并排序總時間=子序列排好序時間+合并時間。

現在我們提前使用遞歸樹方法來解決這里的問題，關于詳細我們會在下一小節敘述：

假設我們有n個數的序列，那么第一次分就可以分為兩個n/2的序列。

$T(n)=2?T(n/2)+合并時間$。又由于合并的時候按照我們上面所說是循環比較兩個指針指向值的大小，所以復雜度為n。則我們可以改寫$T(n)=2?T(n/2)+\theta (n)$。當然了，對于n = 1的情況，T(n) = 1，這個情況我們一般忽略，因為他對遞歸解沒有影響。我們用顯式的$c?n$來替換隱式的θ(n)，然后把其寫出樹狀結構如下所示：

c* n指的是多個常數階步驟所消耗的時間復雜度。常數階的時間復雜度在進行漸進表示時通常省略，所以我們說他是隱式的，而我們用顯式的c*n來表示這些步驟。因為我們在這個時候是要計算T(n)而不是$\Theta (n)$。

也就是說，這個遞歸樹的每一層實際上都是cn。如第二層cn = T(n/2)+T(n/2)。那我們要計算遞歸樹中所有結點所消耗的時間復雜度，即全部相加，用cn乘上樹的高度即可。樹的高度為lgn，所以在遞歸樹中歸并算法花費的時間復雜度為$cn?lgn$。這時候我們如果要求漸進時間復雜度，只需忽略常數項，所以由此可得歸并排序時間復雜度為$\Theta (nlgn)$。

在計算機這一塊領域中，lgn就是$lo{g}_{2}n$。我們設n除2分了一次，除2除了x次，那么最終$n/2^x$ = 1，通過指對互換進行反解，即$x=lo{g}_{2}n$。也就是說樹的高度是$lo{g}_{2}n$。而lgn只不過是$lo{g}_{2}n$的常數倍，由漸進表示可知這個不影響。所以你要拿lgn表示$lo{g}_3、lo{g}_{4}n$也是可以的。

總結

以上是生活随笔為你收集整理的MIT算法导论（一）——算法分析和引论的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。