还剩29页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
《算法基础》ppt课件目录CONTENTS•算法概述•算法设计基础•排序算法•搜索算法•图算法•算法复杂度分析01算法概述算法的定义总结词算法是一系列解决问题的指令,具有明确性、有限性、有效性和能够被任何人在有限的步骤内验证的特性详细描述算法是解决问题的明确和有限的步骤集合,每一步都必须清晰明确,并且每一步都能在有限的时间内完成一个算法的输出或结果是可预测的,并且能够被任何人在有限的步骤内验证算法的特性总结词算法具有输入、输出、确定性、有限性、能行性和终止性等特性详细描述算法可以有输入和输出,其结果是可以观察和度量的算法的每一步都必须明确,不存在任何歧义算法在执行过程中会终止,且执行时间是有限的算法的表示方法总结词常用的算法表示方法有自然语言、伪代码和程序流程图等详细描述自然语言描述算法是一种直观的方法,但可能不够精确伪代码介于自然语言和编程语言之间,具有更高的精确度程序流程图则通过图形方式表示算法的逻辑流程,易于理解和分析02算法设计基础贪心算法总结词贪心算法是一种在每一步选择中都采取当前情况下最好或最优(即最有利)的选择,从而希望导致结果是最好或最优的算法详细描述贪心算法通常用于解决最优化问题,它通过不断地做出在当前看来最好的选择,来希望获得全局最优解这种算法通常不会进行全局搜索,而是在每一步都采取局部最优的选择示例在找零问题中,贪心算法会尽量使用面值最小的钱币来找零,避免使用大面值的钱币分治算法总结词01分治算法是将一个复杂的问题分成两个或更多的相同或相似的子问题,然后再将子问题分成更小的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并详细描述02分治算法的核心思想是将问题分解为若干个子问题,这些子问题相互独立,并且其解法与原问题相同或类似通过求解这些子问题,最终可以得出原问题的解示例03归并排序就是一种典型的分治算法,它将数组分成两半,分别对它们进行排序,然后再将排序后的两个数组合并成一个有序的数组动态规划总结词详细描述示例动态规划是一种通过把原问题分动态规划适用于最优化问题,其斐波那契数列就是一种典型的动解为相对简单的子问题的方式来中每个状态都有一个决策者能够态规划问题,通过保存已经解决求解复杂问题的方法它通过保通过做出最佳选择来达到最优状的子问题的解,能够快速计算出存已经解决的子问题的解,避免态通过保存已经解决的子问题较大的斐波那契数重复计算,从而能够高效地解决的解,动态规划能够避免重复计这类问题算,提高解决问题的效率回溯算法总结词回溯算法是一种通过探索所有可能的候选解来求解问题的算法当发现候选解不满足要求时,回溯算法会撤销已经做出的选择并尝试其他的选择详细描述回溯算法通常用于解决约束满足问题,它通过探索所有可能的候选解来找到满足所有约束条件的解在探索过程中,如果发现候选解不满足要求,回溯算法会撤销已经做出的选择并尝试其他的选择示例排列组合问题就是一种典型的回溯算法问题,通过探索所有可能的排列组合来找到符合要求的解03排序算法冒泡排序总结词简单直观的排序算法详细描述冒泡排序是一种简单的排序算法,它重复地遍历待排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成冒泡排序时间复杂度On^2适用场景适用于小规模数据的排序,理解排序算法的入门算法选择排序总结词简单直观的排序算法详细描述选择排序是一种简单直观的排序算法它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完时间复杂度On^2适用场景数据量较小,对效率要求不高的场景插入排序总结词简单直观的排序算法详细描述插入排序的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入插入排序在实现上,在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间插入排序时间复杂度On^2适用场景数据量较小,对稳定性要求较高的场景快速排序总结词高效的排序算法详细描述快速排序是一种分而治之的排序算法它首先选择一个基准元素,然后重新排列数组,使得基准元素的左侧都比它小,右侧都比它大这个过程称为分区操作基准元素的最终位置就是分区操作结束的位置然后,对基准元素左侧和右侧的两个子数组递归进行这个过程快速排序时间复杂度平均情况下On log n,最坏情况下On^2适用场景大数据量、对效率要求高的场景04搜索算法线性搜索时间复杂度适用场景On,其中n是数组的长度当数组无序或目标元素可能不在数组中时VS二分搜索时间复杂度适用场景Olog n,其中n是数组的长度当数组有序且目标元素一定在数组中时A搜索要点一要点二时间复杂度适用场景Ob^d,其中b是分支因子,d是深度适用于有向图或无向图中寻找路径的问题,尤其适用于节点和边较多的情况05图算法Dijkstra算法总结词详细描述一种用于解决单源最短路径问题的经典算法Dijkstra算法通过不断更新源节点到其他节点的最短路径,最终找到从源节点到所有其他节点的最短路径该算法适用于稀疏图,即边的数量相对较少的情况Floyd-Warshall算法总结词详细描述一种用于解决所有节点对之间最短路径问题的算法Floyd-Warshall算法通过动态规划的思想,利用已知的边和节点信息,逐步计算出所有节点对之间的最短路径该算法适用于稠密图,即边的数量较多的情况Prim算法总结词详细描述一种用于生成最小生成树的算法Prim算法从任意一个节点开始,逐步添加边,每次选择当前生成树到其他未加入生成树的边的最小值,直到所有节点都加入生成树为止该算法适用于解决最小生成树问题06算法复杂度分析时间复杂度010203定义分类分析方法时间复杂度是衡量算法运常见的时间复杂度有O
1、通过计算算法中基本操作行时间随输入规模增长而Ol ogn、On、的数量,并考虑其与输入增长的量度On^
2、O2^n等规模的关系来评估时间复杂度空间复杂度定义分类分析方法空间复杂度是衡量算法所常见的空间复杂度有O
1、分析算法在运行过程中所需存储空间随输入规模增Olog n、On、On^2需的数据结构或临时存储长而增长的量度等空间降低算法复杂度的策略选择合适的算法优化数据结构根据问题特性选择时间复杂度和空间复杂度使用适当的数据结构可以降低算法的复杂度较低的算法分治策略动态规划将问题分解为若干个子问题,分别解决,再通过将子问题存储并复用来避免重复计算,合并结果降低时间复杂度。