高一信息技术：算法设计与优化微课课件

高中信息技术高一信息技术：算法设计与优化概念·方法·效率·思维必修一

数据与计算学科：高中信息技术必修一

数据与计算课程导览01算法是什么从生活情境认识算法概念与五大特征02算法怎么设计掌握枚举、递归、分治三类经典方法03算法如何优化用复杂度分析评价并改进算法效率04算法向何处去回归计算思维素养与真实世界应用CHAPTER01算法是什么从生活步骤到机器指令认识算法，从身边的一件小事开始从生活场景认识算法同一件事，步骤安排不同，效率截然不同为解决一件事而设计的步骤序列，正是算法的雏形导航寻路经建国门换乘换乘1次坐4站，即可到达经崇文门换乘换乘2次坐4站，同样可达从北京站到天安门东站，路线不止一条沏茶待客洗壶1′·烧水8′·洗杯3′·拿茶1′·沏茶1′一依次完成所有事情洗壶→烧水→洗杯→拿茶→沏茶，共需

14分钟二烧水期间同步准备烧水8分钟内同步洗杯拿茶，仅需

10分钟共同发现无论是地铁换乘还是沏茶，都是在为解决一件事而设计这种步骤序列正是算法的雏形算法的定义与本质算法是解决特定问题的一套确定的、有限的步骤算法，是解决问题步骤的集合——步骤清晰、结果确定，便是可行之道定义对特定问题求解步骤的一种描述，是解决问题步骤的集合核心要素明确的目标清晰的步骤确定的结果生活化理解安排一趟出游的全过程就是一条算法：买票、订车票、订酒店、收拾行李、准时出发重要提醒同一问题可以有多种算法，只要能达到目的、步骤清晰，都是可行的算法关键区别算法本身不含歧义，机器只会忠实执行人交给它的步骤算法五大基本特征有穷、确定、可行、有输入、有输出有穷性有限步有限个步骤后终止—算法必须能在有限步骤内结束，不能无限执行下去。不无限循环—避免死循环，保证每一步执行后向终止状态推进。确定性无歧义每步含义确切—每个操作都有唯一明确的定义和执行规则。不产生歧义—同一输入在任何环境下都得到相同的执行路径。可行性可实现基本操作可实现—每一步都能由基本的运算或操作来实际完成。有限时间内完成—每个操作都应在可接受的时限内得出结果。输入可输入0个或多个输入—算法可从外部接收零个或多个数据作为运算起点。刻画运算初始情况—输入用于描述问题求解前对象的初始状态。伪算法辨析违反任何一条特征，都不能称为算法四大伪算法案例4项案例一·无终止循环流程要求反复计算直到满意，却未给终止条件，违反有穷性案例二·指令含糊指令只写"把菜切好"，未说明切什么、怎么切，违反确定性案例三·精度超限要求求出百万位的精确数值，却只允许10次运算，违反可行性案例四·只进不出程序不断读入数据，却从不输出任何结果，违反输出特征判别方法拿到一个步骤序列，逐条对照五大特征，找出缺失项算法的三种描述方法自然语言、流程图、伪代码，各有所长用合适的表达方式，让算法意图清晰传递两种文字化描述2类自然语言用日常语言描述步骤，灵活易懂，但容易产生歧义、不够严谨伪代码介于自然语言与程序代码之间，简洁规范，便于转化为程序图形化表达与选择2项流程图用标准符号图形化表达，直观严谨，分支与循环一目了然常用符号起止框、处理框、判断框、输入输出框、流程线选择原则需严谨选流程图，需快速记录选伪代码算法与程序的区别算法是思路，程序是实现计算机不产生思想，只会忠实执行人交给它的算法算法定义与属性定义解决问题的步骤集合关键属性独立于任何编程语言，可用多种方式描述程序定义与属性定义算法的具体实现关键属性必须用某种编程语言编写，可由计算机执行CHAPTER02算法怎么设计三类经典方法登场枚举、递归、分治，各有所长枚举法：逐一检验的稳妥解法把所有可能情况一个不漏地检验，从中找出答案枚举法：逐一检验，所有可能情况一个不漏，从中找出答案定义与思路定义

