第1章算法基礎(chǔ)1.1算法1.2算法分析1.3算法的運(yùn)行時(shí)間習(xí)題

1.1算法

算法(algorithm)可以被定義為一個(gè)良定的計(jì)算過程，它具有一個(gè)或者若干輸入值，并產(chǎn)生一個(gè)或者若干輸出值。因此，算法是由將輸入轉(zhuǎn)換成輸出的計(jì)算步驟所組成的序列。

也可將算法看做是解決良定計(jì)算問題的工具。人們采用一般術(shù)語陳述問題，確定輸入/輸出關(guān)系，而算法則是描述這種輸入/輸出關(guān)系的特定計(jì)算過程。1.1.1冒泡排序

冒泡排序(bubblesort)屬于基于交換思想的排序方法。它將相鄰的兩個(gè)元素加以比較，若左邊元素值大于右邊元素值，則將這兩個(gè)元素交換；若左邊元素值小于等于右邊元素

值，則這兩個(gè)元素位置不變。右邊元素繼續(xù)和下一個(gè)元素進(jìn)行比較，重復(fù)這個(gè)過程，直到比較到最后一個(gè)元素為止。

冒泡排序的偽代碼用過程BUBBLE-SORT表示，其參數(shù)為包含n個(gè)待排序數(shù)的數(shù)組A［1..n］。當(dāng)過程BUBBLE-SORT結(jié)束時(shí)，數(shù)組A中包含已排序的序列。1 for

i

1to

length[A]

2 dofor

j

length[A]downtoi+1

3 doifA[j]<A[j–1]

4 thenexchangeA[j]

A[j–1]

圖1-1說明了輸入實(shí)例為A=〈5，2，4，6，1，3〉時(shí)，算法BUBBLE-SORT的工作過程。對于外層for循環(huán)的每一次迭代，在A［i］位置產(chǎn)生當(dāng)前元素比較范圍A［i..n］內(nèi)的一個(gè)最小值。下標(biāo)i從數(shù)組第一個(gè)元素開始，從左向右移動，直至數(shù)組中的最后一個(gè)元素。深色陰影部分表示數(shù)組元素A［1..i］構(gòu)成的已排好的序列，淺色陰影部分表示外層循環(huán)開始時(shí)的下標(biāo)i。數(shù)組元素A［i+1..n］表示當(dāng)前正在處理的序列。圖1-1冒泡排序工作過程1.1.2循環(huán)不變式和冒泡排序算法的正確性

我們可以利用循環(huán)不變式證明算法的正確性。循環(huán)不變式具有以下三個(gè)性質(zhì)：

·初始(initialization)：在循環(huán)的第一次迭代之前，循環(huán)不變式為真。

·維持(maintenance)：如果在循環(huán)的某次迭代之前循環(huán)不變式為真，那么在下一次迭代之前，循環(huán)不變式仍然為真。

·終止(termination)：當(dāng)循環(huán)終止時(shí)，循環(huán)不變式給出有用性質(zhì)，這個(gè)性質(zhì)可以用于證明算法的正確性。下面，我們考察這些性質(zhì)是如何對冒泡排序成立的。首先證明內(nèi)層for循環(huán)的不變式。

·循環(huán)不變式：A［j］是A［j..length［A］］中的最小元素。

·初始：在內(nèi)循環(huán)第一次開始迭代之前，j=length［A］，因此，子數(shù)組A［length［A］..length［A］］中只包含一個(gè)元素，也即子數(shù)組中的最小元素，此時(shí)，循環(huán)不變

式成立。

·維持：假定在內(nèi)循環(huán)的某次迭代之前循環(huán)不變式為真，即A［j］是A［j..length［A］］中的最小元素。在下一次迭代之前，若元素A［j］<A［j－1］，則執(zhí)行冒泡算法中的第4行語句，A［j］與A［j－1］交換，于是A［j－1］是A［j－1..length［A］］中的最小元素；若A［j］≥A［j－1］

