計(jì)算機(jī)知識(shí)點(diǎn)第1章算法概述

算法設(shè)計(jì)與分析安吉堯2關(guān)于本課程課程目的：計(jì)算機(jī)算法設(shè)計(jì)與分析導(dǎo)引以算法設(shè)計(jì)為主，介紹算法設(shè)計(jì)的主要方法和基本思想；并簡(jiǎn)要介紹算法分析概念不是程序設(shè)計(jì)課，也不是數(shù)學(xué)課授課形式：上課+作業(yè)/實(shí)驗(yàn)+期末考試參考資料：Web資源,,…圖書(shū)資源,…3第1章算法概述本章知識(shí)要點(diǎn)：1.1算法與程序1.2算法與數(shù)據(jù)結(jié)構(gòu)1.3表達(dá)算法的抽象機(jī)制1.4描述算法與算法設(shè)計(jì)1.5算法分析的基本原則1.6算法復(fù)雜性分析C++程序語(yǔ)言描述算法計(jì)劃授課時(shí)間：4課時(shí)41.1 算法與程序算法：是滿足下述性質(zhì)的指令序列。輸入：有零個(gè)或多個(gè)外部量作為算法的輸入。輸出：算法產(chǎn)生至少一個(gè)量作為輸出。確定性：組成算法的每條指令清晰、無(wú)歧義。有限性：算法中每條指令的執(zhí)行次數(shù)有限，執(zhí)行每條指令的時(shí)間也有限。程序：程序是算法用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。程序可以不滿足算法的性質(zhì)(4)即有限性。例如操作系統(tǒng)，是一個(gè)在無(wú)限循環(huán)中執(zhí)行的程序，因而不是一個(gè)算法。操作系統(tǒng)的各種任務(wù)可看成是單獨(dú)的問(wèn)題，每一個(gè)問(wèn)題由操作系統(tǒng)中的一個(gè)子程序通過(guò)特定的算法來(lái)實(shí)現(xiàn)。該子程序得到輸出結(jié)果后便終止。51.2 算法與數(shù)據(jù)結(jié)構(gòu)描述算法可以有多種方式自然語(yǔ)言方式、表格方式、圖示形式等本書(shū)將采用C++與自然語(yǔ)言相結(jié)合的方式算法與數(shù)據(jù)結(jié)構(gòu)的關(guān)系不了解施加于數(shù)據(jù)上的算法就無(wú)法決定如何構(gòu)造數(shù)據(jù)，可以說(shuō)算法是數(shù)據(jù)結(jié)構(gòu)的靈魂；反之算法的結(jié)構(gòu)和選擇又常常在很大程度上依賴(lài)于數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)則是算法的基礎(chǔ)。算法＋數(shù)據(jù)結(jié)構(gòu)＝程序61.3 表達(dá)算法的抽象機(jī)制從機(jī)器語(yǔ)言到高級(jí)語(yǔ)言的抽象高級(jí)程序設(shè)計(jì)語(yǔ)言的主要好處是：高級(jí)語(yǔ)言更接近算法語(yǔ)言，易學(xué)、易掌握，一般工程技術(shù)人員只需要幾周時(shí)間的培訓(xùn)就可以勝任程序員的工作；高級(jí)語(yǔ)言為程序員提供了結(jié)構(gòu)化程序設(shè)計(jì)的環(huán)境和工具，使得設(shè)計(jì)出來(lái)的程序可讀性好，可維護(hù)性強(qiáng)，可靠性高；高級(jí)語(yǔ)言不依賴(lài)于機(jī)器語(yǔ)言，與具體的計(jì)算機(jī)硬件關(guān)系不大，因而所寫(xiě)出來(lái)的程序可植性好、重用率高；把繁雜瑣碎的事務(wù)交給編譯程序，所以自動(dòng)化程度高，開(kāi)發(fā)周期短，程序員可以集中時(shí)間和精力從事更重要的創(chuàng)造性勞動(dòng)，提高程序質(zhì)量。71.3 表達(dá)算法的抽象機(jī)制抽象數(shù)據(jù)類(lèi)型抽象數(shù)據(jù)類(lèi)型是算法的一個(gè)數(shù)據(jù)模型連同定義在該模型上并作為算法構(gòu)件的一組運(yùn)算。抽象數(shù)據(jù)類(lèi)型帶給算法設(shè)計(jì)的好處有：算法頂層設(shè)計(jì)與底層實(shí)現(xiàn)分離；算法設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)隔開(kāi)，允許數(shù)據(jù)結(jié)構(gòu)自由選擇；數(shù)據(jù)模型和該模型上的運(yùn)算統(tǒng)一在ADT中，便于空間和時(shí)間耗費(fèi)的折衷；用抽象數(shù)據(jù)類(lèi)型表述的算法具有很好的可維護(hù)性；算法自然呈現(xiàn)模塊化；為自頂向下逐步求精和模塊化提供有效途徑和工具；算法結(jié)構(gòu)清晰，層次分明，便于算法正確性的證明和復(fù)雜性的分析。81.4 描述算法與算法設(shè)計(jì)描述算法可以有多種方式，如自然語(yǔ)言方式、圖形表格方式等。在這里，我們將采用C++語(yǔ)言來(lái)描述算法。C++語(yǔ)言的優(yōu)點(diǎn)是類(lèi)型豐富、語(yǔ)句精煉，具有面向?qū)ο蠛兔嫦蜻^(guò)程的雙重優(yōu)點(diǎn)。用C++來(lái)描述算法可使整個(gè)算法結(jié)構(gòu)緊湊、可讀性強(qiáng)。在課程中，有時(shí)為了更好地闡明算法的思路，我們還采用C++與自然語(yǔ)言相結(jié)合的方式來(lái)描述算法。算法設(shè)計(jì)方法主要有：分治策略、動(dòng)態(tài)規(guī)劃、貪心算法、回溯法、分支限界、概率算法等，我們將在后面的章節(jié)中陸續(xù)介紹。91.4 描述算法與算法設(shè)計(jì)問(wèn)題求解(ProblemSolving)證明正確性分析算法設(shè)計(jì)程序理解問(wèn)題精確解或近似解選擇數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)策略設(shè)計(jì)算法101.5算法分析的基本原則正確性定義：在給定有效輸入后，算法經(jīng)過(guò)有限時(shí)間的計(jì)算并產(chǎn)生正確的答案，就稱(chēng)算法是正確的。正確性證明的內(nèi)容：方法的正確性證明——算法思路的正確性。證明一系列與算法的工作對(duì)象有關(guān)的引理、定理以及公式。程序的正確性證明——證明所給出的一系列指令確實(shí)做了所要求的工作。程序正確性證明的方法：大型程序的正確性證明——可以將它分解為小的相互獨(dú)立的互不相交的模塊，分別驗(yàn)證。小模塊程序可以使用以下方法驗(yàn)證：數(shù)學(xué)歸納法、軟件形式方法等。111.5算法分析的基本原則工作量——時(shí)間復(fù)雜性分析計(jì)量工作量的標(biāo)準(zhǔn):對(duì)于給定問(wèn)題，該算法所執(zhí)行的基本運(yùn)算的次數(shù)?；具\(yùn)算的選擇：根據(jù)問(wèn)題選擇適當(dāng)?shù)幕具\(yùn)算。問(wèn)題基本運(yùn)算在表中查找x比較實(shí)矩陣相乘實(shí)數(shù)乘法排序比較遍歷二叉樹(shù)置指針121.5算法分析的基本原則占用空間——空間復(fù)雜性分析兩種占用：存儲(chǔ)程序和輸入數(shù)據(jù)的空間存儲(chǔ)中間結(jié)果或操作單元所占用空間——額外空間影響空間的主要因素：存儲(chǔ)程序的空間一般是常數(shù)(和輸入規(guī)模無(wú)關(guān))輸入數(shù)據(jù)空間為輸入規(guī)模O(n)空間復(fù)雜性考慮的是額外空間的大小如果額外空間相對(duì)于輸入規(guī)模是常數(shù)，稱(chēng)為原地工作的算法。131.5算法分析的基本原則簡(jiǎn)單性含義：算法簡(jiǎn)單，程序結(jié)構(gòu)簡(jiǎn)單。好處：容易驗(yàn)證正確性便于程序調(diào)試簡(jiǎn)單的算法效率不一定高。要在保證一定效率的前提下力求得到簡(jiǎn)單的算法。3n+1問(wèn)題While(n>1)if(odd(n))n=3n+1;elsen=n/2;在最壞情況下，該算法的計(jì)算時(shí)間下界為Ω(logn).但其計(jì)算時(shí)間上界至今未知。即該算法是否在有限時(shí)間內(nèi)結(jié)束？日本學(xué)者米田信夫驗(yàn)證了1013內(nèi)的自然數(shù)。這就是Collatz猜想。141.5算法分析的基本原則最優(yōu)性含義：指求解某類(lèi)問(wèn)題中效率最高的算法兩種最優(yōu)性最壞情況：設(shè)A是解某個(gè)問(wèn)題的算法，如果在解這個(gè)問(wèn)題的算法類(lèi)中沒(méi)有其它算法在最壞情況下的時(shí)間復(fù)雜性比A在最壞情況下的時(shí)間復(fù)雜性低，則稱(chēng)A是解這個(gè)問(wèn)題在最壞情況下的最優(yōu)算法。平均情況：設(shè)A是解某個(gè)問(wèn)題的算法，如果在解這個(gè)問(wèn)題的算法類(lèi)中沒(méi)有其它算法在平均情況下的時(shí)間復(fù)雜性比A在平均情況下的時(shí)間復(fù)雜性低，則稱(chēng)A是解這個(gè)問(wèn)題在平均情況下的最優(yōu)算法。尋找最優(yōu)算法的途徑(以最壞情況下的最優(yōu)性為例)設(shè)計(jì)算法A，求W(n)。相當(dāng)于對(duì)問(wèn)題給出最壞情況下的一個(gè)上界。尋找函數(shù)F(n)，使得對(duì)任何算法都存在一個(gè)規(guī)模為n的輸入并且該算法在這個(gè)輸入下至少要做F(n)次基本運(yùn)算。相當(dāng)于對(duì)問(wèn)題給出最壞情況下所需基本運(yùn)算次數(shù)的一個(gè)下界。如果W(n)=F(n)，則A是最優(yōu)的。如果W(n)>F(n)，A不是最優(yōu)的或者F(n)的下界過(guò)低。改進(jìn)A或設(shè)計(jì)新算法A’使得W’(n)<W(n)。重新證明新下界F’(n)使得F’(n)>F(n)。重復(fù)以上兩步，最終得到W’(n)=F’(n)為止。151.5算法分析的基本原則例：在n個(gè)不同的數(shù)中找最大的數(shù)?；具\(yùn)算：比較算法：FindMax輸入：數(shù)組L，項(xiàng)數(shù)n11輸出：L中的最大項(xiàng)MAXMAX←L(1);i←2;whilei≤ndoifMAX<L(i)thenMAX←L(i);i←i+1;end。行3的比較進(jìn)行n－1次，故W(n)=n－1。定理：在n個(gè)數(shù)的數(shù)組中找最大的數(shù)，并以比較作為基本運(yùn)算的算法類(lèi)中的任何算法最壞情況下至少要做n－1次比較。證：因?yàn)镸AX是唯一的，其它的n－1個(gè)數(shù)必須在比較后被淘汰。一次比較至多淘汰一個(gè)數(shù)，所以至少需要n－1次比較。結(jié)論：FindMax算法是最優(yōu)算法。16課前練習(xí)1,算法分析的基本原則有哪些？2,試設(shè)計(jì)一算法，實(shí)現(xiàn)有31個(gè)網(wǎng)球運(yùn)動(dòng)員參加比賽的循環(huán)賽日程表。且簡(jiǎn)要分析你設(shè)計(jì)算法的時(shí)間和空間復(fù)雜性。171.6 算法復(fù)雜性分析算法復(fù)雜性是算法運(yùn)行所需要的計(jì)算機(jī)資源的量，需要時(shí)間資源的量稱(chēng)為時(shí)間復(fù)雜性，需要的空間資源的量稱(chēng)為空間復(fù)雜性。這個(gè)量應(yīng)該只依賴(lài)于算法要解的問(wèn)題的規(guī)模、算法的輸入和算法本身的函數(shù)。如果分別用N、I和A表示算法要解問(wèn)題的規(guī)模、算法的輸入和算法本身，而且用C表示復(fù)雜性，那么，應(yīng)該有C=F(N,I,A)。一般把時(shí)間復(fù)雜性和空間復(fù)雜性分開(kāi)，并分別用T和S來(lái)表示，則有：T=T(N,I)和S=S(N,I)。（通常，讓A隱含在復(fù)雜性函數(shù)名當(dāng)中）算法復(fù)雜性=算法所需要的計(jì)算機(jī)資源算法的時(shí)間復(fù)雜性T(n)；算法的空間復(fù)雜性S(n)。其中n是問(wèn)題的規(guī)模（輸入大小）。181.6 算法復(fù)雜性分析以上分別是最壞情況下、最好情況下和平均情況下的時(shí)間復(fù)雜性。其中DN是規(guī)模為N的合法輸入的集合；I*是DN中使T(N,I*)達(dá)到TMax(N)的合法輸入；I-是DN中使T(N,I-)達(dá)到TMin(N)的合法輸入；而P(I)是在算法的應(yīng)用中出現(xiàn)輸入I的概率。19算法的時(shí)間復(fù)雜性（1）最壞情況下的時(shí)間復(fù)雜性

