摘要
????? 本文論述了在算法分析領域一個重要問題——時間復雜度分析的基礎內容。本文將首先明確時間復雜度的意義，而后以形式化方式論述其在數學上的定義及相關推導。從而幫助大家從本質上認清這個概念。

前言
????? 通常，對于一個給定的算法，我們要做? 兩項分析。 第一是從數學上證明算法的正確性 ，這一步主要用到形式化證明的方法及相關推理模式，如循環不變式、數學歸納法等。而在證明算法是正確的基礎上， 第二部就是分析算法的時間復雜度 。算法的時間復雜度反映了程序執行時間隨輸入規模增長而增長的量級，在很大程度上能很好反映出算法的優劣與否。因此，作為程序員，掌握基本的算法時間復雜度分析方法是很有必要的。
????? 但是很多朋友并不能清晰的理解這一概念，究其原因，主要是因為沒有從數學層面上理解其本質，而是習慣于從直觀理解。下面，我們就一步步走近算法時間復雜度的數學本質。

算法時間復雜度的數學意義
????? 從數學上定義， 給定算法A，如果存在函數F(n)，當n=k時，F(k)表示算法A在輸入規模為k的情況下的運行時間，則稱F(n)為算法A的時間復雜度 。
????? 這里我們首先要明確輸入規模的概念。關于輸入規模，不是很好下定義，非嚴格的講，輸入規模是指算法A所接受輸入的自然獨立體的大小。例如，對于排序算法來說，輸入規模一般就是待排序元素的個數，而對于求兩個同型方陣乘積的算法，輸入規模可以看作是單個方陣的維數。為了簡單起見，在下面的討論中，我們總是假設算法的輸入規模是用大于零的整數表示的，即n=1,2,3,……,k,……
????? 我們還知道，對于同一個算法，每次執行的時間不僅取決于輸入規模，還取決于輸入的特性和具體的硬件環境在某次執行時的狀態。所以想要得到一個統一精確的F(n)是不可能的。為了解決這個問題，我們做一下兩個說明：
????? 1.忽略硬件及環境因素，假設每次執行時硬件條件和環境條件是完全一致的。
????? 2.對于輸入特性的差異，我們將從數學上進行精確分析并帶入函數解析式。

算法時間復雜度分析示例
????? 為了便于朋友們理解，我將不會采用教科書上慣用的快速排序、合并排序等經典示例進行分析，而是使用一個十分簡單的算法作為示例。我們先來定義問題。
????? 問題定義：
????? 輸入——此問題輸入為一個有序序列，其元素個數為n，n為大于零的整數。序列中的元素為從1到n這n個整數，但其順序為完全隨機。
????? 輸出——元素n所在的位置。（第一個元素位置為1）

????? 這個問題非常簡單，下面直接給出其解決算法之一（偽代碼）：

?????? LocationN(A)
????? {
??????????? for(int i=1;i<=n;i++)-----------------------t1
??????????? {
????????????????? if(A[i] == n) ----------------------------t2
??????????????????????? {?return i;?}------------------------t3
??????????? }
??????}

????? 我們來看看這個算法。其中t1、t2和t3分別表示此行代碼執行一次需要的時間。
????? 首先，輸入規模n是影響算法執行時間的因素之一。在n固定的情況下，不同的輸入序列也會影響其執行時間。最好情況下，n就排在序列的第一個位置，那么此時的運行時間為“t1+t2+t3”。最壞情況下，n排在序列最后一位，則運行時間為“n*t1+n*t2+t3=(t1+t2)*n+t3”。可以看到，最好情況下運行時間是一個常數，而最壞情況下運行時間是輸入規模的線性函數。那么，平均情況如何呢？
????? 問題定義說輸入序列完全隨機，即n出現在1...n這n個位置上是等可能的，即概率均為1/n。而平均情況下的執行次數即為執行次數的數學期望，其解為：

?????? E
????? = p(n=1)*1+p(n=2)*2+...+p(n=n)*n
????? = (1/n)*(1+2+...+n)
????? = (1/n)*((n/2)*(1+n))
????? = (n+1)/2

????? 即在平均情況下for循環要執行(n+1)/2次，則平均運行時間為“(t1+t2)*(n+1)/2+t3”。
????? 由此我們得出分析結論：
????? t1+t2+t3 <= F(n) <= (t1+t2)*n+t3，在平均情況下F(n) = (t1+t2)*(n+1)/2+t3

