计算思维与人工智能 课件 第3章-算法与数据结构

算法与数据结构3算法定义丨数据结构丨应用实例01020304学习目标本章内容重点难点思考与练习目录CONTENTS01学习目标内容引入学习目标

思维导图学习目标内容引入学习目标思维导图算法（Algorism）一词最早出现在12世纪，用于表示十进制算术运算的规则。18世纪，任何定义明确的计算步骤都可称为算法。指导计算机完成特定任务，‌提高处理问题的速度。地图导航、网络游戏…人工智能时代，算法与数据结构的创新应用，彻底改变了世界…人工智能时代，我们能做些什么？学习目标认识算法与数据结构01理解算法的定义及特性02掌握各类算法的设计思路03理解数据结构与算法的关系04内容引入学习目标思维导图学习目标内容引入学习目标思维导图02本章内容初始算法

算法思想数据结构与算法应用3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容算法就是让程序员写出高效、可靠的计算机程序的“菜谱”。3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容1、算法定义算法是指用计算机解决某一类问题的完整的描述或步骤。算法

+数据结构

=程序瑞士计算机科学家尼克劳斯·维尔特（NiklausWirth）世界上的第一个算法：欧几里得算法（求最大公约数）欧几里得算法又称辗转相除法，基本步骤：用较大的数除以较小的数，得到的余数与除数继续相除；如此反复，最后当余数为0时，除数即为最大公约数。3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容1、算法定义【例3-1】求12和15的最大公约数。相除次数除法算式被除数除数商余数112÷151215012215÷12151213312÷312340当余数r为0时的除数就是两数的最大公约数欧几里得算法比传统穷举法求最大公约数，效率高。好的算法能提高计算效率3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容2、算法特征一个算法有0个或多个输入。如果没有输入，应该具备初始条件输入性算法的每个步骤必须都是有明确的定义，即不能产生歧义确定性算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步骤，即每个计算步骤都可以在有限时间内完成可行性一个算法必须有1个或多个输出。输出反映算法执行的结果，如果没有输出，则算法没有意义输出性算法执行的步骤必须是有限的，即一个算法对于任何输入都是可以结束的有穷性3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容3、算法描述（1）自然语言表示用自然语言，即日常的语言（汉语、英语等）来描述算法。（2）流程图表示流程图是算法的一种图形化表示方法，用统一规定的标准符号描述算法执行步骤的图形表示。优点是通俗易懂优点是直观、清晰、更易理解3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容3、算法描述（3）伪代码表示伪代码是介于程序代码和自然语言之间的一种算法描述方法。（4）程序设计语言表示用程序设计语言对算法进行描述。优点是比自然语言更紧凑，比流程图表示更自由任何算法最终都会用程序设计语言来实现3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容4、算法复杂度01正确性02可读性03容错性04算法复杂度一个问题的解决方案可能会存在多种。不同的算法会对程序实现效率产生影响。（1）算法的衡量标准对于一切合法的输入，算法都应该在有限的时间内给出正确的结果。良好的注释和清晰的逻辑结构有助于提高算法的可读性。容错性指一个算法对不合理数据输入的反应能力和处理能力。算法的复杂度体现在算法执行时，所耗费的计算机资源。算法的复杂度分为时间复杂度和空间复杂度。3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容4、算法复杂度渐近复杂度分析是一种评估算法性能的方法，‌它主要关注算法执行效率随问题规模增长的变化趋势和增长速度。（2）复杂度分析算法A算法B计算机的硬件配置会影响算法的执行时间网络速度、所采用的程序设计语言会影响运行效率数据规模也会对算法的执行效率产生影响3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容4、算法复杂度（3）时间复杂度一个算法花费的时间与算法中基本操作的执行次数成正比例，哪个算法中基本操作执行次数多，它花费时间就多。【例3-2】求数列1+2+3+…+100的和。算法问题规模n=100问题规模n=1000A2次2次B303次3003次从时间效率上分析，算法A优于算法B。3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容4、算法复杂度（3）时间复杂度算法的基本操作次数往往与所解决的问题规模n有关。算法B的基本操作执行次数可以用一个函数T(n)表示:

