大二复习-数据结构第一章绪论

什么是算法之魂？既然算法是解决问题的办法或法则，而解决一个问题又不一定只有一种办法。这样，不同办法之间便有了好坏之分。如何进行比较呢？能够进行比较的东西很多：模块性、正确性可维护性、功能性、友好性、简易性、可扩展性、可靠性等等。效率（速度）——算法之魂内容：算法的性能标准算法的后期测试算法的事前估计算法性能分析与度量目的：算法的可用性算法的性能比较让我们从比较两个用于查找（m个元素）的具体算法的效率开始：顺序查找和折半查找。最坏的情况下的效率：顺序查找：要检测所有m个元素；折半查找：最多检测k+1(k=log2m)个元素。m1K1M1G顺序查找10241024210243折半查找112131[例1-12]百鸡问题如果用a表示公鸡的数量，b表示母鸡的数量，c表示小鸡的数量，则有：公鸡每只5元，母鸡每只3元，小鸡3只1元，用100元钱买100只鸡，求公鸡、母鸡和小鸡的数量。inta,b,c,k=0;for(a=0;a<n;a++){for(b=0;b<n;b++){for(c=0;c<n;c++){if((a+b+c==n)&&(5*a+3*b+c/3==n)&&(c%3=0)){记录a,b,c；k++}}}}算法一算法二inta,b,c,k=0;i=n/5;j=n/3;for(a=0;a<i;a++){\\公鸡数量不超过n/5for(b=0;b<j;b++){\\母鸡数量不超过n/3c=n-a-b;if((5*a+3*b+c/3)==n)&&(c%3)=0){记录a,b,c；k++}}}当n=100时，算法一的内循环次数为100万次，而算法二的内循环次数为21*34=714，仅为算法一的万分之七，有重大改进。如果假定内部循环一次花费1μs的时间，则:n算法一算法二结论1001s714μs相差不大1000011天13小时6.7s相差巨大[例1-13]货郎担问题穷举法思路：如果对任意数目的n个城市分别用从1到n进行编号，则此问题归结为在有向带权图中寻找一条路径最短的哈密尔顿回路问题。这里，城市间的距离可以用邻接矩阵表示。售货员的每一条线路，对应于城市编号的一个排列。某售货员要到若干个城市销售货物，已知各城市之间的距离。要求售货员选择出发的城市及旅行路线，使每一个城市仅经过一次，最后回到出发城市，而总路程最短。intp[n],i=1;Floatcost;Min=MAX_FLOAT_NUM;while(i<n!){

产生n个城市的一个排列p；

cost=路线p的长度；

if(cost<min){

保留p的内容；min=cost;

}

i++;}算法需循环n!次，假设每循环一次，需花费1μs的时间，则算法的执行时间随n增长而增长的情况如下表nn！nn！nn！5120μs131.72h1711.27year75.04ms1424h18203year9362ms1515day193857year1139.9s16242day2077146year关于算法的效率，有两个问题要弄清楚：用怎样的一个量来表达一个算法的效率；对于给定的一个算法，怎样具体评估它的效率。算法效率的估量–算法的复杂性算法的复杂性是通过算法的资源耗费和算法所要解决的问题的规模之间的函数关系来度量的。算法的复杂性是算法效率的度量，是评价算法优劣的关键依据。一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面，所需的资源越多，我们就说该算法的复杂性越高（效率越低）；反之，复杂性就越低（效率越高）。计算机的资源，最重要的是时间（即CPU）和空间（即存储器）资源。因而，算法的复杂性有时间复杂性和空间复杂性之分。不言而喻，对于任意给定的问题，设计出复杂性尽可能低的算法是我们在设计算法时追求的一个重要目标。算法的复杂性影响算法执行时间的最直接因素是所解问题的大小；我们将算法求解问题的输入量称为问题的规模，用一个整数来表示；一个给定的输入称为问题的实例。一般地说，一个算法的时间耗费和空间耗费是问题规模的函数；在衡量算法的复杂性时，需要对问题实例的大小进行量化。对于不同的问题，量化的方法不一样。排序问题:待排序数据元素的个数;搜索问题:要搜索的表中的元素的个数;线性方程组问题:未知数的个数;矩阵乘法问题:两个矩阵的行数、列数;图问题:图的顶点数和边数;等等。空间复杂度时间复杂度因为影响执行资源耗费最大的因素通常是问题的规模（即算法的输入规模），因此，对于一个给定的输入规模n，我们一般把算法的资源耗费表示为n的函数。

