1.4 算法分析

如何度量一個(gè)算法的效率呢？一種方法是事后統(tǒng)計(jì)的方法，先將算法實(shí)現(xiàn)，然后輸入適當(dāng)?shù)臄?shù)據(jù)運(yùn)行，測(cè)算其時(shí)間和空間開(kāi)銷(xiāo)。事后統(tǒng)計(jì)的方法至少有以下缺點(diǎn)：① 編寫(xiě)程序?qū)崿F(xiàn)算法將花費(fèi)較多的時(shí)間和精力；② 所得實(shí)驗(yàn)結(jié)果依賴(lài)于計(jì)算機(jī)的軟硬件等環(huán)境因素，有時(shí)容易掩蓋算法本身的優(yōu)劣。通常我們采用事前分析估算的方法——漸進(jìn)復(fù)雜度（asymptoticcom-plexity），它是對(duì)算法所消耗資源的一種估算方法。

1.4.1 算法的時(shí)間復(fù)雜度

撇開(kāi)與計(jì)算機(jī)軟硬件有關(guān)的因素，影響算法時(shí)間代價(jià)的最主要因素是問(wèn)題規(guī)模。問(wèn)題規(guī)模（problom scope）是指輸入量的多少，一般來(lái)說(shuō)，它可以從問(wèn)題描述中得到。例如，找出100以?xún)?nèi)的所有素?cái)?shù)，問(wèn)題規(guī)模是100；對(duì)一個(gè)具有n個(gè)整數(shù)的數(shù)組進(jìn)行排序，問(wèn)題規(guī)模是n。一個(gè)顯而易見(jiàn)的事實(shí)是：幾乎所有的算法，對(duì)于規(guī)模更大的輸入需要運(yùn)行更長(zhǎng)的時(shí)間。例如，找出1000以?xún)?nèi)的所有素?cái)?shù)比找出100以?xún)?nèi)的所有素?cái)?shù)需要更多的時(shí)間；待排序的數(shù)據(jù)量n越大就需要越多的時(shí)間。所以運(yùn)行算法所需要的時(shí)間T是問(wèn)題規(guī)模n的函數(shù)，記作T（n）。

要精確地表示算法的運(yùn)行時(shí)間函數(shù)常常是很困難的，即使能夠給出，也可能是一個(gè)相當(dāng)復(fù)雜的函數(shù)，函數(shù)的求解本身也是相當(dāng)復(fù)雜的。為了客觀地反映一個(gè)算法的執(zhí)行時(shí)間，可以用算法中基本語(yǔ)句的執(zhí)行次數(shù)來(lái)度量算法的工作量。基本語(yǔ)句（basicstatement）是執(zhí)行次數(shù)與整個(gè)算法的執(zhí)行次數(shù)成正比的語(yǔ)句，基本語(yǔ)句對(duì)算法運(yùn)行時(shí)間的貢獻(xiàn)最大，是算法中最重要的操作。這種衡量效率的方法得出的不是時(shí)間量，而是一種增長(zhǎng)趨勢(shì)的度量。換言之，只考查當(dāng)問(wèn)題規(guī)模充分大時(shí)，算法中基本語(yǔ)句的執(zhí)行次數(shù)在漸近意義下的階，稱(chēng)作算法的漸進(jìn)時(shí)間復(fù)雜度①，簡(jiǎn)稱(chēng)時(shí)間復(fù)雜度（timecomplexity），通常用大O（讀作“大歐”）記號(hào)表示②。

定義1-1 若存在兩個(gè)正的常數(shù) c和 n0，對(duì)于任意 n≥n0，都有 T（n）≤cf（n），則稱(chēng)T（n）=O（f（n））（或稱(chēng)算法在O（f（n））中）。

該定義說(shuō)明了函數(shù)T（n）和f（n）具有相同的增長(zhǎng)趨勢(shì)，并且T（n）的增長(zhǎng)至多趨同于函數(shù)f（n）的增長(zhǎng)。大 O記號(hào)用來(lái)描述增長(zhǎng)率的上限，也就是說(shuō)，當(dāng)輸入規(guī)模為n時(shí)，算法耗費(fèi)時(shí)間的最大值，其含義如圖1-17所示。

圖1-17 大O記號(hào)的含義

算法的時(shí)間復(fù)雜度分析實(shí)際上是一種估算技術(shù)，若兩個(gè)算法中一個(gè)總是比另一個(gè)“稍快一點(diǎn)”時(shí)，它并不能判斷那個(gè)“稍快一點(diǎn)”的算法的相對(duì)優(yōu)越性。但是在實(shí)際應(yīng)用中，它被證明是很有效的，尤其是確定算法是否值得實(shí)現(xiàn)的時(shí)候。常見(jiàn)的時(shí)間復(fù)雜度如下：

