1、第第1章章 計算問題計算問題1.1計算問題及其算法計算問題及其算法 所謂計算問題計算問題，指的是問題中所涉及的事物或其屬性可用數(shù)據(jù)加以表示稱為輸入輸入數(shù)據(jù)數(shù)據(jù)，問題的解也可以表示成數(shù)據(jù)稱為輸出數(shù)據(jù)輸出數(shù)據(jù)，并且可以在有限步基本計算（算術(shù)運算、邏輯運算以及數(shù)據(jù)的暫存等）后，將特定的輸入數(shù)據(jù)轉(zhuǎn)換成正確的輸出數(shù)據(jù)的問題。解計算問題就是將輸入數(shù)據(jù)轉(zhuǎn)換成正確的輸出數(shù)據(jù)的過程。計算問題例計算問題例查找問題查找問題 輸入輸入：n個數(shù)構(gòu)成的序列A=，序列中指定的范圍起點p和終點q，特定值x。 輸出輸出：若序列A的指定部分Ap.q中存在元素，其值等于x，返回從左到右的第一個值為x的元素在序列A中的位置下標。否則

2、，返回-1。算法及其設(shè)計算法及其設(shè)計 將問題描述成其輸入與輸出后，就要考慮按什么樣的順序安排有限步的基本計算，將輸入數(shù)據(jù)轉(zhuǎn)換成輸出數(shù)據(jù)，這個過程稱為算法設(shè)計。安排好的計算步驟稱為解決計算問題的算法算法。一個算法對問題輸入的任何特定數(shù)據(jù)都能得到正確的輸出數(shù)據(jù)，則稱算法是正確的。線性查找示意圖線性查找示意圖 在線性表A=中查找特定值x的元素。(a)查找值為x=1的元素，從A1起依次要做5次檢測。(b)查找值為x=11的元素，從A1起依次檢測完所有元素（作10次檢測），沒有找到值為11的元素。(c)查找值為x=3的元素，從A1起僅做一次檢測就找到值為3的元素。線性查找算法的為代碼過程線性查找算法的為

3、代碼過程 LINEAR-SEARCH(A, x) 1 nlengthA n表示序列A中元素個數(shù) 2 i1 從A1開始 3 while i n逐一檢測Ai的值是否等于x 4 do if Ai=x 5 then return i若存在Ai=x，則返回i 6 ii+1 7 return -1偽代碼的使用約定偽代碼的使用約定用分層縮進來指示塊結(jié)構(gòu)。循環(huán)結(jié)構(gòu)while、for和repeat以及條件結(jié)構(gòu)if、then和else具有與計算機高級程序設(shè)計語言相仿的解釋。符號“”表示本行其余部分是注釋。多重賦值形式i j e對變量i和j同賦予表達式e的值。變量（如i、j及key）都局部于給定的過程。數(shù)組元素是通

4、過數(shù)組名后跟括在方括號內(nèi)的下標來訪問。組合數(shù)據(jù)通常組織在對象對象中，其中組合了若干個屬性屬性或域域。用域名緊跟包括在方括號中的對象名來訪問一個具體的域。例如，為說明數(shù)組A的元素個數(shù)的屬性，我們寫lengthA。過程的參數(shù)是按值按值傳遞的：被調(diào)用的過程以拷貝的方式接受參數(shù)，若對參數(shù)賦值，則主調(diào)過程不能看到這一變化。布爾運算符and和or都是短回路短回路的。算法分析算法分析 解決同一問題的不同的算法，消耗的時間和空間資源量可能有所不同。算法運行所需要的計算機資源的量稱為算法的復(fù)雜性復(fù)雜性。一般來說，解決同一問題的算法，需要的資源量越少，我們認為越優(yōu)秀。計算算法運行所需資源量的過程稱為算法復(fù)雜性分析

5、，簡稱為算法分析算法分析。算法運行時間算法運行時間 為客觀、科學(xué)地評估算法的時間復(fù)雜性，我們設(shè)置一臺抽象的計算機。它只用一個處理機，卻有無限量的隨機存儲器。它的有限個基本操作算術(shù)運算、邏輯運算和數(shù)據(jù)的移動（比如對變量的賦值）均在有限固定時間內(nèi)完成，我們進一步假定所有這些基本操作都消耗一個時間單位。稱此抽象計算機為隨機訪問計算機，簡記為RAM（Random Access Machine）。算法在RAM上運行時所需的時間，顯然就是執(zhí)行基本操作的次數(shù)。 把算法的運行時間記為T，輸入的規(guī)模記為n。則根據(jù)以上說明知T是n的正值遞增函數(shù)，我們以T(n)來表示算法的運行時間。3種情形運行時間種情形運行時間對

6、固定的輸入規(guī)模，使得運算時間最長的輸入所消耗的運行時間稱為算法的最壞情形時最壞情形時間間。而對固定的輸入規(guī)模，使運行時間最短的輸入所消耗的時間，稱為最好情形時間最好情形時間。假定對固定的輸入規(guī)模n，所有不同輸入構(gòu)成的集合為Dn，對問題的每一個輸入IDn，若已知該輸入發(fā)生的概率為P(I)，對應(yīng)的運行時間為T(I)，運行時間的數(shù)學(xué)期望值 稱為算法的平均情形時間平均情形時間。算法運行時間的漸近表示算法運行時間的漸近表示 對算法的運行時間T(n)，用幾個定義在自然數(shù)集N上的正值函數(shù)(n)：冪函數(shù)nk（k為正整數(shù)），對數(shù)冪函數(shù)lgkn（k為正整數(shù)，底數(shù)為2）和指數(shù)函數(shù)an（a為大于1的常數(shù)）作為“標準”