算法复杂性度量存储空间的固定部分

程序指令代码的空间，常数、简单变量、定长成分(如数组元素、结构成分、对象的数据成员等)变量所占的空间可变部分

大小与实例特性有关的变量所占空间、引用变量所占空间、递归栈所用的空间、通过new和delete命令动态使用的空间空间复杂度所考虑的空间

一般是指算法工作所需要的额外的辅助存储空间空间复杂度度量时间复杂度的估计1、后期测试通过在计算机上实际测试来确定算法完成某一特定功能所需的时间。2、事前估计通过对算法的分析近似地得到算法的性能。算法的后期测试基本思想：找出算法的执行时间和问题规模的关系。在算法中的某些部位插装时间函数time()，测定算法完成某一功能所花费的时间。[例1-14]顺序查找算法执行时间与实例特性有关，因此考虑最坏情况。intseqsearch(inta[],constintn,constintx){inti=0;while(i<n&&a[i])!=x)i++;if(i==n)

return-1;elsereturni;}0102030…90100200…9001000数组n测试的思路：设定问题从小到大若干不同的规模（存放在数组中），在每一特定的规模下，执行算法并记录所花费的时间。VoidTimeSearch(){inta[1001],n[20];for(intj=1;j<=1000;j++)a[j]=j;//数组a存放1，…，1000for(j=0;j<10;j++){n[j]=10*j;n[j+10]=100*(j+1);//确定每次查找的问题规模}cout<<“ntime“<<endl;for(j=0;j<20;j++){longstart,stop;time(&start);intk=seqsearsh(a,n[j],0);//在n[j]个元素中查找time(&stop);longrunTime=stop–start;cout<<“n[j]<<“”<<runTime<<endl;}}由于time()函数的返回值的精度是有限的，所以在程序执行时间较短时，无法得到正确结果。查找前后time()函数返回的值可能是一样的，使得相减的结果为0。解决的办法：采用重复n次执行的方式得到执行的时间，再除n得到一次执行的时间。例如：当问题的规模为较小时，反复做n次查找，记录查找前后时间之差m，再用n除m，可得平均一次查找的时间。voidTimeSearch(){inta[1001],n[20];

constlongr[20]={300000,300000,200000,200000,100000,100000,100000,80000,80000,50000,50000,25000,15000,15000,10000,7500,7000,6000,5000,5000};//查找的重复次数

for(intj=1;j<=1000;j++)a[j]=j;//数组a赋值

for(j=0;j<10;j++){

n[j]=10*j;n[j+10]=100*(j+1);

}cout<<“ntotalTimerunTime”<<endl;

for(j=0;j<20;j++){

longstart,stop;time(start); //开始计时

for(longb=1;b<=r[j];b++)

intk=seqsearch(a,n[j],0);//执行r[j]次

time(stop); //停止计时

longtotalTime=stop-start;

floatrunTime=(float)(totalTime)/(float)(r[j]);//计算一次执行的时间

cout<<""<<n[j]<<""<<totalTime<<""<<runTime<<endl;

}}程序测试结果输出分析可知，该算法的执行时间与问题的规模基本呈线性关系。通过作图法可得到相应的直线方程。由此方程可推知最坏情况下该算法在任意问题规模下的执行时间。注意：用曲线构造函数关系式，在多数情况下是比较困难的。后期测试的不足1、必须执行程序。2、其它因素掩盖算法本质。3、找出问题规模和执行时间之间的函数关系比较困难。事前估计近似估计

——仅考虑算法中影响效率的主要因素精确估计