若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n))为算法的渐进时间复杂度，简称时间复杂度。当n趋于无穷大，则T(n)=O(n)算法B的时间复杂度为：O(n)3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容4、算法复杂度（3）时间复杂度算法A，基本操作执行次数不会随着n的增大而增加，则时间复杂度记作O(1)，称为常数阶算法B的T(n)是线性函数，时间复杂度记作O(n)，称为线性阶常见算法的时间复杂度及其性能如图所示:3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容4、算法复杂度（4）空间复杂度空间复杂度用于衡量算法占用内存空间随着数据量变大时的增长趋势。算法在计算机中运行时需要占用的空间。输入内容暂存内容输出内容空间复杂度只研究算法运行时暂存内容所占用的内存空间，且不包括程序指令。3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容1、穷举穷举法，也称暴力破解法、枚举法。基本思路是：对于要解决的问题，列举出它的所有可能的情况，逐个判断有哪些是符合问题所要求的条件，从而得到问题的解。假设采用6位长度的密码，密码的组成是10个数字的组合，那么密码可能是106种。按照目前计算机的计算能力，破解密码只是时间长短的问题。3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容1、穷举【例3-3】百鸡百钱是我国古代数学家张丘建在《算经》一书中提出的数学问题：“鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？”。

利用计算机运行速度快的优点，列举每种x，y，z的每种可能：公鸡x母鸡y小鸡z只数钱是否为解0010010034

019910036

029810039

………………02575100100√………………109910038

………………203347100215

符合方程组的就是最终的解3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容1、穷举穷举法主要用于解决“是否存在”和“有多少可能性”等类型问题；穷举法的关键：如何列举所有的情况；理论上讲,穷举法可以解决可计算领域中的各种问题；穷举法的缺点是大多数算法的时间效率都不高，适合规模比较小的问题的求解。3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容2、迭代迭代是一种通过反复执行相似的计算步骤来逐渐逼近问题解决方案的方法，这些计算步骤称为迭代。利用迭代方法解决问题，关键在于确定三个要素：确定迭代变量至少存在一个不断由旧值计算新值的变量确定迭代关系式迭代关系式决定了如何通过旧值计算出新值何时结束迭代确定迭代结束的条件3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容2、迭代【例3-4】验证角谷猜想。日本数学家角谷静夫在研究自然数时发现了一个奇怪现象：对于任意一个自然数n，若n为偶数，则将其除以2；若n为奇数，则将其乘以3，然后再加1。如此经过有限次运算后，总可以得到自然数1。给定一个自然数n，输出n变到1的过程。

假设n为5，利用迭代方法求解的过程：迭代变量n旧值迭代关系式迭代变量n新值是否结束5n=3*5+116

16n=16/28

8n=8/24

4n=4/22

2n=2/21√3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容2、迭代迭代法又分为精确迭代和近似迭代。“角谷猜想”属于精确迭代，而有些问题，迭代结束的条件不是一个精确值，而是收敛到某个近似值，例如“二分法”、“牛顿迭代法”都属于近似迭代。迭代算法在机器学习领域起着重要作用，在训练学习、模型优化中被广泛应用。3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容3、递推递推是按照一定的规律来计算序列中的每个项，通常是通过计算前面的一些项来得出序列中的指定项的值。递推是有方向性的：从已知条件出发逐步推到问题结果，属于顺推；从问题结果逐步推到初始条件，属于逆推。3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容3、递推【例3-5】斐波那契数列（Fibonaccisequence）。13世纪，意大利数学家斐波那契在《算盘书》中记录了兔子产仔问题：如果每对兔子（一雄一雌）每月能生殖一对小兔子（也是一雄一雌，下同），每对兔子第一个月没有生殖能力，但从第二个月以后便能每月生一对小兔子。假定这些兔子都没有死亡现象，那么从第一对刚出生的兔子开始，12个月以后会有多少对兔子呢？根据问题描述，列出每月兔子对数：经过月份01234567…11小兔对数10112358…55成兔对数011235813…89兔子对数1123581321…144从这里能看出什么规律？3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容3、递推斐波那契数列从第3项开始，每一项都是前两项之和。因此，斐波那契数列的递推式为：斐波那契数列符合顺推的方式，已知数列的前两项f1,f2均为1，可以递推出f3=f1+f2。

