眾所周知,算法所需的時間應當是隨著其輸入規模增長的，而輸入規模與特定具體問題有關。對大多數問題來說其最自然的度量就是輸入中的元素個數。算法的運行時間是指在特定輸入時所執行的基本操作數。我們可以得到關于一個關于輸入規模n的所需時間的函數。然而可以進一步簡化算法的時間分析，我們進行進一步抽象，首先，忽略每條語句的真實代價，通過運行時間的增長率來度量一個算法在時間方面的表現。我們只考慮公式的最高次項，并忽略它的常數系數。本博文主要介紹一些相關的數學知識即:函數的漸近的界的定義與性質.常用的證明方法. ### 漸近符號 當輸入規模大到使運行時間只和增長的量級有關時，就是在研究算法的 漸近 效率。就是說，從極限角度看，我們只關心算法運行時間如何隨著輸入規模的無限增長而增長。表示算法的漸近運行時間的記號是用定義域為自然數集 N = {0， 1， 2， …} 的函數來定義的。這些記號便于用來表示最壞情況運行時間 T ( n )。 #### *Θ* 記號(**讀音:theta**) 對一個給定的函數 *g* ( *n* )，用 *Θ* ( *g* ( *n* ))來表示函數集合：  對任何一個函數 *f* ( *n* )，若存在正常數 *c1* ， *c2* ，使當 *n* 充分大時， *f* ( *n* )能被夾在 *c1 g* ( *n* )和 *c2 g* ( *n* )之間，則 *f* ( *n* )屬于集合 *Θ* ( *g* ( *n* ))。可以寫成“ *f* ( *n* ) ∈ *Θ* ( *g* ( *n* ))”表示 *f* ( *n* )是 *Θ* ( *g* ( *n* ))的元素。不過，通常寫成“ *f* ( *n* ) = *Θ* ( *g* ( *n* ))”來表示相同的意思。  上圖給出了函數 *f* ( *n* )和 *g* ( *n* )的直觀圖示，其中 *f* ( *n* ) = *Θ* ( *g* ( *n* ))。對所有位于 *n0* 右邊的 *n* 值， *f* ( *n* )的值落在 *c1 g* ( *n* )和 *c2 g* ( *n* )之間。換句話說，對所有的 *n* >= *n0* ， *f* ( *n* )在一個常數因子范圍內與 *g* ( *n* )相等。我們說 *g* ( *n* )是 *f* ( *n* )的一個 **漸近確界**。*Θ* ( *g* ( *n* ))的定義要求每個成員 *f* ( *n* ) ∈ *Θ* ( *g* ( *n* ))都是 **漸近非負**，就是說當 *n* 足夠大時 *f* ( *n* )是非負值。這就要求函數 *g* ( *n* )本身也是漸近非負的，否則集合 *Θ* ( *g* ( *n* ))就是空集。*Θ* 記號的效果相當于舍棄了低階項和忽略了最高階項的系數。 #### *O* 符號 *Θ* 記號漸近地給出了一個函數的上界和下界。當只有 **漸近**上界時，使用 *O* 記號。對一個函數 *g* ( *n* )，用 *O* ( *g* ( *n* ))表示一個函數集合：  上圖說明了 *O* 記號的直觀意義。對所有位于 *n0* 右邊的 *n* 值，函數 *f* ( *n* )的值在 *g* ( *n* )下。 [![clip_image002[10]](https://box.kancloud.cn/5830ff47f8743bc1ec107f4666226ffb_104x42.png "clip_image002[10]")](http://images.cnblogs.com/cnblogs_com/zabery/201107/201107192011436308.png)， 則可以表示為 f(n) = O(n2)。證明：要使得 0 <= f(n) <= cg(n)????? [![clip_image002[12]](https://box.kancloud.cn/0bab581d328aa6eb03c99486016c950f_198x42.png "clip_image002[12]")](http://images.cnblogs.com/cnblogs_com/zabery/201107/201107192011542187.png) [](http://images.cnblogs.com/cnblogs_com/zabery/201107/201107192012001003.png) [](http://images.cnblogs.com/cnblogs_com/zabery/201107/201107192012005605.png) 存在c = 9/2 ,n0 = 1,使得對所有的n >= n0都有 0 <= f(n) <= cg(n)。O(g(n) 以及后面講到的記號表示的都是集合，而f(n) = O(n2)的實際意義 是 f(n) ∈ O(n2)。假設有 [![clip_image002[14]](https://box.kancloud.cn/1a837264b2834af446bb6e81a3131268_90x31.png "clip_image002[14]")](http://images.cnblogs.com/cnblogs_com/zabery/201107/201107192012029377.png) ， [![clip_image002[10]](https://box.kancloud.cn/5830ff47f8743bc1ec107f4666226ffb_104x42.png "clip_image002[10]")](http://images.cnblogs.com/cnblogs_com/zabery/201107/201107192012055392.png)則 g(n) = O(n2) , f(n) = O(n2) #### **o* 記號* *O* 記號提供的漸近上界可能是也可能不是漸近緊確的。這里用 *o* 記號表示非漸近緊確的上界。 *o* ( *g* ( *n* ))的形式定義為集合：  *O* 記號與 *o* 記號的主要區別在于對 *f* ( *n* ) = *O* ( *g* ( *n* ))，界0 <= *f* ( *n* ) <= *c g* ( *n* )對某個常數 *c* > 0成立；但對 *f* ( *n* ) = *o* ( *g* ( *n* ))，界0 <= *f* ( *n* ) <= *c g* ( *n* )對所有常數 *c* > 0都成立。即  #### **Ω* 記號* *Ω* 記號給出了函數的漸近下界。給定一個函數 *g* ( *n* )，用 *Ω* ( *g* ( *n* ))表示一個函數集合：  上圖說明了 *Ω* 記號的直觀意義。對所有在 *n0* 右邊的 *n* 值，函數 *f* ( *n* )的數值等于或大于 *c g* ( *n* )。 **定理**? 對任意兩個函數 *f* ( *n* )和 *g* ( *n* )， *f* ( *n* ) = *Θ* ( *g* ( *n* ))當且僅當 *f* ( *n* ) = *O* ( *n* )和 *f* ( *n* ) = *Ω* ( *g* ( *n* ))。 #### *ω* 記號 我們用 *ω* 記號來表示非漸近緊確的下界。 *ω* ( *g* ( *n* ))的形式定義為集合：  關系 *f* ( *n* ) = *ω* ( *g* ( *n* ))意味著  如果這個極限存在。也就是說當 *n* 趨于無窮時， *f* ( *n* )相對 *g* ( *n* )來說變得任意大了。 #### 函數間的比較 設 *f* ( *n* )和 *g* ( *n* )是漸近正值函數。 **傳遞性：** - *f* ( *n* ) = *Θ* ( *g* ( *n* ))和 *g* ( *n* ) = *Θ* ( *h* ( *n* )) 蘊含 *f* ( *n* ) = *Θ* ( *h* ( *n* )) - *f* ( *n* ) = *O* ( *g* ( *n* ))和 *g* ( *n* ) = *O* ( *h* ( *n* )) 蘊含 *f* ( *n* ) = *O* ( *h* ( *n* )) - *f* ( *n* ) = *Ω* ( *g* ( *n* ))和 *g* ( *n* ) = *Ω* ( *h* ( *n* )) 蘊含 *f* ( *n* ) = *Ω* ( *h* ( *n* )) - *f* ( *n* ) = *o* ( *g* ( *n* ))和 *g* ( *n* ) = *o* ( *h* ( *n* )) 蘊含 *f* ( *n* ) = *o* ( *h* ( *n* )) - *f* ( *n* ) = *ω* ( *g* ( *n* ))和 *g* ( *n* ) = *ω* ( *h* ( *n* )) 蘊含 *f* ( *n* ) = *ω* ( *h* ( *n* )) **自反性：** - *f* ( *n* ) = *Θ* ( *f* ( *n* )) - *f* ( *n* ) = *O* ( *f* ( *n* )) - *f* ( *n* ) = *Ω* ( *f* ( *n* )) **對稱性：** - *f* ( *n* ) = *Θ* ( *g* ( *n* ))當且僅當 *g* ( *n* ) = *Θ* ( *f* ( *n* )) **轉置對稱性：** - *f* ( *n* ) = *O* ( *g* ( *n* ))當且僅當 *g* ( *n* ) = *Ω* ( *f* ( *n* )) - *f* ( *n* ) = *o* ( *g* ( *n* ))當且僅當 *g* ( *n* ) = *ω* ( *f* ( *n* )) ### 求解遞歸式的方法。 #### 遞歸樹法 遞歸樹法是一種解遞歸式比較特別的方法，在第一節將歸并排序的時候有用到過這個方法。它最棒的一點就是總是能用，它能告訴你一種直覺讓你知道答案是多少，只是有些不嚴謹。所以用這個方法時要特別小心，不然可能會得到錯的答案。因為它需要用到點、點、點，使用省略號來得到結論。  #### 主定理方法 主定理方法本質上可以認為是遞歸樹方法的一個應用，但是它更精確。不同于遞歸樹方法有省略號有待證明，主定理方法基于一個定理（主定理）。遺憾的是，主方法限制頗多只能應用到特定的遞歸式上。主方法是計算時間復雜度的時候用的  那么這里我在取一個不滿足主定理的例子~  所以主定理不滿足時就利用決策樹進行帶入吧！如果數學計算能力比較強大還是可以計算出來的，畢竟主定理都是決策樹證明的，數學能力不強表示證明有點困難... 不過這里有個偷懶的證明方法，直接假設f（n）是一個nk形式的； T（n）=aT（n/b）+nk T（n/b）=aT（n/b2）+（n/b）k ... 所以T(n)=a（aT（n/b2）+（n/b）k）+nk=nk（1+a/bk+...+(a/bk)h)=(nk-nlogba)/(1-a/bk),接下來討論a和bk的關系決定了為nk還是nlogba，上面如果為1則為nklogbn了。 簡單的證明， 替換法舉一個例子如下：  關于[程序算法藝術與實踐](http://blog.csdn.net/column/details/tac-programalgrithm.html)更多討論與交流，敬請關注本博客和新浪微博[songzi_tea](http://weibo.com/songzitea).