Tmax(n)=max{T(I)|size(I)=n}（2）最好情況下的時(shí)間復(fù)雜性

Tmin(n)=min{T(I)|size(I)=n}（3）平均情況下的時(shí)間復(fù)雜性

Tavg(n)=

其中I是問(wèn)題的規(guī)模為n的實(shí)例，p(I)是實(shí)例I出現(xiàn)的概率。201.6 算法復(fù)雜性分析函數(shù)的漸進(jìn)性態(tài)與漸進(jìn)表達(dá)式：一般來(lái)說(shuō)，當(dāng)N單調(diào)增加且趨于∞時(shí)，T(N)也將單調(diào)增加趨于∞。對(duì)于T(N)，如果存在函數(shù)T'(N)，使得當(dāng)N→∞使有(T(N)-T'(N))/T(N)→0，那么我們就說(shuō)T'(N)是T(N)當(dāng)N→∞時(shí)的漸進(jìn)性態(tài)。在數(shù)學(xué)上，T'(N)是T(N)當(dāng)N→∞時(shí)的漸進(jìn)表達(dá)式。例如：3N2+4NlogN+7與3N2。21算法漸近復(fù)雜性T(n),asn;(T(n)-t(n))/T(n)0

，asn;t(n)是T(n)的漸近性態(tài)，為算法的漸近復(fù)雜性。在數(shù)學(xué)上，t(n)是T(n)的漸近表達(dá)式，是T(n)略去低階項(xiàng)留下的主項(xiàng)。它比T(n)簡(jiǎn)單。221.6 算法復(fù)雜性分析算法復(fù)雜性在漸近意義下的階：漸近意義下的記號(hào)：O、Ω、θ、o、ω設(shè)f(N)和g(N)是定義在正數(shù)集上的正函數(shù)。23漸近分析的記號(hào)在下面的討論中，對(duì)所有n，f(n)0，g(n)0。（1）漸近上界記號(hào)OO(g(n))={f(n)|存在正常數(shù)c和n0使得對(duì)所有nn0有：0f(n)

cg(n)}（2）漸近下界記號(hào)