变量计算第3项计算第4项计算第5项计算第6项计算第n项f11123n-2项的值f21235n-1项的值fn2358fn-2+fn-13.1初识算法3.2算法思想3.3数据结构与算法应用本章内容3、递推斐波那契数列符合顺推的方式，已知数列的前两项f1,f2均为1，可以递推出f3=f1+f2。f1和f2并不是第1,2项的值，而是代表了当前要计算项的前两项的值。3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容3、递推【例3-6】猴子吃桃子。小猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了一个。第二天早上又将剩下的桃子吃掉一半，又多吃一个。以后每天早上都吃了前一天剩下的一半零一个。到第n天早上想再吃时，见只剩下一个桃子了。求第一天共摘多少桃子。从问题描述可知，第n天只剩下1个桃子。根据小猴子吃桃子的方式：每天吃掉一半零一个，可以推出第n-1天，共有2*（1+1）=4个。第n天剩下的桃子x计算方法n1n-14x=(1+1)*2n-210x=(4+1)*2n-322x=(10+1)*2n-446x=(22+1)*2………1x=(x+1)*2猴子吃桃子问题是典型的逆推，是从结果倒推到初始条件。3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容3、递推递推方法解决问题的关键是找到已知条件与计算过程中的联系，即找到递推关系式。从斐波那契数列的递推过程可以看出，前两项的变量在反复迭代，因此递推也是特殊的迭代。递推方法表达问题简洁、明确，适合具有明显规律的数值计算问题，且算法的复杂度较好，一般不需要额外的辅助空间。3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容4、递归小时候，我们都听过这样一个故事：从前有座山，山上有座庙，庙里有个老和尚和小和尚。老和尚喜欢给小和尚讲一个故事：从前有座山，山上有座庙，庙里有个老和尚和小和尚。老和尚喜欢给小和尚讲一个故事：……。这个故事里套着相同的故事，反反复复，可以一直讲下去，这个过程就是递归的生动体现。递归是一种思考问题的方法，通过递归可以简化问题的定义和求解过程。3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容4、递归递归算法是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归算法有两个过程：递推过程，调用自身分解问题；回归过程，逐层返回结果的过程；在支持自调用的编程语言中，递归可以通过函数调用来完成。3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容4、递归【例3-7】计算自然数n的阶乘。n的阶乘的数学定义：n的阶乘的递归定义：计算递推

回归

5!5

4！5

24=120

4!4

3！

4

6=24

3!3

2！

3

2=6

2!2

1！

2

1=2

1!1

0！

1

1=1

0!1