O（log2n）＜O（n）＜O（nlog2n）＜O（n2）＜O（n3）＜…＜O（2n）＜O（n！）

算法的時(shí)間復(fù)雜度是衡量一個(gè)算法優(yōu)劣的重要標(biāo)準(zhǔn)。一般來(lái)說(shuō)，具有多項(xiàng)式時(shí)間復(fù)雜度的算法是可接受的、可使用的算法；而具有指數(shù)時(shí)間復(fù)雜度的算法，只有當(dāng)問(wèn)題規(guī)模足夠小的時(shí)候才是可使用的算法。表1-2給出了多項(xiàng)式增長(zhǎng)和指數(shù)增長(zhǎng)的比較。

表1-2 多項(xiàng)式增長(zhǎng)和指數(shù)增長(zhǎng)的比較

1.4.2 算法的空間復(fù)雜度

算法在運(yùn)行過(guò)程中所需的存儲(chǔ)空間包括：① 輸入/輸出數(shù)據(jù)占用的空間；② 算法本身占用的空間；③ 執(zhí)行算法需要的輔助空間。其中，輸入/輸出數(shù)據(jù)占用的空間取決于問(wèn)題，與算法無(wú)關(guān)；算法本身占用的空間雖然與算法相關(guān)，但一般其大小是固定的。所以，算法的空間復(fù)雜度（spacecomplexity）是指在算法執(zhí)行過(guò)程中所需要的輔助空間數(shù)量，也就是除算法本身和輸入/輸出數(shù)據(jù)所占用的空間外，算法臨時(shí)開(kāi)辟的存儲(chǔ)空間。

如果算法所需的輔助空間相對(duì)于問(wèn)題規(guī)模來(lái)說(shuō)是一個(gè)常數(shù)，我們稱(chēng)此算法為原地（或就地）工作；否則，這個(gè)輔助空間數(shù)量也應(yīng)該是問(wèn)題規(guī)模的函數(shù)，通常記作：

S（n）=O（f（n））

其中，n為問(wèn)題規(guī)模，分析方法與算法的時(shí)間復(fù)雜度類(lèi)似。

1.4.3 算法分析舉例

1.非遞歸算法的時(shí)間性能分析

對(duì)非遞歸算法時(shí)間復(fù)雜度的分析，關(guān)鍵是建立一個(gè)代表算法運(yùn)行時(shí)間的求和表達(dá)式，然后用漸進(jìn)符號(hào)表示這個(gè)求和表達(dá)式。

定理1-1 若A（n）=amnm+am-1nm-1+…+a1n+a0是一個(gè)m次多項(xiàng)式，則A（n）=O（nm）。

證明（略）。定理1-1說(shuō)明，在計(jì)算任何算法的時(shí)間復(fù)雜度時(shí)，可以忽略所有低次冪和最高次冪的系數(shù)，這樣能夠簡(jiǎn)化算法分析，并且使注意力集中在最重要的一點(diǎn)上——增長(zhǎng)率。

【例1-10】 ++x；

解：++x是基本語(yǔ)句，執(zhí)行次數(shù)為1，時(shí)間復(fù)雜度為O（1），稱(chēng)為常量階①。

【例1-11】 for（i=1；i＜=n；++i）

                  ++x；

解：++x是基本語(yǔ)句，執(zhí)行次數(shù)為n，時(shí)間復(fù)雜度為O（n），稱(chēng)為線(xiàn)性階。

【例1-12】 for（i=1；i＜=n；++i）

                  for（j=1；j＜=n；++j）
                    ++x；

解：++x是基本語(yǔ)句，執(zhí)行次數(shù)為n2，時(shí)間復(fù)雜度為O（n2），稱(chēng)為平方階。

【例1-13】 for（i=1；i＜=n；++i）

                  for（j=1；j＜=n；++j）
                  {
                    c[i][j]=0；
                    for（k=1；k＜=n；++k）
                      c[i][j]+=a[i][k]*b[k][j]；
                      }

解：c[i][j]+=a[i][k]*b[k][j]是基本語(yǔ)句，由于是一個(gè)三重循環(huán)，每個(gè)循環(huán)從1到n，所以總的執(zhí)行次數(shù)為n3，時(shí)間復(fù)雜度為O（n3），稱(chēng)為立方階。

