2021-2022学年浙教版（2019）高中信息技术必修一《第2章 算法与问题解决》知识点梳理

1、第二章第二章 算法与问题解决算法与问题解决 1. 算法可以帮助算法执行者高效地解决问题。 2. 算法指的是解决问题或完成任务的一系列步骤。 3. 根据算法的定义，算法具有下列特征：有穷性、可行性、确定性、0 个或多个输入、一个或多个输出。 4. 算法三要素 数据、运算及控制转移 5. 常见的算法描述方式有自然语言、流程图、伪代码、计算机程序设计语言等。 6. 流程图用一些图形符号表示规定的操作， 并用带箭头的流程线连接这些图形符号， 表示操作进行方向。 流程图描述算法结构清晰、 寓意明确。 常用的流程图基本图形及其功能 如图 2.1 所示。 图 2.1 7. 计算机程序设计语言经历了“机器语言

2、一汇编语言一高级语言”的发展历程。 8. 常见的高级语言有 Basic、 C、C+、Java、Python、Ruby 等。 9. 算法的控制结构有三种，即顺序结构、分支结构和循环结构。 10. 顺序结构指的是算法中各个步骤按照先后顺序依次执行的结构。 11. 先进行条件判断，再根据判断结果分别执行不同处理的控制结构就称为分支结构（也称选择结构） 12. 算法执行过程中， 在条件控制下， 某些操作步骤需要重复执行（循环） 的控制结构称为循环结构。 13. 循环结构的重复执行（循环）并不是没有限制，没有限制就变成死循环了。 14. 用计算机解决问题时，由于实际问题情境的复杂性，需要先对实际问题进行

3、抽象与建模，再根据建立的计算模型设计算法，并将算法用合适的方式加以准确描述。 15. 常见算法：枚举算法、解析算法、排序算法、查找算法、递归算法 16. 常见的数据结构：叉树、链表、队列、栈 17. 算法好坏衡量指标：同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。 18.时间复杂度： 算法的时间复杂度是指执行算法所需要的计算工作量。 一般来说，计算机算法是问题规模的函数，算法的时间复杂度也因此记做： 因此，问题的规模 n 越大，算法执行的时间的增长率与 f(n)的增长率正相关，称作渐进时间复杂度（Asymptotic Time Complexity）。 19.算法的空间复杂度是指算法需要消耗的内存空间。 其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。