算法的漸近時間復雜度
????? 以上分析，我們對算法的時間復雜度F(n)進行了精確分析。但是，很多時候，我們不需要進行如此精確的分析，原因有下：
????? 1.在較復雜的算法中，進行精確分析是非常復雜的。
????? 2.實際上，大多數時候我們并不關心F(n)的精確度量，而只是關心其量級。
????? 基于此，提出漸近時間復雜度的概念。在正式給出漸近時間復雜度之前，要先給出幾個數學定義：

?????? 定義一：Θ(g(n))={f(n) | 如果存在正常數c1、c2和正整數n0，使得當n>=n0時，0<c1g(n)<=f(n)<=c2g(n)恒成立}
????? 定義二：Ο(g(n))={f(n) | 如果存在正常數c和正整數n0，使得當n>=n0時，0<=f(n)<=cg(n)恒成立}
????? 定義三：Ω(g(n))={f(n) | 如果存在正常數c和正整數n0，使得當n>=n0時，0<=cg(n)<=f(n)恒成立}

????? 可以看到，三個定義其實都定義了一個函數集合，只不過集合中的函數需要滿足的條件不同。有了以上定義，就可以定義漸近時間復雜度了。
????? 不過這里還有個問題：F(n)不是確定的，他是在一個范圍內變動的，那么我們關心哪個F(n)呢？一般我們在分析算法時，使用最壞情況下的F(n)來評價算法效率，原因有如下兩點：
????? 1.如果知道了最壞情況，我們就可以保證算法在任何時候都不能比這個情況更壞了。
????? 2.很多時候，算法運行發生最壞情況的概率還是很大的，如查找問題中待查元素不存在的情況。且在很多時候，平均情況的漸近時間復雜度和最壞情況的漸近時間復雜度是一個量級的。

????? 于是給出如下定義： 設F(n)為算法A在最壞情況下F(n)，則如果F(n)屬于Θ(g(n))，則說算法A的漸近時間復雜度為g(n)，且g(n)為F(n)的漸近確界 。

????? 還是以上面的例子為例，則在上面定義中F(n) = (t1+t2)*n+t3。則F(n)的漸近確界為n，其證明如下：

?????? 證明：
????? 設c1=t1+t2，c2=t1+t2+t3，n0=2
????? 又因為 t1,t2,t3均大于0
????? 則，當n>n0時，0<c1n<=F(n)<=c2n 即 0<(t1+t2)*n<=(t1+t2)*n+t3<=(t1+t2+t3)*n恒成立。
????? 所以 F(n)屬于Θ(n)
????? 所以 n是F(n)的漸近確界
????? 證畢

?????? 在實際應用中，我們一般都是使用漸近時間復雜度代替實際時間復雜度來進行算法效率分析。一般認為，一個漸近復雜度為n的算法要優于漸近復雜度為n^2的算法。注意，這并不是說漸近復雜度為n的算法在任何情況下都一定更高效，而是說在輸入規模足夠大后（大于臨界條件n0），則前一個算法的最壞情況總是好于后一個算法的最壞情況。 事實證明，在實踐中這種分析是合理且有效的。
????? 類似的，還可以給出算法時間復雜度的上確界和下確界? ：
?????? 設F(n)為算法A在最壞情況下F(n)，則如果F(n)屬于Ο(g(n))，則說算法A的漸近時間復雜度上限為g(n)，且g(n)為F(n)的漸近上確界。
????? 設F(n)為算法A在最壞情況下F(n)，則如果F(n)屬于Ω(g(n))，則說算法A的漸近時間復雜度下限為g(n)，且g(n)為F(n)的漸近下確界。
????? 這里一定要注意， 由于我們是以F(n)最壞情況分析的，所以，我們可以100%保證在輸入規模超過臨界條件n0時，算法的運行時間一定不會高于漸近上確界，但是并不能100%保證算法運行時間不會低于漸近下確界，而只能100%保證算法的最壞運行時間不會低于漸近下確界。

總結
????? 算法時間復雜度分析是一個很重要的問題，任何一個程序員都應該熟練掌握其概念和基本方法，而且要善于從數學層面上探尋其本質，才能準確理解其內涵。在以上分析中，我們只討論了“緊確界”，其實在實際中漸近確界還分為“緊確界”和“非緊確界”，有興趣的朋友可以查閱相關資料。

????? 好了，本文就到這里了，希望本文內容能對各位有所幫助。

from：?http://www.cnblogs.com/leoo2sk/archive/2008/11/14/1332381.html

總結

以上是生活随笔為你收集整理的算法时间复杂度分析基础的全部內容，希望文章能夠幫你解決所遇到的問題。

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