【例1-14】 for（i=1；i＜=n；++i）

                  for（j=1；j＜=i-1；++j）
                    ++x；

解：++x是基本語(yǔ)句，執(zhí)行次數(shù)為：，所以時(shí)間復(fù)雜度為O（n2）。分析的策略是從內(nèi)部（或最深層部分）向外展開(kāi)。

【例1-15】 for（i=1；i＜=n；i=2*i）

                  ++x；

解：++x是基本語(yǔ)句，設(shè)其執(zhí)行次數(shù)為T（n），則有2T（n）≤n，即T（n）≤log2n，所以時(shí)間復(fù)雜度為O（log2n），稱(chēng)為對(duì)數(shù)階。

2.遞歸算法的時(shí)間性能分析

對(duì)遞歸算法時(shí)間復(fù)雜度的分析，關(guān)鍵是根據(jù)遞歸過(guò)程建立遞推關(guān)系式，然后求解這個(gè)遞推關(guān)系式。通常用擴(kuò)展遞歸技術(shù)將遞推關(guān)系式中等式右邊的項(xiàng)根據(jù)遞推式進(jìn)行替換，這稱(chēng)為擴(kuò)展，擴(kuò)展后的項(xiàng)被再次擴(kuò)展，依此下去，就會(huì)得到一個(gè)求和表達(dá)式。

【例1-16】 使用擴(kuò)展遞歸技術(shù)分析下面遞推式的時(shí)間復(fù)雜度。

解：為簡(jiǎn)單起見(jiàn)，假定n=2k。將遞推式進(jìn)行擴(kuò)展：

遞歸算法一般存在如下通用分治遞推式：

其中a，b，c，k都是常數(shù)。這個(gè)遞推式描述了將大小為n的原問(wèn)題分成若干個(gè)大小為n/b的子問(wèn)題，其中a個(gè)子問(wèn)題需要求解，而cnk為合并各個(gè)子問(wèn)題的解所需要的工作量。

定理1-2 設(shè)T（n）是一個(gè)非遞減函數(shù)，且滿(mǎn)足通用分治遞推式，則有如下結(jié)果成立：

證明略。

【例1-17】 設(shè)某算法運(yùn)行時(shí)間的遞推式描述為

分析該算法的時(shí)間復(fù)雜度。

解：根據(jù)定理1-2，有a=2，b=2，c=1，k=1成立，即滿(mǎn)足a=bk，因此T（n）=O（nlog2n）。

3.最好、最壞和平均情況

對(duì)于某些算法，即使問(wèn)題規(guī)模相同，如果輸入數(shù)據(jù)不同，其時(shí)間開(kāi)銷(xiāo)也不同。此時(shí)，就需要分析最好、最壞以及平均情況的時(shí)間性能。

【例1-18】 在一維整型數(shù)組A[n]中順序查找與給定值k相等的元素，算法如下：

            intFind（intA[]，intn）
            {
              for（i=0；i＜n；i++）
                if（A[i]==k）break；
              returni；                 //返回元素k的下標(biāo)，返回n時(shí)表示查找失敗
            }

順序查找從第一個(gè)元素開(kāi)始，依次比較每一個(gè)元素，直到找到k為止，而一旦找到了k，算法也就結(jié)束了。如果數(shù)組的第一個(gè)元素恰好就是k，算法只要比較1次就行了，這是最好情況；如果數(shù)組的最后一個(gè)元素是k，算法就要比較n次，這是最壞情況；如果在數(shù)組中查找不同的元素k，假設(shè)數(shù)據(jù)等概率分布，則平均要比較n/2次，這是平均情況。

一般來(lái)說(shuō)，最好情況不能代表算法性能，因?yàn)樗l(fā)生的概率太小，對(duì)于條件的考慮太樂(lè)觀了。但是，當(dāng)最好情況出現(xiàn)的概率較大的時(shí)候，應(yīng)該分析最好情況；分析最差情況有一個(gè)好處——可以知道算法的運(yùn)行時(shí)間最壞能壞到什么程度，這一點(diǎn)在實(shí)時(shí)系統(tǒng)中尤其重要；通常需要分析平均情況的時(shí)間代價(jià)，因?yàn)樗惴ㄒ幚聿煌妮斎霐?shù)據(jù)，而且輸入數(shù)據(jù)有不同的分布。通常假設(shè)等概率分布，例如，順序查找算法平均情況下的時(shí)間性能，如果數(shù)據(jù)不是等概率分布的，那么算法的平均情況就不一定是查找一半的元素了。