摘要
      本文論述了在算法分析領(lǐng)域一個(gè)重要問題——時(shí)間復(fù)雜度分析的基礎(chǔ)內(nèi)容。本文將首先明確時(shí)間復(fù)雜度的意義，而后以形式化方式論述其在數(shù)學(xué)上的定義及相關(guān)推導(dǎo)。從而幫助大家從本質(zhì)上認(rèn)清這個(gè)概念。
　　前言
      通常，對(duì)于一個(gè)給定的算法，我們要做兩項(xiàng)分析。第一是從數(shù)學(xué)上證明算法的正確性，這一步主要用到形式化證明的方法及相關(guān)推理模式，如循環(huán)不變式、數(shù)學(xué)歸納法等。而在證明算法是正確的基礎(chǔ)上，第二部就是分析算法的時(shí)間復(fù)雜度。算法的時(shí)間復(fù)雜度反映了程序執(zhí)行時(shí)間隨輸入規(guī)模增長(zhǎng)而增長(zhǎng)的量級(jí)，在很大程度上能很好反映出算法的優(yōu)劣與否。因此，作為程序員，掌握基本的算法時(shí)間復(fù)雜度分析方法是很有必要的。
      但是很多朋友并不能清晰的理解這一概念，究其原因，主要是因?yàn)闆]有從數(shù)學(xué)層面上理解其本質(zhì)，而是習(xí)慣于從直觀理解。下面，我們就一步步走近算法時(shí)間復(fù)雜度的數(shù)學(xué)本質(zhì)。

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

　　算法時(shí)間復(fù)雜度分析示例
      為了便于朋友們理解，我將不會(huì)采用教科書上慣用的快速排序、合并排序等經(jīng)典示例進(jìn)行分析，而是使用一個(gè)十分簡(jiǎn)單的算法作為示例。我們先來定義問題。
      問題定義：
      輸入——此問題輸入為一個(gè)有序序列，其元素個(gè)數(shù)為n，n為大于零的整數(shù)。序列中的元素為從1到n這n個(gè)整數(shù)，但其順序?yàn)橥耆S機(jī)。
      輸出——元素n所在的位置。（第一個(gè)元素位置為1）

      這個(gè)問題非常簡(jiǎn)單，下面直接給出其解決算法之一（偽代碼）：

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

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

      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循環(huán)要執(zhí)行(n+1)/2次，則平均運(yùn)行時(shí)間為“(t1+t2)*(n+1)/2+t3”。
      由此我們得出分析結(jié)論：
      t1+t2+t3 <= F(n) <= (t1+t2)*n+t3，在平均情況下F(n) = (t1+t2)*(n+1)/2+t3

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

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

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

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

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

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

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

　　總結(jié)
      算法時(shí)間復(fù)雜度分析是一個(gè)很重要的問題，任何一個(gè)程序員都應(yīng)該熟練掌握其概念和基本方法，而且要善于從數(shù)學(xué)層面上探尋其本質(zhì)，才能準(zhǔn)確理解其內(nèi)涵。在以上分析中，我們只討論了“緊確界”，其實(shí)在實(shí)際中漸近確界還分為“緊確界”和“非緊確界”，有興趣的朋友可以查閱相關(guān)資料。
      好了，本文就到這里了，希望本文內(nèi)容能對(duì)各位有所幫助。

it知識(shí)庫：算法時(shí)間復(fù)雜度分析基礎(chǔ)，轉(zhuǎn)載需保留來源！

鄭重聲明：本文版權(quán)歸原作者所有，轉(zhuǎn)載文章僅為傳播更多信息之目的，如作者信息標(biāo)記有誤，請(qǐng)第一時(shí)間聯(lián)系我們修改或刪除，多謝。