(g(n))={f(n)|存在正常數(shù)c和n0使得對(duì)所有nn0有：0

cg(n)

f(n)}24O漸近例子F(N)=3NF(N)=NF(N)=2N2+11N-10F(N)=N2O(g(n))={f(n)|存在正常數(shù)c和n0使得對(duì)所有nn0有：0f(n)

cg(n)}25（3）非緊上界記號(hào)o

o(g(n))={f(n)|對(duì)于任何正常數(shù)c>0，存在正數(shù)和n0>0使得對(duì)所有nn0有：0f(n)<cg(n)}等價(jià)于

f(n)/g(n)0

，asn。（4）非緊下界記號(hào)

(g(n))={f(n)|對(duì)于任何正常數(shù)c>0，存在正數(shù)和n0>0使得對(duì)所有nn0有：0cg(n)

<f(n)}等價(jià)于

f(n)/g(n)

，asn。f(n)

(g(n))

g(n)

o(f(n))26（5）緊漸近界記號(hào)

(g(n))={f(n)|存在正常數(shù)c1,c2和n0使得對(duì)所有nn0有：c1g(n)f(n)

c2g(n)}

定理1：

(g(n))=O(g(n))

(g(n))27漸近分析記號(hào)在等式和不等式中的意義f(n)=(g(n))的確切意義是：f(n)

