mirror of
https://github.com/krahets/hello-algo.git
synced 2024-12-24 03:56:28 +08:00
e720aa2d24
* Sync recent changes to the revised Word. * Revised the preface chapter * Revised the introduction chapter * Revised the computation complexity chapter * Revised the chapter data structure * Revised the chapter array and linked list * Revised the chapter stack and queue * Revised the chapter hashing * Revised the chapter tree * Revised the chapter heap * Revised the chapter graph * Revised the chapter searching * Reivised the sorting chapter * Revised the divide and conquer chapter * Revised the chapter backtacking * Revised the DP chapter * Revised the greedy chapter * Revised the appendix chapter * Revised the preface chapter doubly * Revised the figures
1.4 KiB
1.4 KiB
小结
- 分治是一种常见的算法设计策略，包括分（划分）和治（合并）两个阶段，通常基于递归实现。
- 判断是否是分治算法问题的依据包括：问题能否分解、子问题是否独立、子问题能否合并。
- 归并排序是分治策略的典型应用，其递归地将数组划分为等长的两个子数组，直到只剩一个元素时开始逐层合并，从而完成排序。
- 引入分治策略往往可以提升算法效率。一方面，分治策略减少了操作数量；另一方面，分治后有利于系统的并行优化。
- 分治既可以解决许多算法问题，也广泛应用于数据结构与算法设计中，处处可见其身影。
- 相较于暴力搜索，自适应搜索效率更高。时间复杂度为
O(\log n)的搜索算法通常是基于分治策略实现的。 - 二分查找是分治策略的另一个典型应用，它不包含将子问题的解进行合并的步骤。我们可以通过递归分治实现二分查找。
- 在构建二叉树的问题中，构建树（原问题）可以划分为构建左子树和右子树（子问题），这可以通过划分前序遍历和中序遍历的索引区间来实现。
- 在汉诺塔问题中，一个规模为
n的问题可以划分为两个规模为n-1的子问题和一个规模为1的子问题。按顺序解决这三个子问题后，原问题随之得到解决。