枚举法又称穷举法，逐个考察某类事件的所有可能情况，得出可靠结论基本思路

确定枚举对象、枚举范围和判定条件，逐一验证是否为问题的解常见结构

通常采用循环结构实现遍历四大特点结果可靠

一定正确，不会遗漏效率瓶颈

可能做大量无用功，效率较低典型场景

常涉及求极值，如最大、最小、最重潜在风险

数据量大时可能造成时间崩溃枚举法实例：火柴棒拼等式枚举范围有限，是高效枚举的前提枚举的关键在于范围有限——n∈[1,24]

使得枚举对象有明确上限，枚举才高效可行问题与约束枚举条件限定问题：用

n

根火柴棍拼出形如A+B=C的等式，求可拼出的不同等式数目约束：数字0~9所用火柴数固定，加号与等号各需

2

根，n根火柴必须全部用上关键洞察枚举边界推导关键洞察：n的取值范围为

1~24，因此枚举的数字存在上限，并非无限实现思路：枚举A和B两个数，由C=A+B直接得出C效率提示：双重循环次数控制在

5000以内，范围足够覆盖所有可能递归法：自己调用自己把大问题化为同类型的小问题，直到可以直接求解递归是函数直接或间接调用自身来解决问题的方法。两个必备要素2项递归终止条件问题规模足够小时直接求解，防止无限递归递归关系把原问题拆解为规模更小的同类问题结构与评价2项典型结构先判断终止条件，再调用自身处理子问题优缺点写起来简洁优雅，但相对穷举执行速度较慢，并需注意栈空间消耗分治算法：分而治之分解、求解、合并，三步化解复杂问题分治三步：分解、求解、合并核心思想01分解将原问题拆分为规模更小、结构相同的子问题02求解递归地解决每个子问题03合并将子问题的解逐层合并，得到原问题的解适用四条件：可分解、子问题独立、有终止条件、可合并划分建议：取

k=2

即二分最常见，子问题规模均衡可提升效率与递归关系：递归是实现方式，分治是思想分治经典应用归并排序与二分查找分治思想：将大问题拆解为可独立求解的子问题，再合并得到最终解1分解将数组从中间位置分成左右两个子数组2求解递归地对左右子数组排序3合并将两个有序子数组合并成一个新的有序数组二分查找高效检索高效检索在有序数据中每次排除一半范围，时间复杂度可降至

O(logn)现实类比公司管理由CEO到部门经理再逐级到员工；图书整理先分大类再分小类三种方法效率对比没有最好的方法，只有最适合的方法方法核心思路优点局限枚举法逐一检验所有可能结果正确不遗漏效率低，数据量大时崩溃递归法调用自身缩小问题代码简洁优雅执行较慢，占用栈空间分治算法分解求解再合并适合大规模问题要求问题可分解可合并选型思路：数据规模小且要求稳妥选枚举，问题天然可递归定义选递归，子问题独立可选分治CHAPTER03算法如何优化让算法又快又省时间与空间，衡量算法的两把尺为什么需要算法优化能解决问题只是起点，解决得又快又省才是目标同一问题可用不同算法解决，算法质量直接影响程序效率为什么要优化同一问题可用不同算法解决，算法质量直接影响程序效率。大数据时代算法处理数据的数量级越来越大，优化必不可少。用户体验要求用户希望程序响应迅速，用户量激增时也不能崩溃。优化的方向优化维度时间复杂度空间复杂度正确性健壮性核心目标增强算法处理问题的能力，使算法具有更好的泛化能力。算法评价的五大标准正确、易读、健壮、省时、省空间01正确性能正确解决预定问题，得出正确结果02可读性结构清晰，便于他人理解和调试03健壮性对异常输入能合理处理，不轻易崩溃04时间复杂度衡量算法执行时间随问题规模增长的趋势05空间复杂度衡量算法执行所占用的存储空间考试重点关注

时间复杂度

的分析与计算分析目的在于选择合适算法并改进算法时间复杂度与大O表示法关注的不是耗时多少秒，而是增长快慢复杂度看的是增长趋势，而非绝对耗时定义与核心概念时间复杂度：衡量算法执行时间随问题规模

n

增长的趋势，用

T(n)

