5.1数据结构与算法效率 学案 - 浙教版2019 高中 信息技术 选修1 学案
5.1数据结构与算法效率 导学案
| 高中信息技术 | 教材版本 | 浙教版2019选修1 |
课题 | 5.1数据结构与算法效率 | ||
一、【学习目标】
1.理解数据结构与算法的关系。(重点)(学科核心素养:信息意识、计算思维)
2.认识算法效率高低的主要的两个方面:时间复杂度与空间复杂度,及这两个方面的表示与计算。(难点)(学科核心素养:信息意识、计算思维)
3.逐步自觉将算法的效率应用在算法程序设计中,根据问题选择合适的数据结构,提高算法效率。(学科核心素养:信息意识)
二、【自主探究】
任务一:学生自主学习课本,完成下列题目:
1.算法效率的高低可由 来度量。算法复杂度又分为算法的 和 ,其中时间复杂度反映了 所需要的时间,而空间复杂度反映了算法执行所需要占用的 。
2.算法的 反映了程序执行时间随问题规模增长而增长的量级,在很大程度上能很好地反映出算法的优劣。
任务二:
def ct(n):
s=0
while n>0:
s+=n%2
n//=2
return s
n=int(input("输入一个正整数:")
ans=ct(n)
print(ans)
请回答下列问题:
(1)程序运行后,输入整数23,自定义函数ct(n)中语句“s+=n%2”执行的次数是 。
原创精品资源学科网独家享有版权,侵权必究!
学科网(北京)股份有限公司
(2)该算法的时间复杂度为 (单选,填字母:A.O(n)/B.O(log₂n))。
任务三:小华规划自驾游路线,出发地为杭州,目的地为北京,途径地为上海、苏州、南京、济南、石家庄。用数组来实现其更改过程。
| 1 | 2 | 3 | 4 | 5 | 6 |
杭州 | 上海 | 苏州 | 南京 | 济南 | 石家庄 | 北京 |
(1)小华想要查询第5个到达的城市,如何编程实现 时间复杂度为 。
(2)小华计划有变决定直接从上海出发,不从杭州出发,如何编程实现?时间复杂度为 。
a=["杭州","上海","苏州","南京","济南","石家庄","北京"]
n=ien(a)
q=0
for i in range(q,n-1):
pop()
print(a)
任务四:比较数组和链表两种不同的数据结构对算法的影响并填写表格。
原创精品资源学科网独家享有版权,侵权必究!
学科网(北京)股份有限公司