7、，研究極限： 若為一正常數(shù)，我們稱(n)是T(n)的漸近表達式，或稱T(n)漸近等于漸近等于(n)，記為T(n)=(n)，這個記號稱為算法運行時間的漸近-記號，簡稱為-記號。( )lim( )nnT nY n%O記號和記號和 記號記號 考察定義域為自然數(shù)集N的正值函數(shù)(n)和 T(n)構(gòu)成的極限式 的值，若 為常數(shù)10，則稱函數(shù)T(n)漸近不超過函數(shù)(n)，記為T(n) = O (n)；若1為常數(shù)或為+，則稱函數(shù)T(n)漸近不小于函數(shù)(n)，記為T(n)= (n)。( )lim( )nnT nY n%1.2 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 簡單地說，數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)就是研究如何在計算機中表示一個集合，該集合

8、中的元素間有著某種特殊關(guān)系。 把集合的元素按某種關(guān)系進行組織，稱為數(shù)據(jù)的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)。例如，集合可以有線性結(jié)構(gòu)或樹結(jié)構(gòu)。 具有邏輯結(jié)構(gòu)的集合在內(nèi)存中的存儲方式，稱為數(shù)據(jù)的存儲結(jié)構(gòu)。集合的存儲結(jié)構(gòu)通常分為連續(xù)結(jié)構(gòu)連續(xù)結(jié)構(gòu)和離散結(jié)構(gòu)離散結(jié)構(gòu)兩種。線性結(jié)構(gòu)與樹結(jié)構(gòu)圖示線性結(jié)構(gòu)與樹結(jié)構(gòu)圖示字典與字典操作字典與字典操作設(shè)S為具有n個數(shù)據(jù)元素的集合： INSERT(S, x)，在集合S中插入關(guān)鍵值為x的數(shù)據(jù)元素，即SS x。 SEARCH(S, x)，在集合S中查找關(guān)鍵值為x的數(shù)據(jù)元素，即判斷是否xS。 DELETE(S, x)，在集合S中刪掉元素x，即SS-x。上述三個對集合的操作稱為字典操作字典操

9、作，實現(xiàn)了字典操作的集合簡稱為字典字典。1.3 程序設(shè)計程序設(shè)計計算機程序就是用一種計算機程序設(shè)計語言，將算法表示成計算機能執(zhí)行的數(shù)據(jù)操作指令序列。盡管程序代碼與算法的偽代碼十分相似，但我們要強調(diào)的是用偽代碼描述的算法并不等同于程序。這主要出于如下幾個原因：（1）算法的偽代碼描述著眼于算法思想的簡明闡述，高度抽象是它的最基本的特征之一。（2）算法的偽代碼描述有時并不關(guān)心數(shù)據(jù)的存儲格式。例如，在算法中無須說明序列是存儲在一個數(shù)組中還是存儲在一個鏈表中，這在程序中卻是必須明確聲明的。（3）算法偽代碼描述對變量無須事先聲明，讀者只要在上下文中能識別各變量及其用途就可以了。而在大多數(shù)計算機高級語言中所

10、有的變量都必須先定義后使用。將算法實現(xiàn)為程序?qū)⑺惴▽崿F(xiàn)為程序 將算法的偽代碼過程實現(xiàn)為程序中的函數(shù)或方法需要仔細考慮如下三個要點。參數(shù)與返回值參數(shù)與返回值 。我們知道，偽代碼過程的參數(shù)反映了待解決的計算問題的輸入，而過程可能的返回值，表示該問題的輸出。對于實現(xiàn)算法過程的函數(shù)或方法而言，必須考慮要用多少個參數(shù)表示算法過程的各個參數(shù)（程序中可能需要多個參數(shù)表示算法中的一個參數(shù)），它們各自是什么類型的。數(shù)據(jù)設(shè)置數(shù)據(jù)設(shè)置 。由于C語言中對所有的變量必須先定義后使用，所以我們要考察算法過程中所需要訪問的所有數(shù)據(jù)變量，對每個變量考慮它的數(shù)據(jù)類型、存儲類型、訪問限制和初始值等。關(guān)鍵代碼關(guān)鍵代碼。 前面談到，偽代碼的表述可以是很簡約的，其抽象程度可能是目前的程序設(shè)計語言所不能企及的，這就需要用程序設(shè)計語言提供的技術(shù)來為計算機將這些偽代碼的抽象描述解釋為計算機可理解的語句或表達式。1.5 計數(shù)問題計數(shù)問題 科學(xué)的皇冠是數(shù)學(xué)。數(shù)學(xué)起源于計數(shù)。人們的生活離不開計數(shù)。 簡單的計數(shù)問題可眼看心算。 問題涉及一個計數(shù)過程時，可以模擬這個過程實現(xiàn)計數(shù)。 復(fù)雜的計數(shù)問題大多需要用到加法原理和乘法原理。加法原理和乘法原理加法原理和乘法原理 加法原理：加法原理：做一件事，完成它可以有n類辦法，