(g(n))。一般情況下，等式和不等式中的漸近記號(hào)(g(n))表示(g(n))中的某個(gè)函數(shù)。例如：2n2+3n+1=2n2+(n)表示

2n2+3n+1=2n2+f(n)，其中f(n)是(n)中某個(gè)函數(shù)。等式和不等式中漸近記號(hào)O,o,和的意義是類(lèi)似的。28漸近分析中函數(shù)比較f(n)=o(g(n))a<b;f(n)=O(g(n))ab;f(n)=(g(n))a=b;f(n)=(g(n))ab;f(n)=(g(n))a>b.29漸近分析記號(hào)的若干性質(zhì)（1）傳遞性：f(n)=(g(n))，g(n)=(h(n))

f(n)=(h(n))；f(n)=O(g(n))，g(n)=O

(h(n))

f(n)=O

(h(n))；f(n)=(g(n))，g(n)=(h(n))

f(n)=(h(n))；f(n)=o(g(n))，g(n)=o(h(n))

f(n)=o(h(n))；f(n)=(g(n))，g(n)=

(h(n))

f(n)=

(h(n))；30（2）反身性：f(n)=(f(n))；f(n)=O(f(n))；f(n)=(f(n)).（3）對(duì)稱(chēng)性：f(n)=(g(n))