表示为什么不用秒表计时：运行时间受

机器性能、编程语言、编译质量影响，无法客观比较事前估算：把算法执行时间看作问题规模n的函数，与机器无关大O表示法

T(n)=O(f(n))只保留最高阶项，忽略低阶项忽略常数因子含义：随规模n增大，执行时间的增长率与f(n)相同计算技巧只需看执行次数最多的语句，即最内层循环常见复杂度阶对比问题规模

n

越大，不同复杂度阶的执行次数差距越

悬殊高斯求和：两种算法对比顺序结构恒定耗时，循环结构随规模增长同样解决问题，算法一效率明显更高01算法一顺序结构解析算法思路：直接用求和公式一次性计算语句只执行常数次，时间复杂度恒定，记为O(1)耗时与问题规模

n

无关O(1)常数时间复杂度与规模n无关效率高02算法二循环结构累加算法思路：用循环从1逐项累加到n循环执行

n

次，时间复杂度记为O(n)耗时随规模

n

线性增长O(n)线性时间复杂度随规模增长耗时增长空间复杂度与原地工作衡量算法运行时的辅助空间开销空间复杂度与时间复杂度并列，共同构成算法效率的两个核心维度。定义与关注范围2项定义衡量算法执行过程中临时占用的存储空间大小，用

S(n)

表示关注范围只考虑函数体内部临时变量、辅助变量占用的空间，不计入形参和算法本身表示方式与重要结论3项表示方式同样采用大O表示法重要结论空间复杂度为

O(1)

时占用空间与n无关，称为原地工作或就地算法优化方向减少辅助空间同样是一种优化方向优化实例：奇偶判断求和一个判断，替代n次循环抓住问题规律，往往能用更少步骤得到答案算法一：暴力循环思路：循环计算每一项并累加操作：共执行

n

次循环复杂度：O(n)算法二：优化判断思路：观察相邻两项正负相消操作：只需判断

n

的奇偶性复杂度：O(1)CHAPTER04算法向何处去思维比代码走得更远算法是数字世界的思维方式计算思维：算法的素养落点算法学习的目标是形成可迁移的思维能力计算思维是拆解、梳理、优化问题的通用思维范式，图形创作、数据整理、硬件调试皆可培养信息意识对信息的敏感度与价值判断力计算思维用形式化、结构化、系统化的方法描述和解决问题数字化学习与创新运用数字工具进行学习与创造信息社会责任负责任地使用信息与技术算法学习的完整链条01分析问题02抽象建模03设计算法04编程实现超越编程计算思维是拆解、梳理、优化问题的通用思维范式图形创作数据整理硬件调试范例化培养场景学习目标算法优化形成算法优化思想与解决实际问题的能力算法改变真实世界从地图导航到生活服务的隐形支撑把地点看作节点、路线看作边、花费看作权重，抽象为图上的最短路径问题求解01地图导航路径规划寻找最短路径或最少换乘方案02内容推荐兴趣匹配推送你感兴趣的信息03物流配送路线优化规划派送路线，使总距离最短算法的另一面：责任与边界算法便利之外，也需辩证看待算法偏见训练数据或规则设计不当，可能导致不公平的结果数据隐私推荐、画像类算法可能过度采集和利用个人数据数字鸿沟算法能力分布不均，可能加剧信息获取的不平等学习启示核心素养作为数字公民，既要会用算法，也要理解算法的边界与伦理在技术应用中践行信息社会责任，形成辩证的技术态度AI时代的算法学习让AI承担重复实现，人聚焦高阶思维AI能写出代码，但想清楚为什么这样算，仍然是人的功课趋势变化01课程转向AI时代课程从知识传授转向能力培养02学习定位把AI作为身边的脚手架和智能学习伙伴，而非思考的替代不可替代的核心能力01核心能力抽象建模、算法时间复杂性分析、数据结构选择与算法设计02分工思路把重复性实现交给AI，学习者聚焦高阶思维引导学习路径与迁移应用从概念到方法，再到优化的完整闭环从概念与方法的掌握，到评价与优化的闭环，本课带你完整走通算法学习的迁移路径。认识算法概念与特征算法概念明确输入、处理、输出的基本框架