数据结构-算法评价分解

练习解释数据元素数据记录数据结构说明如何判断给定数据是否具有线性关系的数据说明常用的数据存储形式2023/6/151算法复杂度分析数据结构-算法评价分解全文共70页，当前为第1页。第一章绪论1.1数据结构讨论的范畴1.2数据结构的基本概念与术语1.3算法与算法的分析2023/6/152算法复杂度分析数据结构-算法评价分解全文共70页，当前为第2页。算法+数据结构=程序

(NiklausWirth)Algorithm+DataStructure=Programs算法：解决问题的策略、方法数据结构：问题所涉及的数学模型程序：解决问题的操作步骤，计算机指令的序列如何设计出适合于问题的高效率的数据结构，从而得到高效率的算法与程序第一章绪论

1.1

数据结构讨论的范畴2023/6/153算法复杂度分析数据结构-算法评价分解全文共70页，当前为第3页。数据：计算机能够处理的信息的载体数据元素：最小的独立数据单位数据记录：具有独立逻辑意义的数据单位数据结构：包括三部分内容：数据的逻辑结构、存储结构、算法第一章绪论

1.2数据结构的术语与概念2023/6/154算法复杂度分析数据结构-算法评价分解全文共70页，当前为第4页。数据逻辑结构：线性结构非线性结构树图集合第一章绪论

1.2数据结构的术语与概念2023/6/155算法复杂度分析数据结构-算法评价分解全文共70页，当前为第5页。数据存储结构：顺序存储：一般利用系统数据组织结构--数组链接存储：一般利用系统数据组织结构--链表索引存储：利用数据空间以外的索引表辅助存储散列存储：利用散列函数辅助存储第一章绪论

1.2数据结构的术语与概念2023/6/156算法复杂度分析数据结构-算法评价分解全文共70页，当前为第6页。算法描述：流程图N-S图自然语言伪代码……选择数据集中的最小值……for(i=0;i<n;i++)

选出最小值利用最小值开始递归计算fun(min);第一章绪论

1.2数据结构的术语与概念2023/6/157算法复杂度分析数据结构-算法评价分解全文共70页，当前为第7页。第一章绪论1.3

算法分析1.3.1进行算法分析的目的1.3.2算法分析概述1.3.3空间复杂度分析1.3.4时间复杂度分析2023/6/158算法复杂度分析数据结构-算法评价分解全文共70页，当前为第8页。1.3.1算法分析的目的算法分析：是对一种算法所消耗资源的估计资源：包括硬件设备的需求如内存、磁盘空间等时间的需求如至少需要进行多少基本运算掌握算法分析的目的：将对同一问题不同算法的代价进行比较、对需要实现的算法进行资源限

制与资源需求的估计第一章绪论1.3

算法分析2023/6/159算法复杂度分析数据结构-算法评价分解全文共70页，当前为第9页。对算法分析的认识算法分析的关注问题：

增长率（growthrate)：当问题规模增长时算法代价增长的趋势

增长率的上限与下限：对于算法消耗资源代价的上下限估计

能够从代价的角度对一般的程序进行分析比较第一章绪论1.3

算法分析2023/6/1510算法复杂度分析数据结构-算法评价分解全文共70页，当前为第10页。1.3.2算法分析概述

一般考虑四个方面：

1、算法的正确性

2、算法的简单性

3、算法运行时间消耗

4、算法运行空间消耗第一章绪论1.3

算法分析2023/6/1511算法复杂度分析数据结构-算法评价分解全文共70页，当前为第11页。1.3.2.1算法的正确性分析：在合理的数据输入条件下，在有限的时间内能够得出正确的结果（证明、软件测试、问题要求、容忍的程度）

第一章绪论1.3

算法分析2023/6/1512算法复杂度分析数据结构-算法评价分解全文共70页，当前为第12页。1.3.2.2算法的简单性：在可选择范围内的首要选择以支持算法可修改、可维护、可靠性第一章绪论1.3

算法分析2023/6/1513算法复杂度分析数据结构-算法评价分解全文共70页，当前为第13页。1.3.2.3

算法时间分析

