计算机算法分析与设计第2章

计算机算法分析与设计第2章算法分析基础分治策略与应用动态规划原理及实例贪心算法原理及实例回溯法原理及实例分支限界法原理及实例contents目录算法分析基础CATALOGUE01时间复杂度的定义描述算法运行时间随问题规模增长的速度。大O表示法表示算法时间复杂度的渐近上界。常见时间复杂度常数时间复杂度O(1)、线性时间复杂度O(n)、对数时间复杂度O(logn)、线性对数时间复杂度O(nlogn)、平方时间复杂度O(n^2)、立方时间复杂度O(n^3)、指数时间复杂度O(2^n)。算法时间复杂度123描述算法在运行过程中所需额外空间的数量级。空间复杂度的定义常数空间复杂度O(1)、线性空间复杂度O(n)、平方空间复杂度O(n^2)。常见空间复杂度在算法设计中，通常需要权衡时间复杂度和空间复杂度的关系，以达到最优的算法性能。空间复杂度与时间复杂度的关系算法空间复杂度最好情况分析：指算法在最佳情况下的性能表现，通常对应时间复杂度的下界。最坏情况分析：指算法在最差情况下的性能表现，通常对应时间复杂度的上界。平均情况分析：指算法在所有可能输入下的平均性能表现，通常用于评估算法的实际性能。最好、最坏和平均情况分析的意义：对于某些算法，其在最好和最坏情况下的性能差异可能非常大，因此需要对算法在不同情况下的性能表现进行全面评估。同时，平均情况分析可以帮助我们更好地了解算法在实际应用中的性能表现。最好、最坏和平均情况分析分治策略与应用CATALOGUE02分治策略思想将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；递归地解这些子问题，然后将各子问题的解合并得到原问题的解。归并排序是采用分治法的一个非常典型的应用；归并排序的思想就是先递归分解数组，再合并数组；将数组分解成两个较小的子数组，直到子数组的大小为1，然后将子数组两两合并。典型问题：归并排序快速排序是C.R.A.Hoare于1960年提出的一种划分交换排序；快速排序的基本思想是，通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。它采用了一种分治的策略，通常称其为分治法；典型问题：快速排序动态规划原理及实例CATALOGUE03最优子结构性质大问题的最优解可以由小问题的最优解推出，即问题的最优解具有子问题的最优解组合而成的性质。边界条件确定动态规划问题的边界条件，即子问题的最小规模，以便从边界条件开始逐步求解更大规模的问题。状态转移方程根据最优子结构性质，建立状态转移方程，描述子问题之间的递推关系，从而可以通过迭代或递归的方式求解原问题。动态规划原理给定一组物品，每种物品都有一定的重量和价值，背包的总容量有限。如何选择物品放入背包，使得背包内物品的总价值最大？问题描述定义状态dp[i][j]表示前i个物品放入容量为j的背包中所能获得的最大价值。根据最优子结构性质，可以得到状态转移方程dp[i][j]=max{dp[i-1][j],dp[i-1][j-w[i]]+v[i]}，其中w[i]和v[i]分别表示第i个物品的重量和价值。通过迭代计算dp数组，最终得到dp[n][m]即为背包问题的最优解，其中n为物品数量，m为背包容量。动态规划解法背包问题VS给定两个字符串X和Y，找出它们的最长公共子序列。最长公共子序列是指这样一个序列，它是X和Y的公共子序列（即可以从X和Y中删除一些字符得到），且它的长度是所有公共子序列中最长的。动态规划解法定义状态dp[i][j]表示字符串X的前i个字符和字符串Y的前j个字符的最长公共子序列长度。根据最优子结构性质，可以得到状态转移方程dp[i][j]=dp[i-1][j-1]+1（当X[i]==Y[j]时），或者dp[i][j]=max{dp[i-1][j],dp[i][j-1]}（当X[i]!=Y[j]时）。通过迭代计算dp数组，最终得到dp[n][m]即为最长公共子序列的长度，其中n和m分别为字符串X和Y的长度。问题描述最长公共子序列贪心算法原理及实例CATALOGUE04贪心算法原理贪心算法在每一步都采取当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的。不可回溯贪心算法在有多个可选方案时，总是选择当前看来最好的方案，而不考虑其他可能更优的方案。因此，一旦做出选择，就不能回溯。适用于优化问题贪心算法通常用于解决优化问题，如求最大值、最小值或最优解等。局部最优选择010203问题描述给定一个由活动的集合，每个活动都有一个开始时间和一个结束时间。活动选择问题要求选择出最大的相互兼容的活动子集，即这些活动的时间不会相互冲突。贪心策略在活动选择问题中，贪心算法的策略是按照活动的结束时间进行排序，然后选择结束时间最早的活动，再依次选择与已选活动不冲突的活动。实例假设有4个活动，其开始时间和结束时间分别为(1,3)，(2,4)，(3,5)，(1,2)。按照结束时间排序后得到(1,2)，(1,3)，(2,4)，(3,5)。首先选择(1,2)，然后选择(2,4)，因为这两个活动的时间不冲突。因此，最大相互兼容的活动子集为{(1,2)，(2,4)}。活动选择问题问题描述给定一个连通的无向图，最小生成树问题是要求出该图的一棵包含所有顶点的树，且树上各边的权值之和最小。贪心策略在最小生成树问题中，贪心算法的策略是每次选择权值最小的边加入生成树中，但要保证加入后不会形成环。实例假设有一个包含4个顶点的无向图，其边的权值分别为{1,2}，{2,3}，{3,4}，{4,1}的权值分别为1，2，3，4。按照权值从小到大排序后得到{1,2}，{2,3}，{3,4}，{4,1}。首先选择{1,2}，然后选择{2,3}，再选择{3,4}。因此，最小生成树为{{1,2}，{2,3}，{3,4}}，权值之和为6。最小生成树回溯法原理及实例CATALOGUE05回溯法是一种基于试探和逐步回退的搜索算法，通过不断尝试和撤销操作来寻找问题的解。回溯法的基本思想是从问题的某一初始状态出发，通过逐步改变状态来试探所有可能的解。当试探到某一步时，如果发现当前状态不能达到问题的目标或无法满足问题的约束条件时，就“回溯”到上一步或若干步之前的状态，重新试探其他的可能解。回溯法通过递归或迭代的方式实现，可以系统地搜索问题的所有可能解，适用于求解组合数较多的问题。回溯法原理N皇后问题010203N皇后问题是一个经典的回溯问题，其目标是在N×N的棋盘上放置N个皇后，使得它们不能互相攻击。回溯法求解N皇后问题的基本思路是从第一行开始逐行放置皇后，每次放置一个皇后后检查是否与其他已放置的皇后冲突。如果冲突，则回溯到上一行重新放置；如果不冲突，则继续放置下一行的皇后。在实现上，可以使用一个数组来表示每行皇后的位置，同时使用两个数组分别记录每列和每条对角线上是否有皇后。通过遍历数组和检查冲突，可以逐步找到所有可能的解。图的着色问题是一个著名的NP完全问题，其目标是对给定的图进行着色，使得相邻的顶点颜色不同，且使用的颜色数最少。回溯法求解图的着色问题的基本思路是从第一个顶点开始着色，每次为当前顶点选择一种颜色，然后递归地对与当前顶点相邻的未着色顶点进行着色。如果当前顶点无法着色，则回溯到上一个顶点重新选择颜色。在实现上，可以使用一个数组来表示每个顶点的颜色，同时使用一个邻接矩阵来表示图的结构。通过遍历顶点和递归着色，可以逐步找到所有可能的解。同时，可以使用一些优化策略来减少搜索空间，如优先选择颜色数较少的顶点进行着色等。图的着色问题分支限界法原理及实例CATALOGUE06采用广度优先或深度优先策略，遍历问题的解空间树。搜索策略对每个节点进行评估，根据评估结果和已找到的最优解，决定是否继续搜索该节点及其子树。限界操作在解空间树的每个节点处，根据问题的约束条件进行分支，生成子节点。分支操作在搜索过程中，及时剪去不可能得到最优解的分支，减少搜索量。剪枝操作01030204分支限界法原理剪枝策略在搜索过程中，如果某个分支的总重量已经超过背包容量，或者总价值已经小于当前最优解，则直接剪去该分支。问题描述给定一组物品，每种物品都有自己的重量和价值，背包的总容量有限。要求选择一些物品装入背包，使得背包内物品的总价值最大。分支策略对每个物品，选择装入背包或不装入背包，生成两个子节点。限界策略根据当前背包剩余容量和已选物品的总价值，估算继续搜索可能得到的最大价值。如果估算价值小于当前最优解，则停止搜索该分支。0-1背包问题第二季度第一季度第四季度第三季度问题描述分支策略限界策略剪枝策略旅行商问题给定一组城市和每对城市之间的距离，要求旅行商从某个城市出发，访问所有