资源简介

(共17张PPT)
数据结构与算法效率
数据结构指的是数据之间的相互关系，即数据组织形式。包括：逻辑结构、存储结构、基本操作（数据运算）。
数据结构概念及类型
常见类型：数组、链表、队列、栈、树和图等。
同一个问题若采用不同的数据结构，算法效率也将不同。
算法效率是指算法执行的时间，算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。
活动一：求和问题的效率探讨
求1+2+3+……+n的和
算法一：高斯求和
n=int(input())
s=(1+n)*n/2
print(s)
例
算法二：累加求和
n=int(input())
s=0
for i in range(1,n+1): s=s+i
print(s)
这两种算法的执行效率一样吗？
算法效率的度量方式
方法一：可依据该算法编制的程序在计算机上运行时所消耗的时间来度量；
方法二：算法效率的高低也可由算法复杂度来度量。
利用计算机的计时功能，对不同算法编制的程序的运行时间进行比较。
方法一：计算算法执行所需时间度量算法效率。
算法一:高斯求和
import time
start = time.time()
n=int(input())
s=(1+n)*n/2
print(s)
end = time.time()
print(end - start)
算法二:累加求和
import time
start = time.time()
n=int(input())
s=0
for i in range(1,n+1): s=s+i
print(s)
end = time.time()
print(end - start)
任务要求
执行算法一和算法二的程序，输入不同的n,并将运行时间记录在任务单上，比较分析两种算法的算法效率。
结 论
当输入的问题规模n大到一定程度，高斯求和的运行时间低于累加求和算法，
高斯求和的算法效率高。
算法复杂度分为时间复杂度和空间复杂度。
方法二：预估算法复杂度度量算法效率
时间复杂度: 指该算法中基本操作重复执行的次数与问题规模n的某个函数。
空间复杂度:指该算法在运行过程中临时占用存储空间大小的度量。
算法时间复杂度的表示
算法一:高斯求和
n=int(input())
s=(1+n)*n/2
print(s)
算法二:累加求和
n=int(input())
s=0
for i in range(1,n+1): s=s+i
print(s)
#执行1次
#执行1次
#执行1次
执行次数T(n)=3
执行次数T(n)=2n+3
#执行1次
#执行1次
#执行n次
#执行n次
#执行1次
时间复杂度常用符号O表示，记作: O(T(n))
它表示随着问题规模n的增大，算法执行时间的增长率和T(n)的增长率相同
算法时间复杂度的表示
算法一：高斯求和
T(n)=3
O(3)
O(1)
常量阶
算法二：累加求和
T(n)=2n+3
O(2n+3)
O(2n+1)
线性阶
O(n)
O(2n)
结论
时间效率:O(1)试一试：推导算法时间复杂度
n=int(input())
s=0
x=0
for i in range(1,n+1):
for j in range(1,n+1):
x=x+1
s=s+x
print(s)
#执行1次
#执行1次
#执行1次
#执行n次
#执行n*n次
#执行n*n次
#执行n*n次
#执行1次
算法时间复杂度：
O(3n2+n+4)
O(3n2+n+1)
O(3n2)
O(n2)
平方阶
常见的算法时间复杂度
阶 术语
O(1) 常量阶
O(n) 线性阶
O(n2) 平方阶
O(log2n) 对数阶
O(n3) 立方阶
O(2n) 指数阶
算法的时间复杂度反映了程序执行时间随问题规模增长而增长的量级。
活动二：数据结构对算法效率的影响
数据结构 逻辑结构 存储结构 基本操作
数组 确定 连续 增、删、改、查
链表 确定 不连续 增、删、改、查
数据结构 查看第n个元素的时间复杂度 插入、删除元素时间复杂度
数组
链表
head
移动
O(1)
O(n)
O(n)
O(1)
试一试：计算斐波那契数列的第n项
数学家斐波那契在他的《算盘书》里排了一个数列:1,1,2,3,5……这个数列可以和黄金分割联系起来。这个数列越排到后面,前一个数与后一个数的比值就越接近0.618(34/55约等于0.618),就是黄金分割的近似值。请编写了一个程序来计算并输出斐波那契数列的第n项。
试一试：计算斐波那契数列的第n项
a=[0]*20000001
n=int(input("请输人一个正整数:"))
a[1]=1
a[2]=1
for i in range(3,n+1):
a[i]=a[i-1]+a[i-2]
print(a[n])
算法一
算法二
n=int( input("请输入一个正整数:"))
a=b=1
for i in range(3,n+1):
c=a+b #当前项的值等于前两项的和
a=b
b=c
print(c)
算法一和算法二时间复杂度相同，均为O(n)
算法一的空间复杂度>算法二的空间复杂度
1.你知道空间复杂度是如何度量的吗？
2.有人认为现代计算机的运行速度足够快了，已经没有必要研究算法的效率了，你有什么体会？
拓展思考
1 算法效率度量的一般方法
时间复杂度和空间复杂度
2 数据结构与算法效率的关系
数组、链表不同操作的时间复杂度
3 算法效率评估
合理评估算法效率的重要性
课堂小结
评分项 自我评价 同学互评
能完成新课导入中的问题并建立算法时间复杂度的概念 5 4 3 2 1 5 4 3 2 1
能够对简单程序分析其算法时间复杂度 5 4 3 2 1 5 4 3 2 1
能够对线性结构的算法时间复杂度进行简要分析 5 4 3 2 1 5 4 3 2 1
能合理评估算法效率的重要性 5 4 3 2 1 5 4 3 2 1
对自己和同伴的表现进行客观的评价，并思考后续完善的方向。（5=优秀，4=超出一般水平，3=满意，2=有待改进，1=不太理想）
谢谢观看！

展开更多......

收起↑