算法的时间分析涉及两个问题：

1、是否可以用程序的运行时间来评价、度量算法的时间效率？

2、如何度量算法的时间代价是合理的，是在不同算法间可以比较的？第一章绪论1.3

算法评价2023/6/1514算法复杂度分析数据结构-算法评价分解全文共70页，当前为第14页。程序运行时间涉及的问题：

1、CUP、RAM、硬盘、语言、OS、的速度的差异影响程序的速度。

2、算法执行简单操作的次数，可以用来估计算法的操作时间。第一章绪论1.3

算法评价2023/6/1515算法复杂度分析数据结构-算法评价分解全文共70页，当前为第15页。算法时间评价的结论：

1、不能依据程序的执行时间评价算法的时间代价。

2、依据算法中基本操作的次数用估计算法的时间代价，使得算法之间具有可比性。

3、寻找和确定能够评价和比较算法效率的方法，即建立算法间的可比性。（具体方法下一小节详细介绍）第一章绪论1.3

算法评价2023/6/1516算法复杂度分析数据结构-算法评价分解全文共70页，当前为第16页。1.3.2.4算法空间消耗：空间复杂度分析

1、程序占用空间

2、数据占用空间

3、算法处理过程中的临时空间第一章绪论1.3

算法评价2023/6/1517算法复杂度分析数据结构-算法评价分解全文共70页，当前为第17页。算法空间消耗分析：空间复杂度分析

1、程序占用空间：在不同程序之间差异不大

2、数据占用空间：由问题的规模决定

3、算法处理过程中的临时空间：受到问题规模与算法设计的共同影响第一章绪论1.3

算法评价2023/6/1518算法复杂度分析数据结构-算法评价分解全文共70页，当前为第18页。算法空间占用：临时空间占用的分析临时空间受到问题规模与算法设计的共同影响，分析实例：

1、数据倒序

2、递归程序第一章绪论1.3

算法评价2023/6/1519算法复杂度分析数据结构-算法评价分解全文共70页，当前为第19页。临时空间占用：数据倒序

25891215headtail15589122headtail15128952headtail15129852第一章绪论1.3

算法评价2023/6/1520算法复杂度分析数据结构-算法评价分解全文共70页，当前为第20页。临时空间占用：数据倒序

25891215head15129852headtailheadheadheadheadtailtailtailtailtail第一章绪论1.3

算法评价2023/6/1521算法复杂度分析数据结构-算法评价分解全文共70页，当前为第21页。空间对算法效率的影响方法2:增加存储空间数据量（问题规模）m交换次数为m方法1:在原存储空间数据量（问题规模）m交换次数为3/2*m2023/6/1522算法复杂度分析数据结构-算法评价分解全文共70页，当前为第22页。阶乘递归程序临时空间占用fun(x)intx;{if(x<=1)return1;elsereturn(x*fun(x-1));}第一章绪论1.3

