计算机算法基础(第2章)

计算机算法基础第2章目录算法概述基本数据结构排序算法查找算法图论算法动态规划算法01算法概述算法的定义算法是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算步骤。有穷性算法必须在有限步骤内结束。确定性算法的每一步骤必须有确切的定义，不能含糊不清。可行性算法的每一步都必须是可行的，即能够由计算机执行的基本运算实现。输入算法有零个或多个输入。输出算法有一个或多个输出。算法的定义与特性通过枚举所有可能情况来求解问题。枚举算法在每一步选择中都采取在当前状态下最好或最优的选择，从而希望导致结果是最好或最优的。贪心算法算法的分类将问题分解为若干个子问题，通过求解子问题的解来得到原问题的解。通过探索所有可能的候选解来找出所有的解，如果候选解被确认不是一个解的话，就“回溯”到上一个状态。算法的分类回溯算法动态规划能够求出问题的精确解。精确算法在多项式时间内求出问题的近似解。近似算法采用随机化方法求解问题，有一定的概率得到正确解。概率算法算法的分类评估执行程序所需的时间。可以估算出程序对处理器资源的使用程度。时间复杂度评价算法对于异常情况的处理能力，以及在异常情况下能否保持正常运行并给出相应的错误提示信息。健壮性评估执行程序所需的存储空间。可以估算出程序对计算机内存资源的使用程度。空间复杂度评价算法是否正确地解决了问题。正确性评价算法的易读程度，对于后续的代码维护和修改具有重要意义。可读性0201030405算法的评价指标02基本数据结构线性表是具有n个数据元素的有限序列。线性表的定义线性表是一种典型的线性结构，数据元素之间存在一对一的关系。线性表的逻辑结构包括顺序存储结构和链式存储结构两种。线性表的存储结构线性表栈的定义栈的基本操作队列的定义队列的基本操作栈与队列栈是一种特殊的线性表，其插入和删除操作限定在表的一端进行，该端称为栈顶，另一端称为栈底。队列是一种特殊的线性表，其插入操作在表的一端进行，而删除操作在表的另一端进行。包括入栈、出栈、取栈顶元素等。包括入队、出队、判断队列是否为空等。串的定义串的基本操作数组的定义数组的基本操作串与数组01020304串是由零个或多个字符组成的有限序列。包括串的赋值、串的比较、串的连接、串的截取、串的替换等。数组是一种特殊的线性表，其数据元素是同一类型的数据，且按照一定顺序排列。包括数组的创建、数组的访问、数组的遍历、数组的排序等。二叉树的遍历包括前序遍历、中序遍历和后序遍历三种方式。二叉树的性质包括二叉树的形态、二叉树的深度、二叉树的叶子节点数等。二叉树的定义二叉树是一种特殊的树，每个节点最多只有两个子节点，分别称为左子节点和右子节点。树的定义树是一种非线性结构，由n（n>=0）个有限节点组成一个具有层次关系的集合。树的基本术语包括根节点、子节点、父节点、兄弟节点、叶子节点等。树与二叉树03排序算法将待排序的元素插入到已排序的序列中，从而得到一个新的、更长的已排序序列。插入排序的基本思想最坏情况下为O(n^2)，最好情况下为O(n)，平均情况下为O(n^2)。插入排序的时间复杂度O(1)。插入排序的空间复杂度稳定。插入排序的稳定性插入排序在未排序的序列中找到最小（或最大）元素，将其放到已排序序列的末尾。选择排序的基本思想选择排序的时间复杂度选择排序的空间复杂度选择排序的稳定性最坏情况下为O(n^2)，最好情况下为O(n^2)，平均情况下为O(n^2)。O(1)。不稳定。选择排序通过不断地交换相邻的两个元素，使得整个序列变得有序。交换排序的基本思想最坏情况下为O(n^2)，最好情况下为O(nlogn)，平均情况下为O(n^2)。交换排序的时间复杂度O(1)。交换排序的空间复杂度不稳定。交换排序的稳定性交换排序归并排序归并排序的基本思想将待排序序列分成若干个子序列，每个子序列是有序的。然后再将这些有序子序列合并成一个大的有序序列。归并排序的时间复杂度最坏情况下为O(nlogn)，最好情况下为O(nlogn)，平均情况下为O(nlogn)。归并排序的空间复杂度O(n)。归并排序的稳定性稳定。04查找算法从数据结构的一端开始，顺序扫描，直到找到所查元素为止。原理算法简单，适用于任何数据结构。优点平均时间复杂度和最坏情况下的时间复杂度均为O(n)，其中n为数据结构中元素的个数。时间复杂度当数据量很大时，查找效率低下。缺点01030204顺序查找原理：在有序数据结构中，取中间元素与所查元素进行比较，若相等则查找成功；否则，根据所查元素与中间元素的大小关系，将查找范围缩小为原数据结构的一半，继续进行二分查找，直到找到所查元素或查找范围为空为止。时间复杂度：平均时间复杂度和最坏情况下的时间复杂度均为O(logn)，其中n为数据结构中元素的个数。优点：查找效率高，适用于数据量较大的有序数据结构。缺点：要求数据结构必须是有序的，且插入和删除操作可能导致数据结构的重新排序。二分查找原理时间复杂度优点缺点哈希表查找平均时间复杂度为O(1)，最坏情况下的时间复杂度为O(n)，其中n为哈希表中元素的个数。查找效率高，适用于数据量较大的场景。哈希函数的设计和哈希冲突的解决是影响哈希表性能的关键因素。通过哈希函数将所查元素映射到一个唯一的哈希值，然后在哈希表中查找该哈希值对应的元素。树形查找原理利用树形数据结构进行查找，常见的树形查找算法包括二叉搜索树、平衡二叉树、B树、B+树等。优点查找效率高，适用于数据量较大且需要频繁进行插入和删除操作的场景。时间复杂度平均时间复杂度和最坏情况下的时间复杂度因具体的树形数据结构而异，但通常都低于O(n)，其中n为树中节点的个数。缺点树形数据结构的维护成本较高，需要保证树的平衡性以避免性能下降。05图论算法邻接矩阵、邻接表、边集数组等图的表示方法图的遍历方法图的连通性判断深度优先遍历（DFS）、广度优先遍历（BFS）通过DFS或BFS判断图是否连通，以及找到连通分量030201图的表示与遍历03Bellman-Ford算法适用于有负权边的有向图，通过对所有边进行松弛操作求解最短路径01Dijkstra算法适用于没有负权边的有向图，通过贪心策略逐步确定最短路径02Floyd算法适用于任意有向图，通过动态规划思想求解所有顶点之间的最短路径最短路径算法Prim算法从某一顶点开始，每次选择一条连接已选顶点和未选顶点的最小权值的边，直到所有顶点都被选中Kruskal算法按照边的权值从小到大的顺序选择边，每次选择一条连接两个未连通集合的边，直到所有顶点都在同一个连通集合中最小生成树算法对有向无环图进行排序，使得对于每一条有向边(u,v)，均有u在v的前面。常用方法包括基于DFS的拓扑排序和基于BFS的拓扑排序。拓扑排序在带权有向图中，从源点到汇点的最长路径称为关键路径。关键路径上的活动称为关键活动，它们的完成时间决定了整个项目的完成时间。常用方法包括基于拓扑排序和动态规划的关键路径求解。关键路径拓扑排序与关键路径06动态规划算法

动态规划原理最优子结构大问题的最优解可以由小问题的最优解推出。边界确定问题的边界条件，即最小子问题的解。状态转移方程描述子问题之间是如何转化的，即如何由小问题的解推出大问题的解。每种物品只有一个，可以选择放或不放。01背包问题每种物品有无限个，可以选择放或不放。完全背包问题每种物品有多个，可以选择放或不放，且每种物品的数量有限制。多重背包问题背包问题给定两个序列，找出它们的最长公共子序列。问题描述利用动态规划，构建一个二维数组dp，其中dp[i][j]表示第一个序列的前i个字符与第二个序列的前j个字符的最长公共子序列长度。通过状态转移方程dp[i][j]=dp[i-1][j-1]+1(ifs1[i]==s2[j])或dp[i][j]=max(dp[i-1][j],dp[i][j-1])(ifs1[i]!=s2[j])来求解。解决方案最长公共子序列问题