《算法基礎：打開算法之門》一2.2 如何描述運作時間

本節書摘來自華章出版社《算法基礎：打開算法之門》一書中的第2章，第2.2節，作者 ［美］托馬斯 h 科爾曼（thomas h cormen），更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視

讓我們回顧一下linearsearch程式并計算它的運作時間。回顧第1章的知識可得，運作時間可以表示成一個關于輸入規模的函數。這裡，輸入是一個包含n個元素的數組a，元素數目n，及要查找的值x。随着數組中元素規模的增加，n本身的大小和x的值對運作時間影響不大——畢竟，n僅僅是一個簡單的整數且x僅僅可能與數組的n個元素中的某個元素值一樣大——是以，這裡所提到的輸入規模n指的是數組a中元素的數目。

為了表示完成一項任務所花的時間，我們必須做一些簡單的假設。我們将假定每步單獨的操作——無論它是一個算術運算（例如加、減、乘、除）、比較、變量指派、給數組标記索引操作，或者是程式調用、從程式中傳回結果操作——均會花掉不依賴于輸入規模的固定時間。如果對實際的計算機體系結構有一點了解，那麼你可能知道存取一個指定變量或者通路數組元素的時間并不一定是固定的，因為它可能取決于變量/數組元素是否在緩存、主存，或者在虛拟存儲系統的磁盤外存上。某些精密的計算機模型也将這些因素考慮在内，但是隻通過假定所有變量和數組項均存在主存中，且存取這些元素均需要同樣的時間就足以達到很好的效果了。操作不同，各個操作所花費的時間可能也不同，例如除法操作可能比加法操作會花更長的時間。但是當一個步驟僅僅是由多個簡單操作疊加而成時，該步驟會花費常量時間。由于各個步驟中所執行的操作所花費的時間不同，且根據第1章中所列舉出的各種外在因素的影響可以得出執行不同步驟所花費的時間也是不一樣的。現我們約定執行第i步所需花費的時間為ti，其中ti是不依賴于輸入規模n的常量。當然，我們必須将某一步驟會執行多次考慮在内。第1步和第3步僅僅執行一次，但是第2步呢？我們必須對i和n的值比較n+1次：即判斷i≤n是否成立n次，并且一旦i等于n+1，我們立即跳出循環。第2a步執行n次，當i從1到n變化時，對于每個i值，我們執行一次循環體。我們并不能預知我們有多少次将i的值賦給了answer；這個次數可能是從0次（如果x并未出現在數組中時）到n次（如果數組中的每個值均等于x）的任意一種可能。17如果我們要精确地計算執行次數——但是通常我們不會進行那麼精确的計算——我們應該認識到第2步會執行兩個具有不同循環次數的操作：測試比較i和n的值會執行n+1次，但是自增i的值僅僅會執行n次。讓我們将第2行的操作次數區分開來，其中t′2表示比較操作的時間，t″2表示遞增操作的時間。同樣地，我們将第2a步中判斷a［i］是否等于x的操作時間記為t′2a，把i值賦給answer的操作時間記為t″2a。是以，linearsearch的運作時間介于

和

之間。現在重寫上、下界，并将所有能表示成n的倍數的項組合在一起，而将其他項組合在一起，這時我們可以看到運作時間介于下界

和上界

