<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ??碼云GVP開源項目 12k star Uniapp+ElementUI 功能強大 支持多語言、二開方便! 廣告
                # 第?11?章?排序與查找 **目錄** + [1\. 算法的概念](ch11s01.html) + [2\. 插入排序](ch11s02.html) + [3\. 算法的時間復雜度分析](ch11s03.html) + [4\. 歸并排序](ch11s04.html) + [5\. 線性查找](ch11s05.html) + [6\. 折半查找](ch11s06.html) ## 1.?算法的概念 算法(Algorithm)是將一組輸入轉化成一組輸出的一系列計算步驟,其中每個步驟必須能在有限時間內完成。比如[第?3?節 “遞歸”](ch05s03.html#func2.recursion)習題1中的Euclid算法,輸入是兩個正整數,輸出是它們的最大公約數,計算步驟是取模、比較等操作,這個算法一定能在有限的步驟和時間內完成(想一想為什么?)。再比如將一組數從小到大排序,輸入是一組原始數據,輸出是排序之后的數據,計算步驟包括比較、移動數據等操作。 算法是用來解決一類計算問題的,注意是一類問題,而不是一個特定的問題。例如,一個排序算法應該能對任意一組數據進行排序,而不是僅對`int a[] = { 1, 3, 4, 2, 6, 5 };`這樣一組數據排序,如果只需要對這一組數據排序可以寫這樣一個函數來做: ``` void sort(void) { a[0] = 1; a[1] = 2; a[2] = 3; a[3] = 4; a[4] = 5; a[5] = 6; } ``` 這顯然不叫算法,因為不具有通用性。由于算法是用來解決一類問題的,它必須能夠正確地解決這一類問題中的任何一個實例,這個算法才是正確的。對于排序算法,任意輸入一組數據,它必須都能輸出正確的排序結果,這個排序算法才是正確的。不正確的算法有兩種可能,一是對于該問題的某些輸入,該算法會無限計算下去,不會終止,二是對于該問題的某些輸入,該算法終止時輸出的是錯誤的結果。有時候不正確的算法也是有用的,如果對于某個問題尋求正確的算法很困難,而某個不正確的算法可以在有限時間內終止,并且能把誤差控制在一定范圍內,那么這樣的算法也是有實際意義的。例如有時候尋找最優解的開銷很大,往往會選擇能給出次優解的算法。 本章介紹幾種典型的排序和查找算法,并圍繞這幾種算法做時間復雜度分析。學完本章之后如果想進一步學習,可以參考一些全面系統地介紹算法的書,例如[[TAOCP]](bi01.html#bibli.taocp "The Art of Computer Programming")和[[算法導論]](bi01.html#bibli.algorithm "Introduction to Algorithms")。 ## 2.?插入排序 插入排序算法類似于玩撲克時抓牌的過程,玩家每拿到一張牌都要插入到手中已有的牌里,使之從小到大排好序。例如(該圖出自[[算法導論]](bi01.html#bibli.algorithm "Introduction to Algorithms")): **圖?11.1.?撲克牌的插入排序** ![撲克牌的插入排序](https://box.kancloud.cn/2016-04-02_56ff80d1839ff.png) 也許你沒有意識到,但其實你的思考過程是這樣的:現在抓到一張7,把它和手里的牌從右到左依次比較,7比10小,應該再往左插,7比5大,好,就插這里。為什么比較了10和5就可以確定7的位置?為什么不用再比較左邊的4和2呢?因為這里有一個重要的前提:手里的牌已經是排好序的。現在我插了7之后,手里的牌仍然是排好序的,下次再抓到的牌還可以用這個方法插入。 編程對一個數組進行插入排序也是同樣道理,但和插入撲克牌有一點不同,不可能在兩個相鄰的存儲單元之間再插入一個單元,因此要將插入點之后的數據依次往后移動一個單元。排序算法如下: **例?11.1.?插入排序** ``` #include <stdio.h> #define LEN 5 int a[LEN] = { 10, 5, 2, 4, 7 }; void insertion_sort(void) { int i, j, key; for (j = 1; j < LEN; j++) { printf("%d, %d, %d, %d, %d\n", a[0], a[1], a[2], a[3], a[4]); key = a[j]; i = j - 1; while (i >= 0 && a[i] > key) { a[i+1] = a[i]; i--; } a[i+1] = key; } printf("%d, %d, %d, %d, %d\n", a[0], a[1], a[2], a[3], a[4]); } int main(void) { insertion_sort(); return 0; } ``` 為了更清楚地觀察排序過程,我們在每次循環開頭插了打印語句,在排序結束后也插了打印語句。程序運行結果是: ``` _10_, 5, 2, 4, 7 _5, 10_, 2, 4, 7 _2, 5, 10_, 4, 7 _2, 4, 5, 10_, 7 _2, 4, 5, 7, 10_ ``` 如何嚴格證明這個算法是正確的?換句話說,只要反復執行該算法的`for`循環體,執行`LEN-1`次,就一定能把數組`a`排好序,而不管數組`a`的原始數據是什么,如何證明這一點呢?我們可以借助Loop Invariant的概念和數學歸納法來理解循環結構的算法,假如某個判斷條件滿足以下三條準則,它就稱為Loop Invariant: 1. 第一次執行循環體之前該判斷條件為真。 2. 如果“第N-1次循環之后(或者說第N次循環之前)該判斷條件為真”這個前提可以成立,那么就有辦法證明第N次循環之后該判斷條件仍為真。 3. 如果在所有循環結束后該判斷條件為真,那么就有辦法證明該算法正確地解決了問題。 只要我們找到這個Loop Invariant,就可以證明一個循環結構的算法是正確的。上述插入排序算法的Loop Invariant是這樣的判斷條件:_第`j`次循環之前,子序列a[0..j-1]是排好序的_。在上面的打印結果中,我把子序列a[0..j-1]加粗表示。下面我們驗證一下Loop Invariant的三條準則: 1. 第一次執行循環之前,`j=1`,子序列a[0..j-1]只有一個元素`a[0]`,只有一個元素的序列顯然是排好序的。 2. 第`j`次循環之前,如果“子序列a[0..j-1]是排好序的”這個前提成立,現在要把`key=a[j]`插進去,按照該算法的步驟,把`a[j-1]`、`a[j-2]`、`a[j-3]`等等比`key`大的元素都依次往后移一個,直到找到合適的位置給`key`插入,就能證明循環結束時子序列a[0..j]是排好序的。就像插撲克牌一樣,“手中已有的牌是排好序的”這個前提很重要,如果沒有這個前提,就不能證明再插一張牌之后也是排好序的。 3. 當循環結束時,`j=LEN`,如果“子序列a[0..j-1]是排好序的”這個前提成立,那就是說a[0..LEN-1]是排好序的,也就是說整個數組`a`的`LEN`個元素都排好序了。 可見,有了這三條,就可以用數學歸納法證明這個循環是正確的。這和[第?3?節 “遞歸”](ch05s03.html#func2.recursion)證明遞歸程序正確性的思想是一致的,這里的第一條就相當于遞歸的Base Case,第二條就相當于遞歸的遞推關系。這再次說明了遞歸和循環是等價的。 ## 3.?算法的時間復雜度分析 解決同一個問題可以有很多種算法,比較評價算法的好壞,一個重要的標準就是算法的時間復雜度。現在研究一下插入排序算法的執行時間,按照習慣,輸入長度`LEN`以下用n表示。設循環中各條語句的執行時間分別是c1、c2、c3、c4、c5這樣五個常數<sup>[[23](#ftn.id2745592)]</sup>: ``` void insertion_sort(void) 執行時間 { int i, j, key; for (j = 1; j < LEN; j++) { key = a[j]; c1 i = j - 1; c2 while (i >= 0 && a[i] > key) { a[i+1] = a[i]; c3 i--; c4 } a[i+1] = key; c5 } } ``` 顯然外層`for`循環的執行次數是n-1次,假設內層的`while`循環執行m次,則總的執行時間粗略估計是(n-1)*(c1+c2+c5+m*(c3+c4))。當然,`for`和`while`后面()括號中的賦值和條件判斷的執行也需要時間,而我沒有設一個常數來表示,這不影響我們的粗略估計。 這里有一個問題,m不是個常數,也不取決于輸入長度n,而是取決于具體的輸入數據。在最好情況下,數組`a`的原始數據已經排好序了,`while`循環一次也不執行,總的執行時間是(c1+c2+c5)*n-(c1+c2+c5),可以表示成an+b的形式,是n的線性函數(Linear Function)。那么在最壞情況(Worst Case)下又如何呢?所謂最壞情況是指數組`a`的原始數據正好是從大到小排好序的,請讀者想一想為什么這是最壞情況,然后把上式中的m替換掉算一下執行時間是多少。 數組`a`的原始數據屬于最好和最壞情況的都比較少見,如果原始數據是隨機的,可稱為平均情況(Average Case)。如果原始數據是隨機的,那么每次循環將已排序的子序列a[1..j-1]與新插入的元素`key`相比較,子序列中平均都有一半的元素比`key`大而另一半比`key`小,請讀者把上式中的m替換掉算一下執行時間是多少。最后的結論應該是:在最壞情況和平均情況下,總的執行時間都可以表示成an<sup>2</sup>+bn+c的形式,是n的二次函數(Quadratic Function)。 在分析算法的時間復雜度時,我們更關心最壞情況而不是最好情況,理由如下: 1. 最壞情況給出了算法執行時間的上界,我們可以確信,無論給什么輸入,算法的執行時間都不會超過這個上界,這樣為比較和分析提供了便利。 2. 對于某些算法,最壞情況是最常發生的情況,例如在數據庫中查找某個信息的算法,最壞情況就是數據庫中根本不存在該信息,都找遍了也沒有,而某些應用場合經常要查找一個信息在數據庫中存在不存在。 3. 雖然最壞情況是一種悲觀估計,但是對于很多問題,平均情況和最壞情況的時間復雜度差不多,比如插入排序這個例子,平均情況和最壞情況的時間復雜度都是輸入長度n的二次函數。 比較兩個多項式a<sub>1</sub>n+b<sub>1</sub>和a<sub>2</sub>n<sup>2</sup>+b<sub>2</sub>n+c<sub>2</sub>的值(n取正整數)可以得出結論:n的最高次指數是最主要的決定因素,常數項、低次冪項和系數都是次要的。比如100n+1和n<sup>2</sup>+1,雖然后者的系數小,當n較小時前者的值較大,但是當n&gt;100時,后者的值就遠遠大于前者了。如果同一個問題可以用兩種算法解決,其中一種算法的時間復雜度為線性函數,另一種算法的時間復雜度為二次函數,當問題的輸入長度n足夠大時,前者明顯優于后者。因此我們可以用一種更粗略的方式表示算法的時間復雜度,把系數和低次冪項都省去,線性函數記作Θ(n),二次函數記作Θ(n<sup>2</sup>)。 Θ(g(n))表示和g(n)同一量級的一類函數,例如所有的二次函數f(n)都和g(n)=n<sup>2</sup>屬于同一量級,都可以用Θ(n<sup>2</sup>)來表示,甚至有些不是二次函數的也和n<sup>2</sup>屬于同一量級,例如2n<sup>2</sup>+3lgn。“同一量級”這個概念可以用下圖來說明(該圖出自[[算法導論]](bi01.html#bibli.algorithm "Introduction to Algorithms")): **圖?11.2.?Θ-notation** ![Θ-notation](https://box.kancloud.cn/2016-04-02_56ff80d19a8de.png) 如果可以找到兩個正的常數c<sub>1</sub>和c<sub>2</sub>,使得n足夠大的時候(也就是n≥n<sub>0</sub>的時候)f(n)總是夾在c<sub>1</sub>g(n)和c<sub>2</sub>g(n)之間,就說f(n)和g(n)是同一量級的,f(n)就可以用Θ(g(n))來表示。 以二次函數為例,比如1/2n<sup>2</sup>-3n,要證明它是屬于Θ(n<sup>2</sup>)這個集合的,我們必須確定c<sub>1</sub>、c<sub>2</sub>和n<sub>0</sub>,這些常數不隨n改變,并且當n≥n<sub>0</sub>以后,c<sub>1</sub>n<sup>2</sup>≤1/2n<sup>2</sup>-3n≤c<sub>2</sub>n<sup>2</sup>總是成立的。為此我們從不等式的每一邊都除以n<sup>2</sup>,得到c<sub>1</sub>≤1/2-3/n≤c<sub>2</sub>。見下圖: **圖?11.3.?1/2-3/n** ![1/2-3/n](https://box.kancloud.cn/2016-04-02_56ff80d1b1e0f.png) 這樣就很容易看出來,無論n取多少,該函數一定小于1/2,因此c<sub>2</sub>=1/2,當n=6時函數值為0,n&gt;6時該函數都大于0,可以取n<sub>0</sub>=7,c<sub>1</sub>=1/14,這樣當n≥n<sub>0</sub>時都有1/2-3/n≥c<sub>1</sub>。通過這個證明過程可以得出結論,當n足夠大時任何an<sup>2</sup>+bn+c都夾在c<sub>1</sub>n<sup>2</sup>和c<sub>2</sub>n<sup>2</sup>之間,相對于n<sup>2</sup>項來說bn+c的影響可以忽略,a可以通過選取合適的c<sub>1</sub>、c<sub>2</sub>來補償。 幾種常見的時間復雜度函數按數量級從小到大的順序依次是:Θ(lgn),Θ(sqrt(n)),Θ(n),Θ(nlgn),Θ(n<sup>2</sup>),Θ(n<sup>3</sup>),Θ(2<sup>n</sup>),Θ(n!)。其中,lgn通常表示以10為底n的對數,但是對于Θ-notation來說,Θ(lgn)和Θ(log<sub>2</sub>n)并無區別(想一想這是為什么),在算法分析中lgn通常表示以2為底n的對數。可是什么算法的時間復雜度里會出現lgn呢?回顧插入排序的時間復雜度分析,無非是循環體的執行時間乘以循環次數,只有加和乘運算,怎么會出來lg呢?下一節歸并排序的時間復雜度里面就有lg,請讀者留心lg運算是從哪出來的。 除了Θ-notation之外,表示算法的時間復雜度常用的還有一種Big-O notation。我們知道插入排序在最壞情況和平均情況下時間復雜度是Θ(n<sup>2</sup>),在最好情況下是Θ(n),數量級比Θ(n<sup>2</sup>)要小,那么總結起來在各種情況下插入排序的時間復雜度是O(n<sup>2</sup>)。Θ的含義和“等于”類似,而大O的含義和“小于等于”類似。 * * * <sup>[[23](#id2745592)]</sup> 受內存管理機制的影響,指令的執行時間不一定是常數,但執行時間的上界(Upper Bound)肯定是常數,我們這里假設語句的執行時間是常數只是一個粗略估計。 ## 4.?歸并排序 插入排序算法采取增量式(Incremental)的策略解決問題,每次添一個元素到已排序的子序列中,逐漸將整個數組排序完畢,它的時間復雜度是O(n<sup>2</sup>)。下面介紹另一種典型的排序算法--歸并排序,它采取分而治之(Divide-and-Conquer)的策略,時間復雜度是Θ(nlgn)。歸并排序的步驟如下: 1. Divide: 把長度為n的輸入序列分成兩個長度為n/2的子序列。 2. Conquer: 對這兩個子序列分別采用歸并排序。 3. Combine: 將兩個排序好的子序列合并成一個最終的排序序列。 在描述歸并排序的步驟時又調用了歸并排序本身,可見這是一個遞歸的過程。 **例?11.2.?歸并排序** ``` #include <stdio.h> #define LEN 8 int a[LEN] = { 5, 2, 4, 7, 1, 3, 2, 6 }; void merge(int start, int mid, int end) { int n1 = mid - start + 1; int n2 = end - mid; int left[n1], right[n2]; int i, j, k; for (i = 0; i < n1; i++) /* left holds a[start..mid] */ left[i] = a[start+i]; for (j = 0; j < n2; j++) /* right holds a[mid+1..end] */ right[j] = a[mid+1+j]; i = j = 0; k = start; while (i < n1 && j < n2) if (left[i] < right[j]) a[k++] = left[i++]; else a[k++] = right[j++]; while (i < n1) /* left[] is not exhausted */ a[k++] = left[i++]; while (j < n2) /* right[] is not exhausted */ a[k++] = right[j++]; } void sort(int start, int end) { int mid; if (start < end) { mid = (start + end) / 2; printf("sort (%d-%d, %d-%d) %d %d %d %d %d %d %d %d\n", start, mid, mid+1, end, a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7]); sort(start, mid); sort(mid+1, end); merge(start, mid, end); printf("merge (%d-%d, %d-%d) to %d %d %d %d %d %d %d %d\n", start, mid, mid+1, end, a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7]); } } int main(void) { sort(0, LEN-1); return 0; } ``` 執行結果是: ``` sort (0-3, 4-7) 5 2 4 7 1 3 2 6 sort (0-1, 2-3) 5 2 4 7 1 3 2 6 sort (0-0, 1-1) 5 2 4 7 1 3 2 6 merge (0-0, 1-1) to 2 5 4 7 1 3 2 6 sort (2-2, 3-3) 2 5 4 7 1 3 2 6 merge (2-2, 3-3) to 2 5 4 7 1 3 2 6 merge 0-1, 2-3) to 2 4 5 7 1 3 2 6 sort (4-5, 6-7) 2 4 5 7 1 3 2 6 sort (4-4, 5-5) 2 4 5 7 1 3 2 6 merge (4-4, 5-5) to 2 4 5 7 1 3 2 6 sort (6-6, 7-7) 2 4 5 7 1 3 2 6 merge (6-6, 7-7) to 2 4 5 7 1 3 2 6 merge (4-5, 6-7) to 2 4 5 7 1 2 3 6 merge (0-3, 4-7) to 1 2 2 3 4 5 6 7 ``` `sort`函數把a[start..end]平均分成兩個子序列,分別是a[start..mid]和a[mid+1..end],對這兩個子序列分別遞歸調用`sort`函數進行排序,然后調用`merge`函數將排好序的兩個子序列合并起來,由于兩個子序列都已經排好序了,合并的過程很簡單,每次循環取兩個子序列中最小的元素進行比較,將較小的元素取出放到最終的排序序列中,如果其中一個子序列的元素已取完,就把另一個子序列剩下的元素都放到最終的排序序列中。為了便于理解程序,我在`sort`函數開頭和結尾插了打印語句,可以看出調用過程是這樣的: **圖?11.4.?歸并排序調用過程** ![歸并排序調用過程](https://box.kancloud.cn/2016-04-02_56ff80d1c1cd0.png) 圖中S表示`sort`函數,M表示`merge`函數,整個控制流程沿虛線所示的方向調用和返回。由于`sort`函數遞歸調用了自己兩次,所以各函數之間的調用關系呈樹狀結構。畫這個圖只是為了清楚地展現歸并排序的過程,讀者在理解遞歸函數時一定不要全部展開來看,而是要抓住Base Case和遞推關系來理解。我們分析一下歸并排序的時間復雜度,以下分析出自[[算法導論]](bi01.html#bibli.algorithm "Introduction to Algorithms")。 首先分析`merge`函數的時間復雜度。在`merge`函數中演示了C99的新特性--可變長數組,當然也可以避免使用這一特性,比如把`left`和`right`都按最大長度`LEN`分配。不管用哪種辦法,定義數組并分配存儲空間的執行時間都可以看作常數,與數組的長度無關,常數用Θ-notation記作Θ(1)。設子序列a[start..mid]的長度為`n1`,子序列[mid+1..end]的長度為`n2`,a[start..end]的總長度為n=n1+n2,則前兩個`for`循環的執行時間是Θ(n1+n2),也就是Θ(n),后面三個`for`循環合在一起看,每走一次循環就會在最終的排序序列中確定一個元素,最終的排序序列共有n個元素,所以執行時間也是Θ(n)。兩個Θ(n)再加上若干常數項,`merge`函數總的執行時間仍是Θ(n),其中n=end-start+1。 然后分析`sort`函數的時間復雜度,當輸入長度n=1,也就是`start==end`時,`if`條件不成立,執行時間為常數Θ(1),當輸入長度n&gt;1時: 總的執行時間?=?2?×?輸入長度為n/2的`sort`函數的執行時間?+?`merge`函數的執行時間Θ(n) 設輸入長度為n的`sort`函數的執行時間為T(n),綜上所述: ![](https://box.kancloud.cn/2016-04-02_56ff80d1d9867.png) 這是一個遞推公式(Recurrence),我們需要消去等號右側的T(n),把T(n)寫成n的函數。其實符合一定條件的Recurrence的展開有數學公式可以套,這里我們略去嚴格的數學證明,只是從直觀上看一下這個遞推公式的結果。當n=1時可以設T(1)=c<sub>1</sub>,當n&gt;1時可以設T(n)=2T(n/2)+c<sub>2</sub>n,我們取c<sub>1</sub>和c<sub>2</sub>中較大的一個設為c,把原來的公式改為: ![](https://box.kancloud.cn/2016-04-02_56ff80d1ec291.png) 這樣計算出的結果應該是T(n)的上界。下面我們把T(n/2)展開成2T(n/4)+cn/2(下圖中的(c)),然后再把T(n/4)進一步展開,直到最后全部變成T(1)=c(下圖中的(d)): ![](https://box.kancloud.cn/2016-04-02_56ff80d208f6a.png) 把圖(d)中所有的項加起來就是總的執行時間。這是一個樹狀結構,每一層的和都是cn,共有lgn+1層,因此總的執行時間是cnlgn+cn,相比nlgn來說,cn項可以忽略,因此T(n)的上界是Θ(nlgn)。 如果先前取c<sub>1</sub>和c<sub>2</sub>中較小的一個設為c,計算出的結果應該是T(n)的下界,然而推導過程一樣,結果也是Θ(nlgn)。既然T(n)的上下界都是Θ(nlgn),顯然T(n)就是Θ(nlgn)。 和插入排序的平均情況相比歸并排序更快一些,雖然`merge`函數的步驟較多,引入了較大的常數、系數和低次項,但是對于較大的輸入長度n,這些都不是主要因素,歸并排序的時間復雜度是Θ(nlgn),而插入排序的平均情況是Θ(n<sup>2</sup>),這就決定了歸并排序是更快的算法。但是不是任何情況下歸并排序都優于插入排序呢?哪些情況適用插入排序而不適用歸并排序?留給讀者思考。 ### 習題 1、快速排序是另外一種采用分而治之策略的排序算法,在平均情況下的時間復雜度也是Θ(nlgn),但比歸并排序有更小的時間常數。它的基本思想是這樣的: ``` int partition(int start, int end) { 從a[start..end]中選取一個pivot元素(比如選a[start]為pivot); 在一個循環中移動a[start..end]的數據,將a[start..end]分成兩半, 使a[start..mid-1]比pivot元素小,a[mid+1..end]比pivot元素大,而a[mid]就是pivot元素; return mid; } void quicksort(int start, int end) { int mid; if (end > start) { mid = partition(start, end); quicksort(start, mid-1); quicksort(mid+1, end); } } ``` 請補完`partition`函數,這個函數有多種寫法,請選擇時間常數盡可能小的實現方法。想想快速排序在最好和最壞情況下的時間復雜度是多少?快速排序在平均情況下的時間復雜度分析起來比較復雜,有興趣的讀者可以參考[[算法導論]](bi01.html#bibli.algorithm "Introduction to Algorithms")。 ## 5.?線性查找 有些查找問題要用時間復雜度為O(n)的算法來解決。例如寫一個`indexof`函數,從任意輸入字符串中找出某個字母的位置并返回這個位置,如果找不到就返回-1: **例?11.3.?線性查找** ``` #include <stdio.h> char a[]="hello world"; int indexof(char letter) { int i = 0; while (a[i] != '\0') { if (a[i] == letter) return i; i++; } return -1; } int main(void) { printf("%d %d\n", indexof('o'), indexof('z')); return 0; } ``` 這個實現是最直觀和最容易想到的,但它是不是最快的算法呢?我們知道插入排序也比歸并排序更容易想到,但通常不如歸并排序快。那么現在這個問題--給定一個隨機排列的序列,找出其中某個元素的位置--有沒有比O(n)更快的算法?比如O(lgn)?請讀者思考一下。 ### 習題 1、實現一個算法,在一組隨機排列的數中找出最小的一個。你能想到的最直觀的算法一定是Θ(n)的,想想有沒有比Θ(n)更快的算法? 2、在一組隨機排列的數中找出第二小的,這個問題比上一個稍復雜,你能不能想出Θ(n)的算法? 3、進一步泛化,在一組隨機排列的數中找出第k小的,這個元素稱為k-th Order Statistic。能想到的最直觀的算法肯定是先把這些數排序然后取第k個,時間復雜度和排序算法相同,可以是Θ(nlgn)。這個問題雖然比前兩個問題復雜,但它也有平均情況下時間復雜度是Θ(n)的算法,將上一節習題1的快速排序算法稍加修改就可以解決這個問題: ``` /* 從start到end之間找出第k小的元素 */ int order_statistic(int start, int end, int k) { 用partition函數把序列分成兩半,中間的pivot元素是序列中的第i個; if (k == i) 返回找到的元素; else if (k > i) 從后半部分找出第k-i小的元素并返回; else 從前半部分找出第k小的元素并返回; } ``` 請編程實現這個算法。 ## 6.?折半查找 如果不是從一組隨機的序列里查找,而是從一組排好序的序列里找出某個元素的位置,則可以有更快的算法: **例?11.4.?折半查找** ``` #include <stdio.h> #define LEN 8 int a[LEN] = { 1, 2, 2, 2, 5, 6, 8, 9 }; int binarysearch(int number) { int mid, start = 0, end = LEN - 1; while (start <= end) { mid = (start + end) / 2; if (a[mid] < number) start = mid + 1; else if (a[mid] > number) end = mid - 1; else return mid; } return -1; } int main(void) { printf("%d\n", binarysearch(5)); return 0; } ``` 由于這個序列已經從小到大排好序了,每次取中間的元素和待查找的元素比較,如果中間的元素比待查找的元素小,就說明“如果待查找的元素存在,一定位于序列的后半部分”,這樣可以把搜索范圍縮小到后半部分,然后再次使用這種算法迭代。這種“每次將搜索范圍縮小一半”的思想稱為折半查找(Binary Search)。思考一下,這個算法的時間復雜度是多少? 這個算法的思想很簡單,不是嗎?可是[[編程珠璣]](bi01.html#bibli.pearls "Programming Pearls")上說作者在課堂上講完這個算法的思想然后讓學生寫程序,有90%的人寫出的程序中有各種各樣的Bug,讀者不信的話可以不看書自己寫一遍試試。這個算法容易出錯的地方很多,比如`mid = (start + end) / 2;`這一句,在數學概念上其實是`mid = ?(start + end) / 2?`,還有`start = mid + 1;`和`end = mid - 1;`,如果前者寫成了`start = mid;`或后者寫成了`end = mid;`那么很可能會導致死循環(想一想什么情況下會死循環)。 怎樣才能保證程序的正確性呢?在[第?2?節 “插入排序”](ch11s02.html#sortsearch.insertion)我們講過借助Loop Invariant證明循環的正確性,`binarysearch`這個函數的主體也是一個循環,它的Loop Invariant可以這樣描述:_待查找的元素`number`如果存在于數組`a`之中,那么一定存在于a[start..end]這個范圍之間,換句話說,在這個范圍之外的數組`a`的元素中一定不存在`number`這個元素_。以下為了書寫方便,我們把這句話表示成`mustbe(start, end, number)`。可以一邊看算法一邊做推理: ``` int binarysearch(int number) { int mid, start = 0, end = LEN - 1; /* 假定a是排好序的 */ /* mustbe(start, end, number),因為a[start..end]就是整個數組a[0..LEN-1] */ while (start <= end) { /* mustbe(start, end, number),因為一開始進入循環時是正確的,每次循環也都維護了這個條件 */ mid = (start + end) / 2; if (a[mid] < number) /* 既然a是排好序的,a[start..mid]應該都比number小,所以mustbe(mid+1, end, number) */ start = mid + 1; /* 維護了mustbe(start, end, number) */ else if (a[mid] > number) /* 既然a是排好序的,a[mid..end]應該都比number大,所以mustbe(start, mid-1, number) */ end = mid - 1; /* 維護了mustbe(start, end, number) */ else /* a[mid] == number,說明找到了 */ return mid; } /* * mustbe(start, end, number)一直被循環維護著,到這里應該仍然成立,在a[start..end]范圍之外一定不存在number, * 但現在a[start..end]是空序列,在這個范圍之外的正是整個數組a,因此整個數組a中都不存在number */ return -1; } ``` 注意這個算法有一個非常重要的前提--`a`是排好序的。缺了這個前提,“如果`a[mid] &lt; number`,那么a[start..mid]應該都比`number`小”這一步推理就不能成立,這個函數就不能正確地完成查找。從更普遍的意義上說,函數的調用者(Caller)和函數的實現者(Callee,被調用者)之間訂立了一個契約(Contract),在調用函數之前,Caller要為Callee提供某些條件,比如確保`a`是排好序的,確保a[start..end]都是有效的數組元素而沒有訪問越界,這稱為Precondition,然后Callee對一些Invariant進行維護(Maintenance),這些Invariant保證了Callee在函數返回時能夠對Caller盡到某些義務,比如確保“如果`number`在數組`a`中存在,一定能找出來并返回它的位置,如果`number`在數組`a`中不存在,一定能返回-1”,這稱為Postcondition。如果每個函數的文檔都非常清楚地記錄了Precondition、Maintenance和Postcondition是什么,那么每個函數都可以獨立編寫和測試,整個系統就會易于維護。這種編程思想是由Eiffel語言的設計者Bertrand Meyer提出來的,稱為Design by Contract(DbC)。 測試一個函數是否正確需要把Precondition、Maintenance和Postcondition這三方面都測試到,比如`binarysearch`這個函數,即使它寫得非常正確,既維護了Invariant也保證了Postcondition,如果調用它的Caller沒有保證Precondition,最后的結果也還是錯的。我們編寫幾個測試用的Predicate函數,然后把相關的測試插入到`binarysearch`函數中: **例?11.5.?帶有測試代碼的折半查找** ``` #include <stdio.h> #include <assert.h> #define LEN 8 int a[LEN] = { 1, 2, 2, 2, 5, 6, 8, 9 }; int is_sorted(void) { int i; for (i = 1; i < LEN; i++) if (a[i-1] > a[i]) return 0; return 1; } int mustbe(int start, int end, int number) { int i; for (i = 0; i < start; i++) if (a[i] == number) return 0; for (i = end+1; i < LEN; i++) if (a[i] == number) return 0; return 1; } int contains(int n) { int i; for (i = 0; i < LEN; i++) if (a[i] == n) return 1; return 0; } int binarysearch(int number) { int mid, start = 0, end = LEN - 1; assert(is_sorted()); /* Precondition */ while (start <= end) { assert(mustbe(start, end, number)); /* Maintenance */ mid = (start + end) / 2; if (a[mid] < number) start = mid + 1; else if (a[mid] > number) end = mid - 1; else { assert(mid >= start && mid <= end && a[mid] == number) /* Postcondition 1 */ return mid; } } assert(!contains(number)); /* Postcondition 2 */ return -1; } int main(void) { printf("%d\n", binarysearch(5)); return 0; } ``` `assert`是頭文件`assert.h`中的一個宏定義,執行到`assert(is_sorted())`這句時,如果`is_sorted()`返回值為真,則當什么事都沒發生過,繼續往下執行,如果`is_sorted()`返回值為假(例如把數組的排列順序改一改),則報錯退出程序: ``` main: main.c:33: binarysearch: Assertion `is_sorted()' failed. Aborted ``` 在代碼中適當的地方使用斷言(Assertion)可以有效地幫助我們測試程序。也許有人會問:我們用幾個測試函數來測試`binarysearch`,那么這幾個測試函數又用什么來測試呢?在實際工作中我們要測試的代碼絕不會像`binarysearch`這么簡單,而我們編寫的測試函數往往都很簡單,比較容易保證正確性,也就是用簡單的、不容易出錯的代碼去測試復雜的、容易出錯的代碼。 測試代碼只在開發和調試時有用,如果正式發布(Release)的軟件也要運行這些測試代碼就會嚴重影響性能了,如果在包含`assert.h`之前定義一個`NDEBUG`宏(表示No Debug),就可以禁用`assert.h`中的`assert`宏定義,這樣代碼中的所有`assert`測試都不起作用了: ``` #define NDEBUG #include <stdio.h> #include <assert.h> ... ``` 注意`NDEBUG`和我們以前使用的宏定義有點不同,例如`#define N 20`將`N`定義為20,在預處理時把代碼中所有的標識符`N`替換成20,而`#define NDEBUG`把`NDEBUG`定義為空,在預處理時把代碼中所有的標識符`NDEBUG`替換成空。這樣的宏定義主要是為了用`#ifdef`等預處理指示測試它定義過沒有,而不是為了做替換,所以定義成什么值都無所謂,一般定義成空就足夠了。 還有另一種辦法,不必修改源文件,在編譯命令行加上選項`-DNDEBUG`就相當于在源文件開頭定義了`NDEBUG`宏。宏定義和預處理到[第?21?章 _預處理_](ch21.html#prep)再詳細解釋,在[第?4?節 “其它預處理特性”](ch21s04.html#prep.other)將給出`assert.h`一種實現。 ### 習題 1、本節的折半查找算法有一個特點:如果待查找的元素在數組中有多個則返回其中任意一個,以本節定義的數組`int a[8] = { 1, 2, 2, 2, 5, 6, 8, 9 };`為例,如果調用`binarysearch(2)`則返回3,即`a[3]`,而有些場合下要求這樣的查找返回`a[1]`,也就是說,如果待查找的元素在數組中有多個則返回第一個。請修改折半查找算法實現這一特性。 2、編寫一個函數`double mysqrt(double y);`求`y`的正平方根,參數`y`是正實數。我們用折半查找來找這個平方根,在從0到`y`之間必定有一個取值是`y`的平方根,如果我們查找的數`x`比`y`的平方根小,則x<sup>2</sup>&lt;y,如果我們查找的數`x`比`y`的平方根大,則x<sup>2</sup>&gt;y,我們可以據此縮小查找范圍,當我們查找的數足夠準確時(比如滿足|x<sup>2</sup>-y|&lt;0.001),就可以認為找到了`y`的平方根。思考一下這個算法需要迭代多少次?迭代次數的多少由什么因素決定? 3、編寫一個函數`double mypow(double x, int n);`求`x`的`n`次方,參數`n`是正整數。最簡單的算法是: ``` double product = 1; for (i = 0; i < n; i++) product *= x; ``` 這個算法的時間復雜度是Θ(n)。其實有更好的辦法,比如`mypow(x, 8)`,第一次循環算出x·x=x<sup>2</sup>,第二次循環算出x<sup>2</sup>·x<sup>2</sup>=x<sup>4</sup>,第三次循環算出<sup>4</sup>·x<sup>4</sup>=x<sup>8</sup>。這樣只需要三次循環,時間復雜度是Θ(lgn)。思考一下如果`n`不是2的整數次冪應該怎么處理。請分別用遞歸和循環實現這個算法。 從以上幾題可以看出,折半查找的思想有非常廣泛的應用,不僅限于從一組排好序的元素中找出某個元素的位置,還可以解決很多類似的問題。[[編程珠璣]](bi01.html#bibli.pearls "Programming Pearls")對于折半查找的各種應用和優化技巧有非常詳細的介紹。
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看