总结分治法的基本思想

分治法是一种算法设计策略，它将问题划分为较小的子问题，然后通过解决子问题来解决原始问题。

个人总结如下：
分解问题：分治法首先将原始问题分解为规模较小的子问题。

这可以通过递归地将问题划分为更小的部分来实现。

分解问题的关键是确保每个子问题都是原始问题的规模的一个子集。

解决子问题：每个子问题都可以通过相同的算法来解决。

递归地应用相同的算法，直到达到基本情况，也就是子问题可以直接解决的规模。

合并解决方案：一旦解决了子问题，就将它们的解合并起来，形成原始问题的解。

这通常涉及对子问题的解进行组合，以获得原始问题的最终解。

适用性：分治法适用于那些可以自然地分解为子问题的问题。

它在解决许多常见问题时非常有效，如排序、搜索、计算最大值和最小值、归并等。

时间复杂度：分治法通常在每个子问题上执行相同的操作，并且子问题的数量通常是对数级别的。

因此，分治算法的时间复杂度通常可以表示为递归深度的多项式。

常见的时间复杂度包括O(nlogn)和O(n^2)。

并行化：由于分治法的子问题通常是相互独立的，因此它很适合并行化处理。

可以同时处理多个子问题，然后将它们的解合并起来。

这使得分治法在并行计算中具有较好的可扩展性。

总的来说，分治法是一种强大的算法设计策略，它通过将问题分解为子问题并递归地解决它们，然后将子问题的解合并起来，从而解决了许多复杂的问题。

它在算法设计和并行计算中都具有广泛的应用。

分治法1、二分搜索算法是利用（分治策略）实现的算法。

9. 实现循环赛日程表利用的算法是（分治策略）27、Strassen矩阵乘法是利用（分治策略）实现的算法。

34．实现合并排序利用的算法是（分治策略）。

实现大整数的乘法是利用的算法（分治策略）。

17．实现棋盘覆盖算法利用的算法是（分治法）。

29、使用分治法求解不需要满足的条件是（子问题必须是一样的）。

不可以使用分治法求解的是（0/1背包问题）。

动态规划下列不是动态规划算法基本步骤的是（构造最优解）下列是动态规划算法基本要素的是（子问题重叠性质）。

下列算法中通常以自底向上的方式求解最优解的是（动态规划法）备忘录方法是那种算法的变形。

（动态规划法）最长公共子序列算法利用的算法是（动态规划法）。

矩阵连乘问题的算法可由（动态规划算法B）设计实现。

实现最大子段和利用的算法是（动态规划法）。

贪心算法能解决的问题：单源最短路径问题，最小花费生成树问题，背包问题，活动安排问题，不能解决的问题：N皇后问题，0/1背包问题是贪心算法的基本要素的是（贪心选择性质和最优子结构性质）。

回溯法回溯法解旅行售货员问题时的解空间树是（排列树）。

剪枝函数是回溯法中为避免无效搜索采取的策略回溯法的效率不依赖于下列哪些因素（确定解空间的时间）分支限界法最大效益优先是（分支界限法）的一搜索方式。

分支限界法解最大团问题时，活结点表的组织形式是（最大堆）。

分支限界法解旅行售货员问题时，活结点表的组织形式是（最小堆）优先队列式分支限界法选取扩展结点的原则是（结点的优先级）在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( 分支限界法).从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,以下除( 栈式分支限界法)之外都是最常见的方式.（1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。

（2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。

分治法的简单描述
分治法是一种常见的算法设计方法，它将一个问题划分成若干个小问题，递归解决小问题，最后将小问题的解合并起来得到大问题的解。

这个过程可以被用来解决很多类型的问题，包括排序、搜索、计算等等。

分治算法的基本思想很简单，它适用于那些问题可以被划分成若干个
相同或相似的子问题的情况。

在这种方法中，我们首先将大问题划分
成若干个小问题，并对每个子问题递归地进行处理。

当子问题处理完
成后，我们将它们的解合并起来，得到大问题的解。

举个例子，假设我们需要对一个整数数组进行排序，我们可以采用归
并排序。

该算法首先将数组划分为若干个子数组，对每个子数组递归
地进行排序，然后将子数组的排序结果合并起来得到最终的排序结果。

分治算法的优点在于，它可以减少问题的复杂性，将大问题分解为小
问题处理，从而简化问题的求解过程。