g(n)=(f(n)).（4）互對(duì)稱(chēng)性：f(n)=O(g(n))

g(n)=(f(n))；f(n)=o(g(n))

g(n)=

(f(n))；31（5）算術(shù)運(yùn)算：O(f(n))+O(g(n))=

O(max{f(n),g(n)})；O(f(n))+O(g(n))=

O(f(n)+g(n))；O(f(n))*O(g(n))=

O(f(n)*g(n))；O(cf(n))=

O(f(n))；g(n)=O(f(n))O(f(n))+O(g(n))=

O(f(n))。32規(guī)則O(f(n))+O(g(n))=O(max{f(n),g(n)})的證明：對(duì)于任意f1(n)

O(f(n))，存在正常數(shù)c1和自然數(shù)n1，使得對(duì)所有nn1，有f1(n)

c1f(n)。類(lèi)似地，對(duì)于任意g1(n)

O(g(n))，存在正常數(shù)c2和自然數(shù)n2，使得對(duì)所有nn2，有g(shù)1(n)

c2g(n)。令c3=max{c1,c2}，n3=max{n1,n2}，h(n)=max{f(n),g(n)}。則對(duì)所有的nn3，有f1(n)+g1(n)

c1f(n)+c2g(n)

c3f(n)+c3g(n)=c3(f(n)+g(n))

c32max{f(n),g(n)}=2c3h(n)=O(max{f(n),g(n)}).33算法漸近復(fù)雜性分析中常用函數(shù)（1）單調(diào)函數(shù)單調(diào)遞增：m

n

f(m)f(n);單調(diào)遞減：m

n

f(m)f(n);嚴(yán)格單調(diào)遞增：m

<n

f(m)<f(n);嚴(yán)格單調(diào)遞減：m

<n

f(m)>f(n).（2）取整函數(shù)x：不大于x的最大整數(shù)；

x：不小于x的最小整數(shù)。34取整函數(shù)的若干性質(zhì)

x-1<xxx<x+1；

n/2

+n/2=n;

對(duì)于n

0，a,b>0，有：

n/a/b=n/ab;n/a/b=n/ab;a/b(a+(b-1))/b;a/b(a-(b-1))/b;

f(x)=x,g(x)=x為單調(diào)遞增函數(shù)。35（3）多項(xiàng)式函數(shù)

p(n)=a0+a1n+a2n2+…+adnd；ad>0;

p(n)=(nd);

f(n)=O(nk)f(n)多項(xiàng)式有界；

f(n)=O(1)

f(n)

c;

kdp(n)=O(nk);kdp(n)=(nk);k>

dp(n)=o(nk);k<dp(n)=(nk).36（4）指數(shù)函數(shù)對(duì)于正整數(shù)m,n和實(shí)數(shù)a>0:a0=1;

a1=a;

a-1=1/a;(am)n=amn;

(am)n=(an)m;

aman=

am+n;

a>1an為單調(diào)遞增函數(shù);a>1nb=o(an)37ex

1+x;|x|11+xex

1+x+x2;

ex

=1+x+(x2),asx0;38（5）對(duì)數(shù)函數(shù)

logn=log2n;

lgn=log10n;

lnn=logen;

logkn=(logn)kl;loglogn=log(logn);fora>0,b>0,c>03940|x|1forx>-1,foranya>0,,logbn=o(na)41（6）階層函數(shù)Stirling’sapproximation

4243算法分析中常見(jiàn)的復(fù)雜性函數(shù)44小規(guī)模數(shù)據(jù)45中等規(guī)模數(shù)據(jù)46用c++描述算法47（1）選擇語(yǔ)句：（1.1)if語(yǔ)句：（1.2)？語(yǔ)句：

if(expression)statement;elsestatement;

exp1?exp2:exp3y=x>9?100:200;等價(jià)于：