算法评价1n<=1n!={n*(n-1)!n>12023/6/1523算法复杂度分析数据结构-算法评价分解全文共70页，当前为第23页。fun(4)4*fun(3)3*fun(2)2*fun(1)4*3*2*1=24fun(x)intx;{if(x<=1)return1;elsereturn(x*fun(x-1));}保留现场保留现场保留现场恢复现场恢复现场恢复现场第一章绪论1.3

算法评价2023/6/1524算法复杂度分析数据结构-算法评价分解全文共70页，当前为第24页。fun(4)4*fun(3)3*fun(2)2*fun(1)4*3*2*1=241.保留现场4*fun(3)2.保留现场3*fun(2)3.保留现场2*fun(1)4.恢复fun(2)现场

2*15.恢复fun(3)现场

3*26.恢复fun(4)现场

4*61.5.3算法评价（空间复杂度分析）2023/6/1525算法复杂度分析fun(x)intx;{if(x<=1)return1;elsereturn(x*fun(x-1));}数据结构-算法评价分解全文共70页，当前为第25页。4*3*2*1=241.保留现场4*fun(3)2.保留现场3*fun(2)3.保留现场2*fun(1)4.恢复fun(2)现场

2*15.恢复fun(3)现场3*26.恢复fun(4)现场4*61.5.3算法评价（空间复杂度分析）2023/6/1526算法复杂度分析fun(x)intx;{if(x<=1)return1;elsereturn(x*fun(x-1));}在没有发生函数运行终止条件之前,系统一直处于数据保留状态,不断地累加保留数据,直到遇到终止条件为止.数据结构-算法评价分解全文共70页，当前为第26页。空间复杂度存储要求算法控制方式算法计算过程中的临时空间2023/6/1527算法复杂度分析数据结构-算法评价分解全文共70页，当前为第27页。1.3.3时间复杂度分析第一章绪论1.3

算法评价1、不能依据程序的执行时间评价算法的时间代价。

2、依据算法中简单操作的次数用估计算法的时间代价，使得算法之间具有可比性。2023/6/1528算法复杂度分析数据结构-算法评价分解全文共70页，当前为第28页。1.3.3时间复杂度分析（基本概念）第一章绪论1.3

算法评价

抽象计算机基本操作（元操作）基本操作的时间时间复杂度2023/6/1529算法复杂度分析数据结构-算法评价分解全文共70页，当前为第29页。1.3.3时间复杂度分析（基本概念）第一章绪论1.3

算法评价

我们可以利用抽象计算机来分析和认识算法的时间复杂性分析图灵机（TuringMachine）:一种不受存储限制，进行元操作的，理想计算机，在计算机科学与理论研究中具有非常重要的意义（图灵与图灵奖）。2023/6/1530算法复杂度分析数据结构-算法评价分解全文共70页，当前为第30页。1.3.3时间复杂度分析（基本概念）第一章绪论1.3

算法评价

元操作逻辑计算机提供的基本操作。设提供元操作k种：

O1,O2,……Ok2023/6/1531算法复杂度分析数据结构-算法评价分解全文共70页，当前为第31页。1.3.3时间复杂度分析（基本概念）第一章绪论1.3

算法评价

元操作时间

K种元操作各自占用时间为：

t1,t2,……tk2023/6/1532算法复杂度分析数据结构-算法评价分解全文共70页，当前为第32页。1.3.3时间复杂度分析（基本概念）第一章绪论1.3

算法评价

算法A中元操作Oi的操作次数

ei(N)N---问题的规模2023/6/1533算法复杂度分析数据结构-算法评价分解全文共70页，当前为第33页。1.3.3时间复杂度分析（基本概念）第一章绪论1.3

算法评价算法时间复杂度：算法所对应的元操作所消耗的时间

算法元操作所进行的次数（时间复杂度）问题的规模：求解问题算法时所输入的数据量2023/6/1534算法复杂度分析数据结构-算法评价分解全文共70页，当前为第34页。1.3.3时间复杂度分析（基本概念）第一章绪论1.3

算法评价

算法A的时间消耗

T(N)=t1e1(N)+t2e2(N)+……+tkek(N)

算法A的时间复杂度

T(N)=e1(N)+e2(N)+……+ek(N)2023/6/1535算法复杂度分析数据结构-算法评价分解全文共70页，当前为第35页。1.3.3时间复杂度分析（基本概念）第一章绪论1.3

算法评价通过分析：完成算法所需要的时间，与实现算法的

基本操作的次数、算法的规模有关。算法的时间复杂度是问题规模的函数：记为：

T(n)T:表示算法的时间复杂度n：问题规模

2023/6/1536算法复杂度分析数据结构-算法评价分解全文共70页，当前为第36页。1.3.3时间复杂度分析（实例分析1-累加）第一章绪论1.3

算法评价floatsum(m,n)floatm[];intn;{inti;floats;for(s=0.0,i=0;i<n;i++)s+=m[i];return(s);}简单操作次数：2+6*nT(n)=2+6n

赋值2

加法、赋值、循环处理比较、加法、赋值、跳转ns=0;i=0i<nS+=m[i]i++2023/6/1537算法复杂度分析数据结构-算法评价分解全文共70页，当前为第37页。1.3.3时间复杂度分析（实例分析2-矩阵）第一章绪论1.3

算法评价mul(a,b,c,n)inta[10][10],b[10][10],c[10][10],n;{inti,j;for(i=0;i<n;i++)for(j=0;j<n;j++)c[i][j]=a[i][j]+b[i][j];}

外：赋值1，加法/判断：n

内：赋值1、加法/判断：n

内循环与循环体操作

n*n简单操作次数：1+3n+4*n2T(n)=1+3n+4n22023/6/1538算法复杂度分析数据结构-算法评价分解全文共70页，当前为第38页。1.3.3时间复杂度分析（讨论）第一章绪论1.3

算法评价

精确性，具体到1，2次基本运算的意义？我们关心的不是算法在具体的问题状况下“操作的次数”我们所关心的是当问题规模增大或减小时，算法的时间复杂度变化的趋势简单操作次数：T(n)=1+3n+4n22023/6/1539算法复杂度分析数据结构-算法评价分解全文共70页，当前为第39页。1.3.3时间复杂度分析（讨论）第一章绪论1.3

算法评价

我们所关心的是当问题规模增大或减小时，

算法时间复杂度变化的趋势希望找到一种能够反映时间复杂度的变化趋势，描述形式简单，变化趋势明确的表达方式。2023/6/1540算法复杂度分析数据结构-算法评价分解全文共70页，当前为第40页。1.3.3时间复杂度分析（变化趋势的讨论）第一章绪论1.3

算法评价为此我们定义时间复杂度数量级设算法时间复杂度：T(n)若存在一个简单的函数f(n)，在n>n0时，存在常数a<b，满足：

T(n)a<-----------<bf(n)（n0为一个足够大的整数，即问题的规模足够大时）2023/6/1541算法复杂度分析数据结构-算法评价分解全文共70页，当前为第41页。1.3.3时间复杂度分析（时间复杂度数量级）第一章绪论1.3

算法评价f(n)称为算法的时间复杂度数量级，记为：O(n)设算法时间复杂度：T(n)若存在一个简单的函数f(n)，在n>n0时，存在常数a<b，满足：

T(n)a<-----------<bf(n)2023/6/1542算法复杂度分析数据结构-算法评价分解全文共70页，当前为第42页。1.3.3时间复杂度分析（时间复杂度数量级）第一章绪论1.3

算法评价一般情况下，在数学上，f(n)是T(n)的渐近表达式在直观上，f(n)是T(n)省略低阶数据项后的高阶数据项

2023/6/1543算法复杂度分析数据结构-算法评价分解全文共70页，当前为第43页。1.3.3时间复杂度分析（变化趋势的讨论）第一章绪论1.3

算法评价实例：设算法时间复杂度为：T(n)=5n+2

存在简单函数:f(n)=n5n+2-----------=5+2/n当n=5时

n

存在a=5b=6使得：a<5+2/n<b

2023/6/1544算法复杂度分析数据结构-算法评价分解全文共70页，当前为第44页。1.3.3时间复杂度分析（变化趋势的讨论）第一章绪论1.3

算法评价则算法时间复杂度为：T(n)=5n+2

算法时间复杂度数量级为：f(n)=n

2023/6/1545算法复杂度分析数据结构-算法评价分解全文共70页，当前为第45页。1.3.3时间复杂度分析（变化趋势的讨论）实例：for(i=0;i<n;i++){y=y+1;for(k=0;k<2*n;k++)x++;}第一章绪论1.3

算法评价2023/6/1546算法复杂度分析数据结构-算法评价分解全文共70页，当前为第46页。实例：for(i=0;i<n;i++){y=y+1;①for(k=0;k<=2*n;k++)k++;②}①运行的频度n②运行的频度2n+1第一章绪论1.3

算法评价2023/6/1547算法复杂度分析数据结构-算法评价分解全文共70页，当前为第47页。①运行的频度n②运行的频度2n+1

核心操作运行的总频度：n(2n+1)=2n2+n

即T(n)=2n2+n

设f(n)=n2第一章绪论1.3

算法评价2023/6/1548算法复杂度分析数据结构-算法评价分解全文共70页，当前为第48页。

运行的总频度：n(2n+1)=2n2+n

即T(n)=2n2+n

设f(n)=n2

当n>2时T(n)2n2+n---------=-------------=2+1/nf(n)n2

a=2;b=3T(n)2<---------=2+1/n<3f(n)第一章绪论1.3

算法评价2023/6/1549算法复杂度分析数据结构-算法评价分解全文共70页，当前为第49页。

所以,当

T(n)=2n2+n时，

T(n)的时间复杂度数量级为：

O(n)=n2第一章绪论1.3

算法评价2023/6/1550算法复杂度分析数据结构-算法评价分解全文共70页，当前为第50页。1.3.3时间复杂度分析（时间复杂度数量级）第一章绪论1.3

算法评价常见的算法的时间复杂度数量级：O(log2n)O(n)O(nlog2n),O(n2)O(2n)O(n!)2023/6/1551算法复杂度分析数据结构-算法评价分解全文共70页，当前为第51页。Log2(n)2023/6/1552算法复杂度分析数据结构-算法评价分解全文共70页，当前为第52页。nlog(n)2023/6/1553算法复杂度分析数据结构-算法评价分解全文共70页，当前为第53页。Log(n)<nlog(n)<n22023/6/1554算法复杂度分析数据结构-算法评价分解全文共70页，当前为第54页。比较2023/6/1555算法复杂度分析数据结构-算法评价分解全文共70页，当前为第55页。1.3.3时间复杂度分析（时间复杂度数量级结论）第一章绪论1.3

算法评价O(log2n)<O(n)<O(nlog2n)<O(n2)<O(2n)<O(n!)时间复杂度数量级给我们提供了一个简单工具，可以清楚地对同一问题的不同算法，考察在问题规模变化的情况下，时间代价变化的情况。当我们将算法的核心部分设计基本完成之后，不必完成编程，我们就可以估计、比较算法的时间代价，2023/6/1556算法复杂度分析数据结构-算法评价分解全文共70页，当前为第56页。典型时间复杂度的程序形式：第一章绪论1.3

算法评价实例1：

i=1;①while(i<=n){i++;②

……;}①频度1②频度nf(n)=n2023/6/1557算法复杂度分析数据结构-算法评价分解全文共70页，当前为第57页。1.3.3时间复杂度分析（时间复杂度数量级结论）第一章绪论1.3

算法评价实例2：

i=1;①while(i<=n)i*=2;②①频度1②频度f(n)？2023/6/1558算法复杂度分析数据结构-算法评价分解全文共70页，当前为第58页。1.3.3时间复杂度分析（时间复杂度数量级结论）第一章绪论1.3

算法评价实例2：i=1;①while(i<=n)i*=2;②②频度f(n)的分析循环的功能为n=2*2*2*……*2

频度f(n)为表达式幂次，即n=2f(n)2023/6/1559算法复杂度分析数据结构-算法评价分解全文共70页，当前为第59页。1.3.3时间复杂度分析（时间复杂度数量级结论）第一章绪论1.3

算法评价②频度f(n)的分析循环的功能为i=2*2*2*……*2

频度f(n)为表达式幂次，即i=2f(n)

循环的结果为：i=2f(n)=n

表达式两边log：log22f(n)=log2nf(n)*log22=log2n2023/6/1560算法复杂度分析数据结构-算法评价分解全文共70页，当前为第60页。1.3.3时间复杂度分析（时间复杂度数量级结论）第一章绪论1.3

算法评价

f(n)*log22=log2nf(n)=log2nO(log2n)2023/6/1561算法复杂度分析数据结构-算法评价分解全文共70页，当前为第61页。1.3.3时间复杂度分析（时间复杂度数量级结论）第一章绪论1.3

算法评价实例3：i=1;while(i<=n)①{j=1;while(j<=n){j*=2;…….}

②i++;}①复杂度为：n②复杂度为：log2nO(n*log2n)2023/6/1562算法复杂度分析数据结构-算法评价分解全文共70页，当前为第62页。1.3.3时间复杂度分析（时间复杂度数量级结论）第一章绪论1.3

算法评价实例4：i=1；while(i<=n){j=1;while(j<=i)

{applicationcode;