之間。觀察可得上、下界均可表示成cn+d的形式，其中c和d均表示不依賴于n的常量。也就是說，它們均是關于n的線性函數。linearsearch的運作時間介于關于n的一個線性函數和關于n的另一個線性函數之間。我們用一個特殊符号來表示運作時間大于關于n的某線性函數，同時小于關于n的某個線性函數（可能與上述線性函數不同）。我們将這樣的運作時間表示為Θ（n）。Θ是希臘字母theta，并且我們稱它為“theta of n”或者“theta n”。正如第1章所指出的那樣，這個符号去除了低階項（t1+t′2+t3）和n的系數（對于下界，n的系數是t′2+t″2+t′2a；對于上界，n的系數是t′2+t″2+t′2a+t″2a）。盡管我們用Θ（n）來表示運作時間會降低精度，但是它強調了運作時間的增長階數，同時弱化了不必要的細節。這個Θ符号适合于任何通用的函數，而不僅僅是那些用來描述算法運作時間的函數，并且它也适用于非線性函數。這個想法正如當我們有兩個函數f(n)和g(n)，且n足夠大時，f(n)在g(n)的常數倍之内，18此時我們稱f(n)=Θ（g(n)）。是以我們說當n足夠大時，linearsearch的運作時間小于等于n的某個常數倍。關于Θ符号有一個嚴格定義，但幸運的是，當使用Θ符号時，我們很少求助于它。我們僅僅關心主階項，而忽略低階項和主階項的常數因子。例如，函數n2/4+100n+50等價于Θ（n2）；這個例子中我們忽略了低階項100n和常數項50，并且舍棄了常數因子1/4。盡管當n較小時，相對于n2/4，低階項會起主導作用。一旦n超過了400，n2/4會超過100n+50。當n=1000時，主階項n2/4等于250000，而低階項100n+50僅僅會達到100050；對于n=2000，此時n2/4等于1000000，而100n+50等于200050。在算法領域中，有時候我們會濫用符号而寫作f(n)=Θ（g(n)），是以我們可以寫作n2/4+100n+50=Θ（n2）。現在讓我們看看betterlinearsearch程式的運作時間。由于我們事先并不知道循環的疊代次數，這一程式比linearsearch更複雜一些。如果a［1］等于x，那麼循環隻會疊代一次。如果x沒有在數組中出現，那麼循環會疊代n次，這是出現得最多的循環次數。每次循環疊代需要花費常量時間，是以我們稱在最壞情況下，betterlinearsearch在一個包含n個元素的數組中進行查找操作需要花費Θ（n）時間。為什麼要用“最壞情況下”呢？因為我們想要得到運作時間少的算法，最壞情況下發生在對任何可能的輸入，一個算法花費最多時間的時候。在最好情況下，當a［1］等于x時，betterlinearsearch僅僅會花費常量時間：将i指派為1，檢查i≤n，此時a［i］=x為真，并且程式傳回i的值，即傳回1。該時間不依賴于n。我們将betterlinearsearch在最好情況下的運作時間寫作Θ（1），因為在最好情況下，它的運作時間在1的常數因子之内。換句話說，最好情況下的運作時間是一個不依賴于n的常量。是以我們看到了不能使用Θ來涵蓋betterlinearsearch運作時間的所有情況。我們不能說運作時間總是Θ（n），因為在最好情況下，運作時間是Θ（1）。我們也不能說運作時間總是Θ（1），因為在最壞情況下，運作時間是Θ（n）。然而，我們說關于n的一個線性函數是所有情況下的一個上界，并且我們用一個符号來表示：o（n）。在念這個符号時，19我們說“bigoh of n”或者僅僅稱之為“oh of n”。如果一個函數f(n)是o（g(n)），即一旦n變得非常大，f(n)的上界是關于g(n)的常數因子倍，寫作f(n)=o（g(n)）。對于betterlinearsearch，我們可以稱在所有情況下，該算法的運作時間均滿足o（n)；盡管它的運作時間可能會比關于n的某個線性函數運作時間好，但是它一定不會比關于n的所有線性函數運作時間都差。我們使用o符号來表示該運作時間從不會比關于n的某個函數的常量倍差，但是如何表示不會比關于n的某個函數的常量倍好呢？這是一個下界問題，此時我們使用Ω符号，這與o符号的含義恰恰相反：如果f(n）是Ω(g(n)），即一旦n變得非常大時，f(n）的下界是g(n)的常數倍，寫作f(n)=Ω(g(n)）。由于o符号給出了上界，Ω符号給出了下界，Θ符号既給出了上界，又給出了下界，我們能推斷出f(n）是Θ（g(n)），當且僅當f(n)是o（g(n))且f(n)是Ω(g(n))。我們能對betterlinearsearch的運作時間給出一個滿足所有情況的下界：在所有情況下該運作時間均是Ω(1)。當然，那是一個相對較弱的聲明，我們知道對于任何輸入的任何算法均至少需要花費常量時間。我們并不會經常使用Ω符号，但是它偶爾也會派上用場。Θ符号、o符号和Ω符号這幾個符号均是漸近符号。因為這些符号記錄了随着變量近似趨向于無窮大時函數的增長趨勢。所有這些漸近符号均使得我們去掉了低階項和高階項的常數因子，以便能夠淡化不必要的細節而專注于主要方面：函數是如何随着n增長而變化的。現在讓我們轉向講述sentinellinearsearch程式。正如betterlinearsearch一樣，循環的每次疊代均需要花費常量時間，并且最少會執行1次疊代，最多執行n次疊代。sentinellinearsearch和betterlinearsearch的最大不同是，sentinellinearsearch每次疊代花費的時間小于betterlinearsearch每次疊代花費的時間。兩者在最壞情況下均需要花費線性時間，但是sentinellinearsearch的常數因子更小一些。盡管我們設想sentinellinearsearch在實際程式設計條件下運作速度更快，但那也僅僅可能是因為它的常量因子較小引起的。當我們使用漸近符号來表示betterlinearsearch和sentinellinearsearch的運作時間時，20它們是相等的，即在最壞情況下均是Θ（n），在最好情況下均是Θ（1），滿足所有條件時均為o（n）。