，那么不執(zhí)行第4行語句，A［j－1］仍然是A［j－1..length［A］］中的最小元素。無論哪一種情況，都能使循環(huán)不變式為真。

·終止：對于冒泡排序，當(dāng)j<i+1，即j=i時(shí)，內(nèi)層for循環(huán)結(jié)束。在內(nèi)循環(huán)不變式中，用i代替j，可得子數(shù)組A［i..length［A］］，其中A［i］是最小元素。其次，證明外層for循環(huán)的不變式。

·循環(huán)不變式：在1～4行外層for循環(huán)的每次迭代開始時(shí)，子數(shù)組A［1..i－1］中的元素有序。

·初始：在外層for循環(huán)的第一次迭代之前，i=1，因此，A［1..0］為空，循環(huán)不變式成立。

·維持：假定在外循環(huán)的某次迭代之前循環(huán)不變式為真，即子數(shù)組A［1..i－1］中的元素有序。在下一次迭代之前，由內(nèi)循環(huán)的不變式可得A［i－1］≤A［i］成立，因此，子數(shù)組A［1..i］中的元素有序。

·終止：當(dāng)i>length［A］，即i=length［A］+1時(shí)，外

層for循環(huán)結(jié)束。在外循環(huán)不變式中，用length［A］+1代替i，可得子數(shù)組A［1..length［A］］。由循環(huán)不變式得，子數(shù)組有序，而這個(gè)子數(shù)組就是整個(gè)數(shù)組。因此，整個(gè)數(shù)組有序，這表明冒泡排序算法是正確的。1.1.3偽代碼使用約定

在本書的偽代碼(pseudocode)中使用以下約定：

(1)縮進(jìn)形式表示塊結(jié)構(gòu)。

(2)while、do-while、for循環(huán)結(jié)構(gòu)(語句)以及if-then-else條件結(jié)構(gòu)(語句)分別采用類似于高級語言中的相應(yīng)表示。

(3)符號“∥”的后面是注釋部分。

(4)多重賦值i←j←e是將表達(dá)式e的值賦給變量i和變量j，這種賦值與i←e和j←e等價(jià)。

(5)變量如i、j和key是給定過程的局部變量。不經(jīng)顯式說明，不使用全局變量。

(6)通過數(shù)組名后跟索引訪問數(shù)組元素。

(7)復(fù)合數(shù)據(jù)可以組織成由屬性或域組成的對象。通過域名后跟方括號括住的對象名訪問某個(gè)特定域。

(8)通過傳值將參數(shù)傳給一個(gè)過程。被調(diào)用的過程接收參數(shù)的一個(gè)復(fù)制，如果它對某個(gè)參數(shù)賦值，則調(diào)用過程是看不到這種變化的。當(dāng)傳遞一個(gè)對象時(shí)，只是拷貝指向?qū)ο蟮?/p>

數(shù)據(jù)的指針，不拷貝它的各個(gè)域。

(9)“and”和“or”是布爾運(yùn)算符。當(dāng)對表達(dá)式“xandy”求值時(shí)，首先計(jì)算x的值，如果其值為FALSE，則整個(gè)表達(dá)式的值為FALSE，無需再計(jì)算y的值；如果x的值為TRUE，則必須計(jì)算y的值，這樣才能決定整個(gè)表達(dá)式的值。類似地，當(dāng)對表達(dá)式“xory”求值時(shí)，僅當(dāng)x的值為FALSE時(shí)，才需計(jì)算表達(dá)式y(tǒng)的值。

(10)break語句表示將控制轉(zhuǎn)移到含有break的最內(nèi)層循環(huán)語句后面的第一條語句。循環(huán)語句可以是約定(2)中所列的那些循環(huán)語句。 1.2算法分析

1.2.1冒泡排序算法分析