if(x>9)y=100;elsey=200;48（1.3)switch語(yǔ)句：switch(expression){case1:statementsequence;break;case2:statementsequence;break;

default:statementsequence;}49（2）迭代語(yǔ)句：（2.1)for循環(huán)：

for(init;condition;inc)statement;（2.2)while循環(huán)：

while(condition)statement;（2.3)do-while循環(huán)：

do{statement;}while(condition);50（3）跳轉(zhuǎn)語(yǔ)句：（3.1)return語(yǔ)句：

returnexpression;（3.2)goto語(yǔ)句：

gotolabel;

label:51（4）函數(shù)：例：

return-typefunctionname(para-list){bodyofthefunction}

intmax(intx,inty){returnx>y?x:y;}52（5）模板template

：template<classType>Typemax(Typex,Typey){returnx>y?x:y;}inti=max(1,2)；doublex=max(1.0,2.0)；53（6）動(dòng)態(tài)存儲(chǔ)分配：（6.1）運(yùn)算符new：運(yùn)算符new用于動(dòng)態(tài)存儲(chǔ)分配。new返回一個(gè)指向所分配空間的指針。例：intx；y=newint；y=10；也可將上述各語(yǔ)句作適當(dāng)合并如下：inty=newint；y=10；或inty=newint(10)；或inty；y=newint(10)；54（6.2）一維數(shù)組：為了在運(yùn)行時(shí)創(chuàng)建一個(gè)大小可動(dòng)態(tài)變化的一維浮點(diǎn)數(shù)組x，可先將x聲明為一個(gè)float類(lèi)型的指針。然后用new為數(shù)組動(dòng)態(tài)地分配存儲(chǔ)空間。例：floatx=newfloat[n]；創(chuàng)建一個(gè)大小為n的一維浮點(diǎn)數(shù)組。運(yùn)算符new分配n個(gè)浮點(diǎn)數(shù)所需的空間，并返回指向第一個(gè)浮點(diǎn)數(shù)的指針。然后可用x[0]，x[1]，…，x[n-1]來(lái)訪問(wèn)每個(gè)數(shù)組元素。55（6.3）運(yùn)算符delete：當(dāng)動(dòng)態(tài)分配的存儲(chǔ)空間已不再需要時(shí)應(yīng)及時(shí)釋放所占用的空間。用運(yùn)算符delete來(lái)釋放由new分配的空間。例：deletey；delete[]x；分別釋放分配給y的空間和分配給一維數(shù)組x的空間。56（6.4）動(dòng)態(tài)二維數(shù)組：創(chuàng)建類(lèi)型為T(mén)ype的動(dòng)態(tài)工作數(shù)組，這個(gè)數(shù)組有rows行和cols列。template<classType>voidMake2DArray(Type**&x,introws,intcols){x=newType*[rows];for(inti=0;i<rows;i++)x[i]=newType[cols];}57當(dāng)不再需要一個(gè)動(dòng)態(tài)分配的二維數(shù)組時(shí)，可按以下步驟釋放它所占用的空間。首先釋放在for循環(huán)中為每一行所分配的空間。然后釋放為行指針?lè)峙涞目臻g。釋放空間后將x置為0，以防繼續(xù)訪問(wèn)已被釋放的空間。template<classType>void

Delete2DArray(Type**&x,introws){for(inti=0;i<rows;i++)delete[]x[i];delete[]x;x=0;}58算法分析方法例：順序搜索算法template<classType>intseqSearch(Type*a,intn,Typek){for(inti=0;i<n;i++) if(a[i]==k)returni;return-1;}Q:試分析該算法的時(shí)間復(fù)雜性。59（1）Tmax(n)=max{T(I)|size(I)=n}=O(n)（2）Tmin(n)=min{T(I)|size(I)=n}=O(1)（3）在平均情況下，假設(shè)：

(a)搜索成功的概率為p(0

p

1)；

(b)在數(shù)組的每個(gè)位置i(0i<n)搜索成功的概率相同，均為p/n。60算法分析的基本法則非遞歸算法：（1）for/while循環(huán)循環(huán)體內(nèi)計(jì)算時(shí)間*循環(huán)次數(shù)；（2）嵌套循環(huán)循環(huán)體內(nèi)計(jì)算時(shí)間*所有循環(huán)次數(shù)；（3）順序語(yǔ)句各語(yǔ)句計(jì)算時(shí)間相加；（4）if-else語(yǔ)句if語(yǔ)句計(jì)算時(shí)間和else語(yǔ)句計(jì)算時(shí)間的較大者。61template<classType>voidinsertion_sort(Type*a,intn){Typekey;//