——统计算法所执行的总的步数（若假定所有程序语句的执行时间相同，均为单位时间，则总的执行步数与总的时间相同）近似估计的例子Intlargest(intarray[],intn){inti,currlarge=0;for(i=1;i<n;i++)if(array[currlarge]<array[i])currlarge=i;returncurrlarge;}这里，问题规模的大小为n。算法的基本操作是比较整数的值。我们假定每次比较花费了同样的时间c。我们仅仅需要算法执行时间的近似估计，所以，在最坏情况下，其执行时间近似为cn，即T(n)=cn。[例1－15]求一维数组中具有最大值的元素将一个整型数组赋给一个变量的赋值语句的执行时间一般为该数组首元素地址的复制时间。无论该数组多大，我们假定此时间为c1。这样，花费的时间可以简单地表示为：T(n)=c1这被称为常数时间，即输入规模n的大小对执行时间没有影响。[例1－16]Sum=0;for(i=1;i<n;i++)for(j=1;j<n;j++)sum++;这个例子中的基本操作是变量sum的增量操作。我们可以假定增量操作花费常数时间c2，这样，我们可以估计该程序段的执行时间为T(n)=c2n2。当算法的执行时间为cn时我们称其计算时间复杂度为线性阶的，当算法的执行时间中含有n2因子，则被称为二次阶的。如果n出现在指数部分，则被称为具有指数阶的时间复杂度度。[例1－17]精确估计影响程序执行效率的因素程序设计语言编译的代码质量机器执行指令的速度问题的规模程序运行的环境程序运行时与其他用户的资源竞争……统一：通过提取程序中的元操作（语句执行单位时间），评价问题规模与时间之间的关系一个算法所用的时间是它的编译时间加上运行时间。这里，我们只考虑算法的运行时间。任何一个算法都是由一些“控制结构”和若干“原操作”组成的，因此一个算法的执行时间可以看成是所有原操作的执行时间之和∑(原操作的执行次数×原操作的执行时间)。这样，算法的执行时间与所有原操作的执行次数之和成正比。从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为衡量算法时间复杂度的依据。这种衡量效率的办法所得出的不是时间量，它与软硬件环境无关，只暴露算法本身执行效率的优劣。对于用程序形式描述的算法，我们用程序步作为算法的元操作。一个程序步是指在语法或语义上有意义的一段指令序列，这段指令的执行时间与实例特性无关。1.注释语句:02.声明语句:03.表达式：如果表达式中不包含函数调用为1，否则要加上函数调用的程序步数。4.赋值语句：与表达式类似。5.循环语句：循环次数+16.if-else语句:if<expr><statement1>else<statement2>

分别将<expr>、<statement1>、<statement2>分配给每一部分。7.switch语句:switch(<expr>){casecond1:<statement1>casecond2:<statement2>…}首部switch(<expr>)的程序步数等于<expr>的程序步数，执行一个条件的程序步数等于它自己的程序步数加上它前面所有条件的程序步数。8.函数执行语句:

本身的步数为1，但值传递的参数的计算步数需要另外考虑。8.存储管理语句:

本身的步数为1，但如调用了对象的构造函数或析构函数，额外的程序步数另外考虑。10.函数调用语句:0，其时间开销记入函数执行语句。11.转移语句:一般为1。但return<expr>需另外考虑<expr>的程序步数。

程序步确定方法插入全局计数变量count

建表，列出各个语句的程序步行

floatsum(floata[],constintn)

1

{

2

floats=0.0;

3

for(inti=0;i<n;i++)

4s+=a[i];

5

returns;

6

}

统计程序步的方法：插入全局计数变量count[例1-18]以迭代方式求累加和的函数

floatsum(floata[],constintn) {floats=0.0;count++; //count统计执行语句条数

for(inti=0;i<n;i++){count++; //针对for语句

s+=a[i]; count++;//针对赋值语句

}

count++; //针对for的最后一次

count++; //针对return语句

returns;}执行结束得程序步数计数结果：count=2×n+3。

voidsum(floata[],constintn){for(inti=0;i<n;i++)count+=2;count+=3;}

