算法效率分析，敏感性分析算法 程序_計算機程序設計藝術(TAOCP)精讀筆記1 - 算法分析真正應該有的樣子 Part 1...

系列文章的導航鏈接：

下篇文章Part 2導航：

作者： @張靖昆

編輯： @張浩馳

一、前言

算法效率分析？上一部分講了算法的5個特征，事實上算法還有諸如效率(Performance)、魯棒性(Robustness)等特征，效率要與有效性區分開，效率是與時空間復雜度相關的，而魯棒性是指算法應對錯誤的能力例如運行時錯誤和錯誤輸入等。Donald對這兩個特性并沒有過多介紹，只是對Performance做了一些簡單的介紹，這里我也不再贅述，因為相對比較好理解，是算法的高階特性。

在這一部分，Donald講解了在整套TAOCP的寫作中可能用到的數學知識Mathematical Preliminary，在細看了它的目錄結構后，我發現這部分似乎就是《具體數學》(Concrete Mathematics)的縮略版，而這本《具體數學》的作者之一也是Donald，哈哈哈....

所以，，我在經過“深思熟慮”之后，決定將TAOCP的學習旅程分出一個分支部分，專門學習Concrete Mathematics，也就是說，之后的TAOCP將是《具體數學》和TAOCP的并行，TAOCP部分主要講解算法部分，剛開始我讀TAOCP也是為了更具體深刻的學習算法，但是沒想到第一卷的大部頭是具體數學，真難頂。

計算機基礎與程序設計02275？所以，TAOCP部分專門講解算法，另開一個系列專門討論具體數學，大家和我一起學習吧。哈哈哈哈.....

總之，不要在意這些細節，重點還是算法，對不對，我希望可以讓大家通過這一系列的閱讀，學習到干貨，不需要記筆記，我就是要盡力做到讓大家翻著手機，就把東西學了！

二、第1卷 基本算法 - 第1章 基本概念 - Analysis of an Algorithm

這里以一個簡單算法的分析，來說明算法分析真正的樣子

問：給定

算法是程序設計的基礎對嗎？答：這簡單的要死對吧，就設定一個局部變量記錄暫時的最大值，遍歷所有數組所有元素即可。ok，按照這個方法，我們可以將算法步驟如下所示，注意算法是從上到下順序執行，然后根據條件跳轉：、

步驟1. [初始化] 令

步驟2. [邊界條件] 若

步驟3. [比較] 如果

步驟4. [改變

程序設計的基本要求？步驟5. [減小

上述步驟淺顯易懂，沒毛病。那么你將如何分析算法復雜度？當然這也是P話，踏馬的，這么簡單，不就是

嗎？沒錯，確實是，你長得最漂亮，最帥，學的最棒，你說得對。但是，卑微的我要告訴眾美女帥哥，

這樣的上界分析，算法分析還要考慮下界情況，平均情況，并且還要考慮到常系數！！！

可以說，人們確實更多關注算法的上界，為了心里有個數，了解最壞的情況，這可能適用于做決策不需要精細考察的場合，但在算法分析中，僅僅一個

不夠的，因為只關注這個可能會讓你對一個算法的了解比較片面，例如樸素排序方法中的插入排序，可能我們都知道是

，但

好了， 我要開始裝逼了，我們來看看如何分析這個算法：

算法設計技巧與分析。不妨先看一下下表，

步驟 執行次數

步驟1

步驟2

步驟3

程序設計的方法有幾種？步驟4

(一個未知量)

步驟5

這里步驟4是一個未知量，因為我不知道序列的分布是怎么樣的，因此并不清楚步驟4會被執行多少次，而對該算法的分析就是對A的研究！

so？怎么研究？嗯哼？

沒錯，就是這樣，yes！采用概率研究！當然你也可以只考慮A最好的情況和最壞的情況，比如你所選取的k一開始就是最大元素，之后每次到步驟3都會直接跳至步驟5，或者你開始選取的k是最小元素，使得步驟4始終會被執行。

下面屬于程序設計的典型算法？考慮全排列，即1個序列有多少種排列方法，根據我們的已有知識，一個包含有

，因此進行概率研究時，

個元素構成序列所有可能的樣本空間中包含

個元素，也就是求概率時的分母。下面我們列出要研究的概率式子：

***那么，重點來了，如何確定

現在我們的研究是黑盒性質的，我們并不清楚原始序列的元素是什么樣的即我們不知道原始序列有沒有相同的元素或者相同的元素有多少等等，因此我們只能一般意義上來進行概率研究，我們不能考慮元素本身的特征，要從一般意義上研究

。

舉個栗子幫助大家理解“為什么要從一般意義上研究

開始的前

個自然數(

)構成的序列，那么顯然

的概率就是

。因為只有當初始值

時，遇到序列中的

這總共10個數才會導致步驟4被執行10次，那么初始值

的初始值序列個數就是

，就是說元素

事先占了下標

的最后一個坑位，那么剩余99個元素隨意排列就行了，得到的最終序列都將導致步驟4被執行

次，所以A=10的概率顯然就是

，

為其他值也是這樣就得到了，然后很easy的就得到了

的期望。

然而這并不是我們想要的，所以這就是為什么我們必須從一般意義上研究A，否則我們的研究就必須考慮原始序列中元素的分布情況，那就多了去了，原始序列可能遵循均勻分布、正態分布、幾何分布等等等，也可能不遵循任何分布，你對每種分布都做一次研究，那你的研究就不具有很好地泛化能力，原地爆炸。

如何才能解決這個問題？這個重點我們下一篇繼續，大家可以自行思考一下先。

程序分析，感謝大家的閱讀，非常感謝！讓我們共同成長！