BUBBLE-SORT過程的時(shí)間開銷與輸入有關(guān)：1000個(gè)元素排序的時(shí)間要比10個(gè)元素的排序時(shí)間長。此外，即使對兩個(gè)具有相同元素個(gè)數(shù)的序列排序，時(shí)間也可能不同，這取決于它們已排序的程度。一般而言，算法所需時(shí)間是與輸入規(guī)模同步增長的，因而傳統(tǒng)上將一個(gè)程序的運(yùn)行時(shí)間表示為輸入規(guī)模的函數(shù)。為此，需要更仔細(xì)地定義“輸入規(guī)模”和“運(yùn)行時(shí)間”的概念。

在下面的討論中，我們先給出BUBBLE-SORT過程中每一條語句的執(zhí)行時(shí)間開銷以及執(zhí)行次數(shù)。設(shè)n=length［A］，ti為第4行執(zhí)行的次數(shù)。假定注釋部分是不可執(zhí)行的語句，不占運(yùn)行時(shí)間。該算法的總運(yùn)行時(shí)間是每一條語句的執(zhí)行時(shí)間之和，若執(zhí)行一條語句的開銷為ci，共執(zhí)行了n次這條語句，則它在總的運(yùn)行時(shí)間中占cin。對每一對開銷和執(zhí)行時(shí)間乘積求和，可得算法的運(yùn)行時(shí)間T(n)為(1.1)即使給定問題規(guī)模，算法的運(yùn)行時(shí)間也不能完全確定。例如，在冒泡排序算法中，當(dāng)輸入數(shù)組正好為升序時(shí)，出現(xiàn)最好情況(best-case)：第4行語句不執(zhí)行，即ti=0，式(1.1)最后一項(xiàng)為0。此時(shí)，運(yùn)行時(shí)間為當(dāng)輸入數(shù)組為降序時(shí)，則出現(xiàn)最壞情況(worst-case)：第4行語句的執(zhí)行次數(shù)為 ，即ti=n(n－1)/2。此時(shí)，運(yùn)行時(shí)間為1.2.2最壞情況和平均情況分析

在冒泡排序算法中，我們分析了算法在最好情況和最壞情況下的性能。在本書的后續(xù)章節(jié)中，主要考慮算法在最壞情況下的運(yùn)行時(shí)間，即對于規(guī)模n的任何輸入，算法運(yùn)行最長的時(shí)間。之所以這樣，是由于以下三個(gè)原因：

·算法的最壞情況運(yùn)行時(shí)間是任一輸入運(yùn)行時(shí)間的上界。由此可知，算法的運(yùn)行時(shí)間不會比這更長。我們無需對算法的運(yùn)行時(shí)間做出有根據(jù)的推測，并希望它不會變得更壞。

·對于某些算法，最壞情況經(jīng)常出現(xiàn)。

·算法的“平均情況”性能常常與最壞情況大致相同。上述冒泡排序算法的平均情況與最壞情況具有相同的數(shù)量級。1.2.3增長的數(shù)量級

為了更容易地分析算法，需對公式進(jìn)行簡化。首先，忽略每條語句的實(shí)際開銷，利用常量ci表示這些開銷。其次，公式an2+bn+c中的常數(shù)給出了我們并不需要的詳細(xì)信息，這些常數(shù)a、b和c依賴于ci。因此，我們可以忽略實(shí)際語句開銷，也可以忽略抽象開銷ci。

我們可以對公式做進(jìn)一步簡化，只關(guān)注運(yùn)行時(shí)間增長的數(shù)量級(orderofgrowth)。當(dāng)n很大時(shí)，相對于公式中的首項(xiàng)(leadingterm，最高階項(xiàng))，如an2，低階項(xiàng)可以忽略。另外，還可以忽略最高階項(xiàng)的系數(shù)，因?yàn)閷τ谳^大規(guī)模的輸入而言，與計(jì)算效率的增長相比，系數(shù)也是可以忽略的。因此，冒泡排序最壞情況下的運(yùn)行時(shí)間為Θ(n2)。(符號Θ的定義在下一節(jié)中給出。)如果一個(gè)算法的最壞情況運(yùn)行時(shí)間的數(shù)量級比另一個(gè)算法的數(shù)量級要低，則認(rèn)為該算法更有效。由于忽略了常數(shù)因子和低階項(xiàng)，這樣的評價(jià)對于輸入規(guī)模較小的問題會產(chǎn)生錯(cuò)誤。但對于足夠大的輸入規(guī)模n，一個(gè)最壞情況下數(shù)量級為Θ(n2)的算法要比數(shù)量級為Θ(n3)的算法運(yùn)行得快。