程序的简化形式floatsum(float*a,constintn){ floats=0; count++;//countisglobal for(inti=0;i<n;i++){ count++;//forfor s+=a[i]; count++;//forassignment } count++;//forlasttimeoffor count++;//forreturn returns;}Program:Program1.13withcountstatementsadded在求累加和程序中加入count语句注意：

一个语句本身的程序步数可能不等于该语句一次执行所具有的程序步数。例如：赋值语句

x=sum(R,n);本身的程序步数为1，一次执行对函数sum(R,n)的调用需要的程序步数为2*n+3，赋值语句x=sum(R,n)总的执行的程序步数为

1+2*n+3=2*n+4linefloatrsum(float*a,constintn)1{2 if(n<=0)return0;3 elsereturn(rsum(a,n–1)+a[n-1]);4}Program:Recursivefunctionforsumfloatrsum(float*a,constintn){count++;//forifconditionalif(n<=0){count++;//forreturnreturn0;}else{count++;//forreturnreturn(rsum(a,n–1)+a[n-1]);}}Program:Withcountstatementsadded[例1-19]以递归方式求累加和的函数linevoidadd(matrixa,matrixb,matrixc,intm,intn)1{2 for(inti=0;i<m;i++)3 for(intj=0;j<n;j++)4 c[i][j]=a[i][j]+b[i][j];5}Program:Matrixaddition

voidadd(matrixa,matrixb,matrixc,intm,intn){ for(inti=0;i<m;i++){ count++;//forfori,mtimes for(intj=0;j<n;j++){ count++;//forforj,mntimes c[i][j]=a[i][j]+b[i][j]; count++;//forassignment,mntimes } count++;//forlasttimeofforj,mtimes } count++;//forlasttimeoffori,onetime}Program:Matrixadditionwithcountingstatements

[例1-20]矩阵相加linevoidadd(matrixa,matrixb,matrixc,intm,intn)1{2 for(inti=0;i<m;i++)3 {4 for(intj=0;j<n;j++)5 count+=2;//2mn6 count+=2;//2m7 }8 count++;9}Program:Simplifiedprogramwithcountingonlylinevoidadd(matrixa,matrixb,matrixc,intm,intn)1{2 for(inti=0;i<m;i++)3 for(intj=0;j<n;j++)4 c[i][j]=a[i][j]+b[i][j];5}Program:Matrixaddition当问题的规模n趋于无穷大时，把时间复杂度函数f(n)的数量级（阶）称为算法的渐进时间复杂度（有时简称为时间复杂度）。注意：一个算法的“运行工作量”通常是随问题规模的增长而增长，因此，实际比较不同算法的优劣主要应该以其“增长的快慢”为准则，算法性能评价的结果也是一个反映变化趋势的函数(在给定规模下比较算法的优劣没有意义)。时间复杂度的渐进表示法若f(n)和g(n)是定义在正整数集合上的两个函数，当存在两个正的常数整数C和n0时，使得对所有的成立，则都有这时称g(n)为f(n)的渐进上界(asymptoticupperbound)，或称算法的渐进时间复杂度为：O记法注意：我们希望得到的是“尽可能紧凑”的上界若f(n)和g(n)是定义在正整数集合上的两个函数，当存在两个正的整数C和n0时，使得对所有的成立，则都有这时称g(n)为f(n)的渐进下界。Ω记法注意：如何理解渐进下界的意义？都有对于一个给定的函数g(n),我们记Θ(g(n))为函数的集合：Θ(g(n))={f(n):如果存在正的常数c1,c2和n0，使得当n≥n0时，有0≤c1g(n)≤f(n)≤c2g(n)}Θ记法这可以解释为：如果存在正的常数c1,c2，使得对于充分大的n，函数f(n)被“夹在”c1g(n)和c2g(n)之间，则函数f(n)属于集合Θ(g(n))。因为Θ(g(n))是一个集合，所以，可以记为：f(n)∈Θ(g(n))以表示f(n)是Θ(g(n))的成员。实际上，我们通常将此写为：f(n)=Θ(g(n))以表示同样的含义。注意：Θ、O、Ω三种记法之间具有如下关系：若f(n)和g(n)是定义在正整数集合上的两个函数，当有f(n)=O(g(n))和f(n)=Ω(g(n))成立,则Θ表示法比O表示法的限制性更强。因此，按照集合论的观点，有：1.对于3n+1

取C=4，这时假设当n≥n0时，有：3n+1≤4n，

求解n，得n≥1，取n0＝1，即当n≥1时，3n+1≤4n

所以，3n+1=O(n)，这里n0＝1，C＝4。[例1－21]nn0f(n)=3n+14g(n)=4n完全类似地有：2.对于3n+3当n≥3时，3n+3≤4n所以，3n+3=O(n)，这里n0＝3，C＝4。3.对于100n+6当n≥10时，100n+6≤101n所以，100n+6=O(n)，这里n0＝10，C＝101。4.对于10n2+4n+2当n≥5时，10n2+4n+2≤11n2所以，10n2+4n+2=O(n2)，这里n0＝5，C＝11。5.对于1000n2+100n-6当n≥100时，1000n2+100n-6≤1001n2

所以1000n2+100n-6=O(n2)，这里n0＝100，C＝101。6.对于6×2n+n2当n≥4时，6×2n+n2≤7×2n

所以，6×2n+n2=O(2n)，这里n0＝4，C＝7。思路：解决问题要抓主要矛盾，解决主要矛盾着眼于矛盾的主要方面。常数阶对数阶线性阶线性对数阶平方阶立方阶………K次方阶指数阶常见的时间复杂度，按数量级递增排序：10n20n5nlogn2n22n时间问题规模nloglognlognnnlognn2n32n16242425282122162563828211216224225610243.3102102132202302102464K416216220232248264K1M4.32022022424026021M1G4.93023023526029021G在给定的计算能力下问题的规模与不同算法的执行时间之间的关系设f(n)关于算法A的时间复杂性函数。一般说来，当n单调增加且趋于∞时，f(n)也将单调增加趋于∞。对于f(n)，如果存在g(n)，使得当n→∞时有：算法的渐进时间复杂度的解释那么，我们就说g(n)是f(n)当n→∞时的渐近性态，或叫g(n)为算法A当n→∞的渐近时间复杂度而与f(n)相区别，因为在数学上，g(n)是f(n)当n→∞时的渐近表达式。直观上，g(n)是f(n)中略去低阶项所留下的主项。所以它无疑比f(n)来得简单。简化规则：1.如果f(n)＝O(g(n))且g(n)＝O(h(n))，那么：f(n)＝O(h(n))2.如果f(n)＝O(kg(n))，这里，k>0为一常数，那么：

f(n)＝O(g(n))3.如果f1(n)＝O(g1(n))且f2(n)＝O(g2(n))，那么：f1(n)+f2(n)＝O(max(g1(n),g2(n)))4.如果f1(n)＝O(g1(n))且f2(n)＝O(g2(n)),那么：f1(n)f2(n)＝O(g1(n)×g2(n))linefloatsum(float*a,constintn)1{2 floats=0;3 for(inti=0;i<n;i++)4 s+=a[i];5 returns;6}Program:IterativefunctionforsumLines/efrequencytotal10-O(0)211O(1)31n+1O(n)41nO(n)511O(1)60-O(0)[例1－22]linefloatrsum(float*a,constintn)1{2if(n<=0)return0;3elsereturn(rsum(a,n–1)+a[n-1]);4}Program:RecursivefunctionforsumLines/efrequencytotaln=0n>0n=0n>010--0O(0)2(a)1111O(1)2(b)1101O(0)31+trmin(n-1)010O(1+trsum(n-1))40--0O(0)

trsum(n)=2O(1+trsum(n-1))[例1－23]linevoidadd(matrixa,matrixb,matrixc,intm,intn)1{2 for(inti=0;i<m;i++)3 for(intj=0;j<n;j++)4 c[i][j]=a[i][j]+b[i][j];5}Program:MatrixadditionLines/efrequencytotal10-O(0)21m+1O(m)31m(n+1)O(mn)41mnO(mn)50-O(0)tadd(m,n)=O(mn)[例1－24]魔方是一个从1到n2个整数的n×n矩阵，一个从1到n2个整数的n×n魔方中的每一行、每一列及对角线上的整数的和都是相同的。下面是一个n=5的魔方(和是75):15812417161475232220136432119121092251811[例1－25]1、在最上一行的中间位置填入1，然后不断寻找下一个位置，顺次填入2，3，…。2、寻找下一个位置的方向是左上；即如当前位置是i、j，则下一个位置就是i-1，j-1。2、把平面看成是环状的封闭体（即第一行的上方是最后一行，第一列的左方是最右一列）；3、当前位置是i、j，如下一个预填入的位置不空，则以i+1、j作为下一个预填入的位置。492357816当n为奇数时，H.Coxeter给出了一个生成魔方的简单规则：15872417161415232220136432119121011182529voidmagic(intn)//createamagicsquareofsizen,nisodd{constintMaxSize=51;//maximumsquaresizeintsquare[MaxSize][MaxSize],k,l;

//checkcorrectnessofnif((n>(MaxSize))||(n<1)){cerr<<“Error!…noutofrange”<<range”<<endl;return;}elseif(!(n%2)){cerr<<“Error!…niseven”<<range”<<endl;return;}//nisodd.Coxeter’srulecanbeusedfor(inti=0;i<n;i++)//initializesquareto0for(intj=0;j<n;j++)square[i][j]=0;square[0][(n-1)/2]=1;//middleoffirstrow

//iandjarecurrentpositionintkey=2;i=0;intj=(n-1)/2;n2

while(key<=n*n){//moveupandleftif(i–1<0)k=n–1;elsek=i–1;if(j–1<0)l=n–1;elsel=j–1;if(square[k][l])i=(i+1)%n;//squareoccupied,movedownelse{//square[k][l]isunoccupiedi=k;j=l;}square[i][j]=key;key++;}//endofwhile

//outputthemagicsquarecout<<“magicsquareofsize”<<n<<endl;for(i=0;i<n;i++){for(j=0;j<n;j++)cout<<square[i][j]<<““;cout<<endl;}}//Program：MagicsquareNomorethann2-1n2intBinarySearch(int*a,constintx,constintn)//Searchthesortedarraya[0],…,a[n-1]forx{for(intleft=0,right=n–1;left<=right;){//whilemoreelementsintmiddle=(left+right)/2;switch(compare(x,a[middle])){ case‘>’:left=middle+1;break;//x>a[middle] case‘<’:right=middle–1;break;//x<a[middle] case‘=’:foundx;//x==a[middle] }//endofswitch}//endofforreturn–1;//notfound}//endofBinarySearchProgram:C++functionforbinarysearch考虑二分查找函数的时间复杂度。[例1－26]实例规模是数组a中元素的个数n。循环部分每次迭代花费的时间为O(1)。假定循环一共执行k次迭代，在第i次迭代中需搜索的元素为n/2i-1。所以，每次迭代搜索的元素个数的序列为：这样，循环迭代的次数一共是：log2n+1，时间复杂度为O(log2n)。voidperm(char*a,constintk,constintn)//n是元素个数//生成a[k],…,a[n-1]的所有排列{if(k==n–1){//输出一个排列for(inti=0;i<n;i++)cout<<a[i]<<““;cout<<endl;}else{//递归处理for(i=k;i<n;i++){//交换a[k]和a[i]chartemp=a[k];a[k]=a[i];a[i]=temp;perm(a,k+1,n);//生成a[k+1],…,a[n-1]的所有排列//再次交换a[k]和a[i],恢复原样temp=a[k];a[k]=a[i];a[i]=temp;}}}Program:Recursivepermutationgenerator[例1－27]从else后面的for循环可以看出，计算n个符号的全排列需要做n次对n-1个符号的递归求解，所以该算法执行时间的递归方程为：使用替换规则，我们得到：通常只考虑三种情况下的复杂性，即最坏情况、最好情况和平均情况下的时间复杂性，并分别记为Tmax(N)、Tmin(N)和Tavg(N)。三种情况下的时间复杂性各从某一个角度来反映算法的效率，各有各的用处，也各有各的局限性。但实践表明可操作性最好的且最有实际价值的是最坏情况下的时间复杂性。

计算平均时间复杂度，也就是计算大小为n的所有问题实例的工作量的平均值。设Bn是大小为n的问题实例的集合，I是一个实例，且大小为n，即I∈Bn，P(I)是I出现的概率，t(I)是算法对实例I运行时所需要的基本运算的执行次数，则平均工作量为：但P(I)不是很容易确定的，因此平均工作量不易计算。为简化问题起见，作等概率假设，这样：

x=48x=50[例1－28]线性表顺序查找的时间复杂度分析搜索不成功，数据比较n次。时间复杂度均为O(n)搜索成功时的平均比较次数：其中，ci为查找的是第i个元素时的比较次数，ci=

i+1。若搜索概率相等，即：p0=p1=...=pn-1=1/n，则：1、决定用哪个（或那些）参数作为输入规模的度量。2、找出算法的基本操作（作为一个规律，它总是位于算法的最内层循环中）。3、检查算法的执行次数是否只依赖于输入规模。如果它还依赖于其他的一些特性，则最坏、平均、最好（如有必要）情况下的算法效率需要分别研究。4、建立一个算