(
课件网) 结 据 数 构 5.1 数据结构与算法的关系 与 算 法 问题提出 1+2+3+……+100=？ 1+2+3+……+n=？(n>0) n=int(input("你输入问题规模n:")) s=(1+n)*n/2 print ("1+2+……+n的结果是：",str(s)) n=int(input("你输入问题规模n:")) s=0 for i in range(1,n+1): s=s+i print ("1+2+……+n的结果是：",str(s)) VS 运行结果一致，算法思想等有什么差别？ 顺序结构 循环结构 算法1语句执行次数共：3次 算法2语句执行次数共：2*n+3次 1次 1次 1次 1次 1次 n次 n次 1次 一、算法效率 n=int(input("你输入问题规模n:")) s=(1+n)*n/2 print ("1+2+……+n的结果是：",str(s)) 算法1: t(n)=3 n=int(input("你输入问题规模n:")) s=0 for i in range(1,n+1): s=s+i print ("1+2+……+n的结果是：",str(s)) 算法2: t(n)=2*n+3 导入时间模块，记录运行时间，比较算法对应程序的执行次数与执行时间的关系 import time n=int(input("你输入问题规模n:")) starttime = time.time() s=(1+n)*n/2 print ("1+2+……+n的结果是：",str(s)) endtime = time.time() dtime = endtime - starttime print(“算法1运行时间：%.8s s" % dtime) 算法1和算法2运行次数和时间比较表 算法1t(n)=3运行时间稳定 算法2 t(n)=2*n+3运行时间与n成正比 n=int(input("你输入问题规模n:")) s=0;c=0 for i in range(1,2*n+2,2): s=s+i c=c+1 print ("1+3+……+2*n+1的结果是：",str(s)) 算法3: t(n)=3*n+4 1次 2次 n次 n次 n次 1次 算法3 t(n)=3*n+4运行时间与n成正比 二、算法效率的表示 时间是衡量效率的重要方面，算法执行所需要的时间用时间复杂度来反应 执行算法相应程序的时间与语句执行次数成正比（忽略其他硬软件设施） 算法执行所占用的存储空间也需要考虑，用空间复杂度来反应，硬件进步考虑较少 算法效率 时间复杂度 空间复杂度 算法的时间复杂度由程序基础语句的执行次数可推得 三、时间复杂度的大o阶记法 算法1t(n)=3运行时间稳定 算法2 t(n)=2*n+3运行时间与n成正比 算法3 t(n)=3*n+4运行时间与n成正比 O(1) O(n) O(n) 算法4 t(n)=n2+5运行时间与n成正比 O(n2) 算法5 t(n)=3*n2+5运行时间与n成正比 O(n2) 常数阶 线性阶 线性阶 平方阶 平方阶 三、时间复杂度的大o阶记法 O(n2) n=int(input("你输入问题规模n:")) s=0;c=0 for i in range(1,n+1): for j in range(1,n+1): s=s+i print ("结果是：",str(s)) 算法6: t(n)=2*n*n+n+4 n=int(input("你输入问题规模n:")) s=0;c=0 for i in range(1,n+1): for j in range(1,i+1): s=s+i print ("结果是：",str(s)) 算法7: t(n)=n*n+2*n+4 O(n2) 程序执行次数转换为算法时间复杂度规则： 1.只保留最高阶；2.与高阶相乘的常数去除；3.只有常数则用1取代 1次 2次 n次 n*n次 n*n次 1次 1次 2次 n次 1+2+……n次 1+2+……n次 1次 O(1) n=int(input("你输入问题规模n:")) s=0;c=0 if s>c: print ("结果是：",str(s)) else: print ("结果是：",str(c)) 算法8: t(n)=5 n=int(input("你输入问题规模n:")) s=0;c=0 for i in range(1,n+1): if s>c: print ("结果是：",str(s)) else: print ("结果是：",str(c)) print ("结果是：",str(s)) 算法9: t(n)=3*n+4 O(n) 程序执行次数转换为算法时间复杂度规则： 1.只保留最高阶；2.与高阶相乘的常数去除；3.只有常数则用1取代 三、时间复杂度的大o阶记法 O(log2n) n=int(input("你输入问题规模n:")) s=0;i=1 while i<=n: s=s+1 i=i*2 print ("结果是：",str(s)) 算法10: 关注循环体执行次数即可 i=1 i=2 i=4 i=8 i=16 i=n …… 循环体执行次数： log2n 对数阶 O(1) O(n) O(n2) O(log2n) 三、时间复杂度的大o阶记法 O( ... ...
