5.1数据结构与算法的关系ppt课件-2023新浙教版《高中信息技术》选择性必修第一册.pptx

1、1+2+3+100=？1+2+3+n=？(n0)n=int(input(n=int(input(你输入问题规模你输入问题规模n:)n:)s=(1+n)s=(1+n)*n/2n/2print(1+2+nprint(1+2+n的结果是：的结果是：,str(s),str(s)n=int(input(n=int(input(你输入问题规模你输入问题规模n:)n:)s=0s=0for i in range(1,n+1for i in range(1,n+1):):s=s+i s=s+iprint(1+2+nprint(1+2+n的结果是：的结果是：,str(s),str(s)运行结果一致，算法运行结果一

2、致，算法思想思想等等有什么差别有什么差别？顺序结构循环结构算法1语句执行次数共：3次算法2语句执行次数共：2*n+3次1次1次1次1次1次n次n次1次n=int(input(n=int(input(你输入问题规模你输入问题规模n:)n:)s=(1+n)s=(1+n)*n/2n/2print(1+2+nprint(1+2+n的结果是：的结果是：,str(s),str(s)算法1:t(n)=3n=int(input(n=int(input(你输入问题规模你输入问题规模n:)n:)s=0s=0for i in range(1,n+1for i in range(1,n+1):):s=s+i s=s+

3、iprint(1+2+nprint(1+2+n的结果是：的结果是：,str(s),str(s)算法2:t(n)=2*n+3导入时间模块，记录运导入时间模块，记录运行时间，比较算法对应行时间，比较算法对应程序的执行次数与执行程序的执行次数与执行时间的关系时间的关系import import timetimen=int(input(n=int(input(你输入问题规模你输入问题规模n n:):)starttime=time.timestarttime=time.time()()s=(1+n)s=(1+n)*n/2n/2print(1+2+nprint(1+2+n的结果是：的结果是：,str(s,

4、str(s)endtime endtime=time.time()=time.time()dtime=endtime-starttimedtime=endtime-starttimeprintprint(“(“算法算法1 1运行时间：运行时间：%.8s s%dtime)%.8s s%dtime)算法算法1 1t(n)=t(n)=3 3运行时间稳定运行时间稳定算法算法2 2 t(n)=2t(n)=2*n+3n+3运行时间与运行时间与n n成正比成正比n=int(input(n=int(input(你输入问题规模你输入问题规模n:)n:)s=0;c=0s=0;c=0for i in for i i

5、n range(1,2range(1,2*n+2,2)n+2,2):s=s+i s=s+i c=c+1c=c+1print(print(1+3+21+3+2*n+1n+1的的结果是：结果是：,str(s),str(s)算法3:t(n)=3*n+41次2次n次n次n次1次算法算法3 3 t(nt(n)=3)=3*n+4n+4运行时间与运行时间与n n成正比成正比时间是衡量效率的重要方面，算法执行所需要的时间用时间复杂度来反应执行算法相应程序的时间与语句执行次数成正比（忽略其他硬软件设施）算法执行所占用的存储空间也需要考虑，用空间复杂度来反应，硬件进步考虑较少算法效率算法效率时间复杂度时间复杂度空

6、间复杂度空间复杂度算法的时间复杂度由程序基础语句的执行次数可推得算法算法1 1t(n)=t(n)=3 3运行时间稳定运行时间稳定算法算法2 2 t(n)=2t(n)=2*n+3n+3运行时间与运行时间与n n成正比成正比算法算法3 3 t(nt(n)=3)=3*n+4n+4运行时间与运行时间与n n成正比成正比O(1)(1)O(n)(n)O(n)(n)算法算法4 4 t(nt(n)=n)=n2 2+5+5运行时间与运行时间与n n成正比成正比O(n(n2 2)算法算法5 5 t(nt(n)=3)=3*n n2 2+5+5运行时间与运行时间与n n成正比成正比O(n(n2 2)常数阶常数阶线性阶

7、线性阶线性阶线性阶平方阶平方阶平方阶平方阶O(n(n2 2)n=int(input(n=int(input(你输入问题规模你输入问题规模n:)n:)s=0;c=0s=0;c=0for i in range(1,n+1):for i in range(1,n+1):for j in range(1,n+1):for j in range(1,n+1):s=s+i s=s+iprint print(结果结果是：是：,str(s),str(s)算法6:t(n)=2*n*n+n+4n=int(input(n=int(input(你输入问题规模你输入问题规模n:)n:)s=0;c=0s=0;c=0for

8、 i in range(1,n+1):for i in range(1,n+1):for j in range(1,i+1):for j in range(1,i+1):s=s+i s=s+iprint print(结果结果是：是：,str(s),str(s)算法7:t(n)=n*n+2*n+4O(n(n2 2)程序执行次数转换为算法时间复杂度规则：1.只保留最高阶；2.与高阶相乘的常数去除；3.只有常数则用1取代1次2次n次n*n次n*n次1次1次2次n次1+2+n次1+2+n次1次O(1)(1)n=int(input(n=int(input(你输入问题规模你输入问题规模n:)n:)s=0;

9、c=0s=0;c=0if sc:if sc:print(print(结果结果是：是：,str(s,str(s)else:else:print print(结果是：结果是：,str(c)str(c)算法8:t(n)=5n=int(input(n=int(input(你输入问题规模你输入问题规模n:)n:)s=0;c=0s=0;c=0for i in range(1,n+1):for i in range(1,n+1):if if sc:sc:print print(结果是：结果是：,str(s),str(s)else else:print print(结果是：结果是：,str(c,str(c)p

10、rint(print(结果结果是：是：,str(s),str(s)算法9:t(n)=3*n+4O(n)(n)程序执行次数转换为算法时间复杂度规则：1.只保留最高阶；2.与高阶相乘的常数去除；3.只有常数则用1取代O(logO(log2 2n n)n=int(input(n=int(input(你输入问题规模你输入问题规模n:)n:)s=0;i=1s=0;i=1while i=n:while i=n:s=s+1 s=s+1 i=i i=i*2 2print print(结果结果是：是：,str(s),str(s)算法10:关注循环体执行次数即可i=1i=1i=2i=2i=4i=4i=8i=8i=

11、16i=16i=ni=n循环体执行次数：循环体执行次数：loglog2 2n n对数阶对数阶O(1)(1)O(n)(n)O(n(n2 2)O(log(log2 2n n)O(n(n3 3)O(2(2n n)O(n(n!)常见算法时间复杂度耗时比较常见算法时间复杂度耗时比较算法的时间复杂度在很大程度上能很好的反映出算法的时间复杂度在很大程度上能很好的反映出算法的优劣。算法的优劣。设计算法时，尽量减少循环的嵌套，减少基础语设计算法时，尽量减少循环的嵌套，减少基础语句运行次数。句运行次数。算法效率算法效率时间复杂度时间复杂度空间复杂度空间复杂度大大O阶记法阶记法有具体程序有具体程序则看语句执则看语句

12、执行次数行次数关注算法的关注算法的循环次数循环次数数据结构的设计和选择关注：数据的逻辑结构、存储结构以及基本操作数据结构的设计和选择关注：数据的逻辑结构、存储结构以及基本操作算法的设计和选择更多关注：如何在数据结构的基础上综合运用各种基本数据操作来解决实际问题算法的设计和选择更多关注：如何在数据结构的基础上综合运用各种基本数据操作来解决实际问题算法和数据结构设计皆为最终解决问题服务算法和数据结构设计皆为最终解决问题服务算法是编程思想，数据结构则是这些思想的基础算法是编程思想，数据结构则是这些思想的基础数据结构数据结构逻辑结构逻辑结构存储结构存储结构基本操作基本操作数组数组确定确定连续连续增、删

13、、改、查增、删、改、查链表链表明确的明确的不连续不连续增、删、改、查增、删、改、查查看第查看第n n个元素个元素的时间复杂度的时间复杂度插入、删除元素插入、删除元素时间复杂度时间复杂度数组数组链表链表d0d1d2d3d4d5“赵”“钱”“孙”“李”“周”“吴”d3“郑”新数据插入位置data3 nulldata1 nextnewnextdata2 nextO(1)O(n)O(n)O(1)import import timetimen=int(input(n=int(input(你输入问题规模你输入问题规模n n:):)starttime=time.timestarttime=time.time

14、()()s=(1+n)s=(1+n)*n/2n/2print(1+2+nprint(1+2+n的结果是：的结果是：,str(s,str(s)endtime endtime=time.time()=time.time()dtime=endtime-starttimedtime=endtime-starttimeprint(print(程序运行时间程序运行时间：%.8s s%dtime)%.8s s%dtime)import import timetimen=int(input(n=int(input(你输入问题规模你输入问题规模n n:):)starttime=time.timestarttime=time.time()()s=0s=0for i in range(1,n+1):for i in range(1,n+1):s=s+i s=s+iprint print(1+2+n(1+2+n的结果是：的结果是：,str(s,str(s)endtime endtime=time.time()=time.time()dtime=endtime-starttimedtime=endtime-starttimeprint(print(程序运行时间程序运行时间：%.8s s%dtime)%.8s s%dtime)上机运行，体会程序的运行时间上机运行，体会程序的运行时间