与其他算法相比，分治算法可
以更快地解决一些复杂的问题，因为它更容易充分利用计算机系统的
并行性。

总的来说，分治算法是一种非常有用的算法设计方法，常常被用于解
决大型计算问题。

当我们面对那些需要将问题划分成若干个子问题才能解决的情况时，我们可以考虑采用分治算法来进行求解。

练习——简答题1.什么是算法？算法有哪些特征？答：算法是求解问题的⼀系列计算步骤。

算法具有有限性、确定性、可⾏性、输⼊性和输出性5个重要特征。

2.算法设计应满⾜的⼏个⽬标答：算法设计应满⾜正确性、可使⽤性、可读性、健壮性和⾼效率与低存储量需求。

3.算法设计的基本步骤答：算法设计的基本步骤是:(1)分析求解问题(2)选择数据结构和算法设计策略(3)描述算法(4)证明算法正确性(5)算法分析各步骤之间存在循环和反复过程。

4.什么是算法复杂性？它主要有哪两个⽅⾯构成？答：算法复杂性是算法运⾏时所需要的计算机资源的量，它包括两个⽅⾯：时间复杂性（需要时间资源的量）和空间复杂性（需要空间资源的量）。

5.分析算法复杂性的意义是什么？算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。

⼀个算法的复杂性的⾼低体现在运⾏该算法所需要的计算机资源的多少上⾯，所需的资源越多，我们就说该算法的复杂性越⾼；反之，所需的资源越低，则该算法的复杂性越低。

6.f(n)=O(g(n))答：f(n)=O(g(n))当且仅当存在正常量c和n0，使当n≥n0时，f(n)≤cg(n)，即g(n)为f(n)的上界。

7.f(n)=W(g(n))答：f(n)=W(g(n))当且仅当存在正常量c和n0，使当n≥n0时，f(n)≥cg(n)，即g(n)为f(n)的下界。

8.f(n)=Q(g(n))答：f(n)=Q(g(n))当且仅当存在正常量c1、c2和n0，使当n≥n0时，有c1g(n)≤f(n)≤c2g(n)，即g(n)与f(n)的同阶。

9.算法的平均情况、最好情况、最坏情况，哪种情况的可操作性最好，最具有实际价值？答：设⼀个算法的输⼊规模为n，Dn是所有输⼊的集合，任⼀输⼊I∈Dn，P(I)是I出现的概率，有 =1，T(I)是算法在输⼊I下所执⾏的基本语句次数，则该算法的平均执⾏时间为：A(n)=算法的最好情况为：G(n)= ，是指算法在所有输⼊I下所执⾏基本语句的最少次数。

分治法实验总结
分治法是一种常用的算法设计策略，它将问题分解成若干个子问题，然后递归地解决这些子问题，最后将子问题的解合并成原问题的解。

在本次实验中，我们通过实现归并排序和快速排序两个算法，深入理解了分治法的思想和实现方式。

我们实现了归并排序算法。

归并排序的基本思想是将待排序的序列分成若干个子序列，每个子序列都是有序的，然后再将子序列合并成一个有序的序列。

在实现过程中，我们采用了递归的方式，将序列不断地分成两半，直到每个子序列只有一个元素，然后再将这些子序列两两合并，直到最终得到一个有序的序列。

归并排序的时间复杂度为O(nlogn)，是一种稳定的排序算法。

接着，我们实现了快速排序算法。

快速排序的基本思想是选择一个基准元素，将序列分成两个部分，一部分比基准元素小，一部分比基准元素大，然后递归地对这两个部分进行排序。

在实现过程中，我们选择了序列的第一个元素作为基准元素，然后使用两个指针分别从序列的两端开始扫描，将比基准元素小的元素放在左边，将比基准元素大的元素放在右边，最后将基准元素放在中间，然后递归地对左右两个部分进行排序。

快速排序的时间复杂度为O(nlogn)，但是在最坏情况下，时间复杂度会退化为O(n^2)。

通过实现归并排序和快速排序两个算法，我们深入理解了分治法的
思想和实现方式。

分治法是一种非常重要的算法设计策略，可以用来解决很多复杂的问题，比如最近点对问题、矩阵乘法问题等。

在实际应用中，我们可以根据具体问题的特点选择合适的分治算法，以提高算法的效率和准确性。

一、选择题1、衡量一个算法好坏的标准是（C ）。