递推过程：即分解问题的方法递归的终止条件：即递归返回的边界3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容4、递归【例3-7】计算自然数n的阶乘。递推过程：即分解问题的方法（递推公式）递归的终止条件：即递归返回的边界n=n×(n-1)!n==0算法描述：C++语言描述：3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容4、递归【例3-8】汉诺塔问题。设有标号A、B、C的三根柱子（如图3-12所示），其中A柱子上放有从小到大的n个圆盘，要求将A柱子上的圆盘移到C柱子上去，求移动的步骤和移动的次数。移动规则：（1）一次只能移到一个盘子；（2）大盘子不能在小盘子上面；（3）移动过程中，盘子可以放在A、B、C的任意一个柱子上。3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容4、递归【例3-8】汉诺塔问题。（1）n等于1：移动步骤：A---＞C（将第n个盘子移动到目的柱）移动次数：1次3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容4、递归【例3-8】汉诺塔问题。（2）n等于2：移动次数：3次第一步：将上面的小圆盘从A移至B第二步：将大圆盘从A移至C第三步：将上面的小圆盘从B移至C3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容4、递归【例3-8】汉诺塔问题。（3）n等于3：移动次数：7次第一阶段：将上面的2个圆盘从A移至B参考n=2时，移动3次第二阶段：将大圆盘从A移至C移动1次第三阶段：将上面的2个圆盘从B移至C参考n=2时，移动3次3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容4、递归【例3-8】汉诺塔问题。当n为2和3时，移动过程就分为了三个步骤：①将n-1个圆盘从A柱移动到B柱；②将第n个圆盘移动到C柱；③将n-1个圆盘从B柱移动到C柱。①、③两个执行步骤都是移动n-1个盘子的过程，只是起始柱和目的柱不同而已“汉诺塔”问题递归算法3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容4、递归递归算法经常用于解决较为复杂的问题。例如汉诺塔问题、二叉树的遍历、图的深度优先遍历都是通过递归算法实现的。遍历过程中不断向前搜索的过程就是递归调用的过程，回溯的过程就是递归返回。递归的过程就是由大到小，由近及远，到达一个明确的终点，再原路返回，最终解决问题。3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容5、贪心战国时期，田忌和齐王赛马，两人的马分上中下三等，如果同等级的马对应比赛，田忌赢不了齐王。但是田忌遇到了孙膑，孙膑就教他用自己的下等马对齐王的上等马，再用自己的上等马对齐王的中等马，最后用自己的中等马对齐王的下等马，结果三局两胜，田忌赢了。这就是历史上有名的“田忌赛马”。这类问题可以用贪心算法解决。贪心算法的宗旨就是一个字“贪”，让田忌用最小的代价赢每一场，让齐王用最大的代价赢每一场。3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容5、贪心贪心算法是一种常见的解决优化问题的算法，其基本思想是在问题的每个决策阶段，都选择当前看起来最优的选择，即贪心地做出局部最优的决策，以期获得全局最优解。【例3-9】齐王和田忌又要赛马了，他们各派出N匹马，每场比赛，输的一方将要给赢的一方200两黄金，如果是平局的话，双方都不必拿出钱。现在每匹马的速度值是固定而且已知的，而齐王总是先出最好的马，再出次好的，也不管田忌的出马顺序。请问田忌该如何安排自己的马去对抗齐王的马，才能赢取最多的钱？贪心的原则就是用最小的代价获得最大的利益。如果田忌的马要输，就要输的有价值，要输给齐王最快的马3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容5、贪心首先将双方的赛马按照速度值排序，接下来田忌就要考虑如何安排自己的马匹了。贪心的原则就是用最小的代价获得最大的利益。如果田忌的马要输，就要输的有价值，要输给齐王最快的马，基于这样的贪心思想，可以给出如图所示的贪心策略：3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容5、贪心第一组数据第二组数据田忌的马齐王的马选择策略田忌获利田忌的马齐王的马选择策略田忌获利9295①+200200200⑤+2008387①+200170180①+2007174②-200160165①+200------------150150⑤-200两组数据说明按照上述贪心策略，如何安排赛马获取最大利益。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容程序=数据结构+算法数据结构是算法实现的数据基础3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容1、数据之间的关系数据结构研究的是数据的逻辑结构和数据的物理结构以及对数据实现的操作。（1）逻辑结构逻辑结构揭示了数据元素之间的逻辑关系。数据的逻辑结构与数据的存储无关，独立于计算机，是从具体问题抽象出来的数学模型。3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容1、数据之间的关系（2）物理结构物理结构反映了数据在计算机内存中的存储方式，可分为顺序存储结构和链式存储结构。物理结构从底层决定了数据的访问、处理等操作方法。计算机系统通过内存地址来访问目标位置的数据。3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容1、数据之间的关系（2）物理结构顺序存储结构用一组连续的存储单元存储逻辑上相邻的数据元素。可以实现随机存取。链式存储结构逻辑上相邻的数据元素在存储时，存储单元可能不连续，寻找它们时，需要通过附加的指针（地址信息）来实现。链式存储的优点是不受空间限制，空间利用率高。一组数据在计算机中的存储，可以采用顺序或者链式，也可以两者兼而有之。无论采用哪种物理结构，其目的都是为了更好的组织数据、访问数据。3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容2、数组与排序排序犹如一把将混乱变为秩序的魔法钥匙，使我们能以更高效的方式理解与处理数据。3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容2、数组与排序（1）数组：将具有相同类型的若干数据有序地组织在一起的集合。数组元素在内存中的存储是连续的，访问数组元素可以通过索引（下标）计算出这个元素的内存地址，例如查找索引为3的元素，那么a[3]的内存地址=a[0]+2*元素大小。3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容2、数组与排序（2）排序：对一组数据按照特定顺序进行排列。排序算法的衡量要素：排序效率（时间和空间）排序稳定性（相等元素在排序后的相对顺序不发生改变）先按姓名，再按年龄排序的稳定性示例排序后A、D数据行发生了位置的变化不稳定的排序会影响输入数据的有序性3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容2、数组与排序（3）冒泡排序：比较类排序，依次比较相邻两个数据，若和所期望的相反，则互换这两个数据。。一趟冒泡排序从第一个元素开始，依次比较相邻的元素，直到最后一个元素。如果第一个比第二个大，就交换它们两个元素的位置。一趟排序后，最大的元素被放到正确的位置。冒泡排序算法实现：将待排序的数据存储在一个数组里，利用数组的下标访问元素，实现比较与交换。3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容2、数组与排序冒泡排序过程一趟冒泡排序完成了一个元素位置的调整。继续从头开始两两比较，比较范围缩小至第1个元素到第5个元素之间，如此一趟趟排序，经过5趟排序后，所有元素全部排好。冒泡排序算法实现：3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容2、数组与排序冒泡排序过程优化冒泡排序可以通过设置一个标志，当某一趟排序过程中没有发生元素交换，则排序过程结束。冒泡排序一般需要经过n-1趟排序，但有时排序的趟数可以优化。冒泡排序算法实现：3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容2、数组与排序稳定排序：两个数据值为46的数据元素，在排序后，位置没有交换，因此冒泡排序属于稳定的排序算法。时间复杂度：冒泡排序需要经过n-1趟排序，每趟排序均需依次比较相邻元素，因此时间复杂度为O(n2)。空间复杂度：冒泡排序过程，不需要额外的辅助空间，利用数组的随机访问特性，进行元素比较和交换，因此空间复杂度为O(1)。冒泡排序性能分析：3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容3、栈与浏览器的前进后退栈还可以用于表达式的计算、递归的实现等3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容3、栈与浏览器的前进后退（1）什么是栈栈是一种遵循先入后出规则的数据结构。3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容3、栈与浏览器的前进后退（2）实现浏览器的前进与后退设置两个栈，一个用于后退操作，一个用于前进操作。3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容3、栈与浏览器的前进后退（2）实现浏览器的前进与后退依次浏览了A、B、C三个页面，此时在用于后退操作的栈back中，按照浏览顺序放入这三个页面点击“后退”，从back栈中弹出栈顶元素C页面，并放入front栈中。此时back栈顶元素为B，浏览器回到B页面，访问B页面继续点击“后退”，可以返回到A页面，此时，front栈中依次存储了B、C页面；若点击“前进”，从front栈中弹出栈顶元素B页面，放入back栈中，浏览器又前进到B页面3.1初识算法3.2算法思想3.3数据结构与算法应用本章内容4、图与社交关系在生命旅途中，我们就像是一个个节点，被无数看不见的边相连。每一次的相识与相离，都在这张巨大的网络图中留下独特的印记。3.1初识算法3.2算法