1.3算法的運(yùn)行時(shí)間

1.3.1函數(shù)增長

大部分算法都有一個(gè)主要參數(shù)n，它是影響算法運(yùn)行時(shí)間的最主要因素。這個(gè)參數(shù)可以是多項(xiàng)式的指數(shù)、待查找文件的大小或其他對于問題規(guī)模的抽象度量。為解決同一個(gè)問題所設(shè)計(jì)的各種算法在效率上會有很大差異，這些差異可能比個(gè)人微型計(jì)算機(jī)與巨型計(jì)算機(jī)之間的差異還大。例如，一臺巨型機(jī)進(jìn)行冒泡排序，另一臺微型計(jì)算機(jī)進(jìn)行歸并排序，它們的輸入都是一個(gè)規(guī)模為100萬的有序數(shù)組。假設(shè)巨型機(jī)每秒執(zhí)行1億條指令，微型機(jī)每秒執(zhí)行百萬條指令。又假如，一個(gè)優(yōu)秀的程序員用機(jī)器代碼在巨型機(jī)上實(shí)現(xiàn)冒泡排序，編出的程序需要執(zhí)行2n2條指令來對n個(gè)數(shù)進(jìn)行排序；另一個(gè)一般的程序員在微型機(jī)上用高級語言實(shí)現(xiàn)歸并排序算法，產(chǎn)生的代碼為50nlbn條指令。為排序100萬個(gè)數(shù)，巨型機(jī)需要的時(shí)間為

微型機(jī)需要的時(shí)間為由上述比較可以看出，由于采用了更低階的算法，即使用低效的編譯器，微型機(jī)還是比巨型機(jī)快20倍。上述例子說明，數(shù)量級的改進(jìn)可對算法效率產(chǎn)生重要影響。

表1-1列舉了算法分析中一些常見函數(shù)的相對大小,說明快的算法比快的計(jì)算機(jī)更能幫助我們在可以忍受的時(shí)間內(nèi)解決問題。例如，對于較大的n，n3/2比n(lbn)2大，而當(dāng)n取較小值時(shí)，可能n(lbn)2反而要大一些。一個(gè)準(zhǔn)確描述算法運(yùn)行時(shí)間的函數(shù)可能是這樣幾個(gè)函數(shù)的線性組合。lbn與n、n與n2之間存在著巨大差異，但要在幾個(gè)較快的算法中區(qū)分出哪個(gè)更快還需要仔細(xì)分析。表1-1常見函數(shù)值對于很多應(yīng)用問題，當(dāng)問題規(guī)模很大時(shí)，能夠解決它們的惟一方法是找到一個(gè)有效算法。表1-2列出了當(dāng)問題規(guī)模為100萬和10億時(shí)，在運(yùn)算能力分別為每秒執(zhí)行100萬、10億、1萬億條指令的計(jì)算機(jī)上，分別使用線性的、nlbn和二次的算法解決問題時(shí)所需的最小運(yùn)行時(shí)間。一個(gè)快的算法能夠使我們在較慢的機(jī)器上解決問題，而使用慢的算法，即使是在很快的機(jī)器上也仍要花費(fèi)很長的時(shí)間。表1-2解決大規(guī)模問題所需的時(shí)間1.3.2漸近表示

定義1.1如果存在三個(gè)正常數(shù)c1，c2，n0，對于所有的n≥n0，有0≤c1g(n)≤f(n)≤c2g(n)，則記作f(n)=Θ(g(n))。