（A）运行速度快（B）占用空间少（C）时间复杂度低（D）代码短2、记号O的定义正确的是（A）。

（A）O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤f(n) ≤cg(n) }；（B）O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤cg(n) ≤f(n) }；（C）O(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有n≥n0 有：0 ≤f(n)<cg(n) }；（D）O(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有n≥n0 有：0 ≤cg(n) < f(n) }；3、二分搜索算法是利用（ A ）实现的算法。

（A）分治策略（B）动态规划法（C）贪心法（D）回溯法4、使用分治法求解不需要满足的条件是（A ）。

（A）子问题必须是一样的（B）子问题不能够重复（C）子问题的解可以合并（D）原问题和子问题使用相同的方法解5、合并排序算法是利用（A）实现的算法。

（A）分治策略（B）动态规划法（C）贪心法（D）回溯法6、实现大整数的乘法是利用（C ）的算法。

（A）贪心法（B）动态规划法（C）分治策略（D）回溯法7、以下不可以使用分治法求解的是（D ）。

（A）棋盘覆盖问题（B）选择问题（C）归并排序（D）0/1背包问题8、实现循环赛日程表利用的算法是（ A ）。

（A）分治策略（B）动态规划法（C）贪心法（D）回溯法9、实现棋盘覆盖算法利用的算法是（ A ）。

（A）分治法（B）动态规划法（C）贪心法（D）回溯法10、矩阵连乘问题的算法可由（B）设计实现。

（A）分支界限算法（B）动态规划算法（C）贪心算法（D）回溯算法11、实现大整数的乘法是利用的算法（ C ）。

（A）贪心法（B）动态规划法（C）分治策略（D）回溯法12、最长公共子序列算法利用的算法是（B）（A）分支界限法（B）动态规划法（C ）贪心法（D）回溯法13、下列算法中通常以自底向上的方式求解最优解的是（B ）（A）备忘录法（B）动态规划法（C）贪心法（D）回溯法14、下列是动态规划算法基本要素的是（D）（A）定义最优解（B）构造最优解（C）算出最优解（D）子问题重叠性质15、下列不是动态规划算法基本步骤的是（ A ）。

分治法有哪些经典用途分治法是一种常见的算法思想，它的核心思想就是将一个问题分解成多个子问题，然后解决各个子问题，最后将各个子问题的结果合并，从而得到原问题的解决方案。

分治法一般可以分为三个步骤：分解问题、解决子问题、合并子问题结果。

分治法可以用来解决许多经典问题，下面将介绍一些常见的应用。

1. 排序排序可以说是计算机程序中最常见的问题之一，而分治法则是其中的一种经典算法思想。

经典的归并排序算法就是一种基于分治法的排序算法。

该算法将数组分解成两个子数组，分别进行递归排序，最后将两个子数组合并成一个有序数组。

2. 最大子序列和问题最大子序列和问题是一个在数组中寻找一个连续子序列，使得该子序列中的元素和最大的问题。

该问题可以使用分治法来解决。

将数组分成两半，分别计算左半边、右半边以及横跨两个子数组的最大子序列和。

最后将这些结果合并，找出最大的子序列和。

3. 二分搜索二分搜索是一种常见的查找算法，它可以在有序数组中快速查找指定元素。

该算法也是一个基于分治法的算法。

将数组分成两半后查看中间元素，如果中间元素等于指定元素，则查找结束。

如果中间元素大于指定元素，则在左边的子数组中查找。

如果中间元素小于指定元素，则在右边的子数组中查找。

4. 逆序对问题逆序对问题是一个在数组中寻找所有逆序对个数的问题。

逆序对指的是在一个数组中，如果i<j且a[i]>a[j]，则称(a[i], a[j])是一个逆序对。

这个问题可以利用分治法来解决，将数组分成两个子数组，分别计算左半边、右半边以及跨越两个子数组的逆序对数。

最后将这些结果合并，得到所有逆序对的个数。

5. 矩阵乘法矩阵乘法是一个重要的数学问题，也是在计算机领域中广泛应用的问题之一。

分治法可以用来加快矩阵乘法的计算。

将两个矩阵分成四个子矩阵后，可以利用递归方式对每个子矩阵进行矩阵乘法计算，最后将结果合并得到最终的乘积矩阵。

6. 凸包问题凸包问题是计算机几何学中的一个经典问题，它的主要目标是求出一个点集的凸包，即包含给定点集的最小凸多边形。