圖1-2給出了函數(shù)f(n)和g(n)的直觀圖示，其中f(n)=Θ(g(n))。對于所有位于n0右邊的n值，f(n)值落在c1g(n)和c2g(n)之間，即對所有n≥n0，f(n)在一個(gè)常數(shù)因子內(nèi)與g(n)相等，其中n0是最小可能的值。我們稱g(n)是f(n)的一個(gè)漸近緊致界(asymptoticallytightbound)。

Θ(g(n))的定義要求每個(gè)元素漸近非負(fù)，即當(dāng)n充分大時(shí)f(n)非負(fù)。這就要求函數(shù)g(n)本身是非負(fù)的。圖1-2

f(n)=Θ(g(n))下面我們利用定義來證明 。首先要確定常數(shù)c1，c2，n0，使得對于所有n≥n0，有

化簡得

定義1.2如果存在兩個(gè)正常數(shù)c，n0，對于所有的n≥

n0，有0≤f(n)≤cg(n)，則記作f(n)=O(g(n))。

圖1-3給出了函數(shù)f(n)和g(n)的直觀圖示，其中f(n)=O

(g(n))。對于所有位于n0右邊的n值，f(n)的值總落在cg(n)之下，即對所有n≥n0，g(n)是計(jì)算時(shí)間f(n)的一個(gè)上界(upperbound)函數(shù)。f(n)的數(shù)量級就是g(n)。

當(dāng)我們用O表示算法的最壞情況運(yùn)行時(shí)間時(shí)，同時(shí)也隱含地給出了對任意輸入的運(yùn)行時(shí)間的上界。例如，冒泡排序的最壞情況運(yùn)行時(shí)間為O(n2)，這隱含著該算法的運(yùn)行時(shí)間

為O(n2)。圖1-3

f(n)=O(g(n))下面我們利用定義來證明n2－3n=O(n2)。首先要確定常數(shù)c和n0，使得對于所有n≥n0，有

n2－3n≤cn2

化簡得

≤c

不等式在n≥1，c≥1/3時(shí)成立。

定義1.3如果存在兩個(gè)正常數(shù)c和n0，對于所有的n≥n0，有0≤cg(n)≤f(n)，則記作f(n)=Ω(g(n))。

圖1-4給出了函數(shù)f(n)和g(n)的直觀圖示，其中f(n)=Ω(g(n))。對于所有位于n0右邊的n值，f(n)的值總落在cg(n)之上，即對所有n≥n0，g(n)是計(jì)算時(shí)間f(n)的一個(gè)下界(lowerbound)函數(shù)。

當(dāng)我們用Ω表示算法的最好情況運(yùn)行時(shí)間時(shí)，同時(shí)也隱含地給出了對任意輸入的運(yùn)行時(shí)間的下界。例如，冒泡排序算法的最好情況運(yùn)行時(shí)間為Ω(n2)，這隱含著該算法的運(yùn)行時(shí)間為Ω(n2)。因此可得，冒泡排序算法運(yùn)行時(shí)間為Ω(n2)。圖1-4

f(n)=Ω(g(n))下面我們利用定義來證明n2－3n=Ω(n2)。首先要確定常數(shù)c和n0，使得對于所有n≥n0，有

cn2≤

n2－3n

化簡得

c≤

不等式在n≥18，c≥1/6時(shí)成立。從計(jì)算時(shí)間上可以把算法分成兩類：凡可用多項(xiàng)式來對其計(jì)算時(shí)間限界的算法稱為多項(xiàng)式時(shí)間算法(polynomialtimealgorithm)；而可用指數(shù)函數(shù)來對其計(jì)算時(shí)間限界的算法稱為指數(shù)時(shí)間算法(exponentialtimealgorithm)。例如，一個(gè)計(jì)算時(shí)間為O(1)的算法，它的基本運(yùn)算執(zhí)行的次數(shù)是固定的，因此，總的時(shí)間由一個(gè)常數(shù)來限界；而一個(gè)計(jì)算時(shí)間為O(n2)的算法則由一個(gè)二次多項(xiàng)式來限界。以下六種計(jì)算時(shí)間的多項(xiàng)式時(shí)間算法最為常見，其關(guān)系為

O(1)<O(lbn)<O(n)<O(nlbn)<O(n2)<O(n3)

指數(shù)時(shí)間算法一般有O(2n)、O(n!)和O(nn)這幾種，其關(guān)系為 O(2n)<O(n!)<O(nn)

其中最為常見的是計(jì)算時(shí)間為O(2n)的算法。

習(xí)題

1-1回答以下問題：

(1)冒泡排序在最壞情況下要做多少次元素比較？最壞情況下的元素排列順序是什么？

(2)冒泡排序在最好情況下的元素排列順序是什么？在這種情況下，需要進(jìn)行多少次元素比較？

1-2利用BUBBLE-SORT排序算法，通過實(shí)例A=〈31,41,59,26,41,58〉說明該算法的運(yùn)行過程。BUBBLESORT(A)

1 for

i

1to

length[A]

2 dofor

j

length[A]downtoi+1

3 doifA[j]<A[j–1]

4 thenexchangeA[j]

A[j–1]

1-3重寫冒泡排序，排成遞減次序。

1-4假設(shè)在同一臺機(jī)器上實(shí)現(xiàn)冒泡排序和歸并排序。對于輸入規(guī)模n，冒泡排序運(yùn)行步數(shù)為8n2，歸并排序運(yùn)行步數(shù)為64nlbn。當(dāng)n為多大值時(shí)，冒泡排序優(yōu)于歸并排序？

1-5設(shè)有兩個(gè)運(yùn)行時(shí)間分別為100n2和2n的算法，要使前者快于后者，n最小為多少？

1-6比較函數(shù)的運(yùn)行時(shí)間。函數(shù)f(n)和時(shí)間t如表1-3所示。請確定時(shí)間t內(nèi)可解的最大問題規(guī)模n。假設(shè)解問題算法需花費(fèi)f(n)微秒時(shí)間。表1-3函數(shù)f(n)與時(shí)間t的對應(yīng)關(guān)系

1-7考慮查找問題。

輸入：n個(gè)數(shù)的序列A=〈a1,a2,…,an〉和一個(gè)值v。

輸出：滿足v=A［i］的下標(biāo)i。如果v不在A中，則輸出特殊值NIL。

寫出在序列A中線性查找v的偽代碼。利用循環(huán)不變式，證明你的算法是正確的。確定你所構(gòu)造的循環(huán)不變式履行了三個(gè)性質(zhì)。

1-8用Θ表示法表示函數(shù)n3/1000－100n2－100n+3。

1-9對存儲在A中的元素進(jìn)行排序。首先，找出A中的最小元素，并將最小元素與A［1］交換。然后，找出A中的次小元素，并將它與A［2］交換。對A中的前n－1個(gè)元素繼續(xù)這一過程。這個(gè)算法稱為選擇排序。給出這個(gè)算法的循環(huán)不變式。回答問題：為什么這個(gè)算法只運(yùn)行前n－1個(gè)元素，而不是所有n個(gè)元素？用Θ表示法表示該算法的最好和最壞情況下的運(yùn)行時(shí)間。

1-10對于線性查找問題，假設(shè)查找每個(gè)元素的概率相等，則平均情況下要查找多少個(gè)元素？最壞情況下要查找多少個(gè)元素？(用Θ表示法表示。)

1-11給定n個(gè)元素的集合S和一個(gè)整數(shù)x，描述一個(gè)Θ(nlbn)的算法，確定S中是否存在兩個(gè)元素，其和正好為x。

1-12設(shè)f(n)和g(n)是漸近非負(fù)函數(shù)。利用Θ表示法證明

max(f(n),g(n))=Θ(f(n)+g(n))

1-13

2n+1=O(2n)？22n=O(2n)？

1-14