Zxy's Blog

小结 分治是一种常见的算法设计策略，包括分（划分）和治（合并）两个阶段，通常基于递归实现。 判断是否是分治算法问题的依据包括：问题能否分解、子问题是否独立、子问题能否合并。 归并排序是分治策略的典型应用，其递归地将数组划分为等长的两个子数组，直到只剩一个元素时开始逐层合并，从而完成排序。 引入分治策略往往可以提升算法效率。一方面，分治策略减少了操作数量；另一方面，分治后有利于系统的并行优化。 分治既可以解决许多算法问题，也广泛应用于数据结构与算法设计中，处处可见其身影。 相较于暴力搜索，自适应搜索效率更高。时间复杂度为 O(log⁡n)O(\log n)O(logn) 的搜索算法通常是基于分治策略实现的。 二分查找是分治策略的另一个典型应用，它不包含将子问题的解进行合并的步骤。我们可以通过递归分治实现二分查找。 在构建二叉树的问题中，构建树（原问题）可以划分为构建左子树和右子树（子问题），这可以通过划分前序遍历和中序遍历的索引区间来实现。 在汉诺塔问题中，一个规模为 nnn 的问题可以划分为两个规模为 n−1n-1n−1 的子问题和一个规模为 111...

汉诺塔问题 在归并排序和构建二叉树中，我们都是将原问题分解为两个规模为原问题一半的子问题。然而对于汉诺塔问题，我们采用不同的分解策略。 question 给定三根柱子，记为 `A`、`B` 和 `C` 。起始状态下，柱子 `A` 上套着 $n$ 个圆盘，它们从上到下按照从小到大的顺序排列。我们的任务是要把这 $n$ 个圆盘移到柱子 `C` 上，并保持它们的原有顺序不变（如下图所示）。在移动圆盘的过程中，需要遵守以下规则。 1. 圆盘只能从一根柱子顶部拿出，从另一根柱子顶部放入。 2. 每次只能移动一个圆盘。 3. 小圆盘必须时刻位于大圆盘之上。 我们将规模为 iii 的汉诺塔问题记作 f(i)f(i)f(i) 。例如 f(3)f(3)f(3) 代表将 333 个圆盘从 A 移动至 C 的汉诺塔问题。 考虑基本情况 如下图所示，对于问题 f(1)f(1)f(1) ，即当只有一个圆盘时，我们将它直接从 A 移动至 C 即可。 12 如下图所示，对于问题 f(2)f(2)f(2) ，即当有两个圆盘时，由于要时刻满足小圆盘在大圆盘之上，因此需要借助 B...

构建二叉树问题(前序和中序) question 给定一棵二叉树的前序遍历 `preorder` 和中序遍历 `inorder` ，请从中构建二叉树，返回二叉树的根节点。假设二叉树中没有值重复的节点（如下图所示）。 判断是否为分治问题 原问题定义为从 preorder 和 inorder 构建二叉树，是一个典型的分治问题。 问题可以分解：从分治的角度切入，我们可以将原问题划分为两个子问题：构建左子树、构建右子树，加上一步操作：初始化根节点。而对于每棵子树（子问题），我们仍然可以复用以上划分方法，将其划分为更小的子树（子问题），直至达到最小子问题（空子树）时终止。 子问题是独立的：左子树和右子树是相互独立的，它们之间没有交集。在构建左子树时，我们只需关注中序遍历和前序遍历中与左子树对应的部分。右子树同理。 子问题的解可以合并：一旦得到了左子树和右子树（子问题的解），我们就可以将它们链接到根节点上，得到原问题的解。 如何划分子树 根据以上分析，这道题可以使用分治来求解，但如何通过前序遍历 preorder 和中序遍历 inorder...

分治搜索策略 我们已经学过，搜索算法分为两大类。 暴力搜索：它通过遍历数据结构实现，时间复杂度为 O(n)O(n)O(n) 。 自适应搜索：它利用特有的数据组织形式或先验信息，时间复杂度可达到 O(log⁡n)O(\log n)O(logn) 甚至 O(1)O(1)O(1) 。 实际上，时间复杂度为 O(log⁡n)O(\log n)O(logn) 的搜索算法通常是基于分治策略实现的，例如二分查找和树。 二分查找的每一步都将问题（在数组中搜索目标元素）分解为一个小问题（在数组的一半中搜索目标元素），这个过程一直持续到数组为空或找到目标元素为止。 树是分治思想的代表，在二叉搜索树、AVL 树、堆等数据结构中，各种操作的时间复杂度皆为 O(log⁡n)O(\log n)O(logn)...

分治算法 分治（divide and...

小结 重点回顾 冒泡排序通过交换相邻元素来实现排序。通过添加一个标志位来实现提前返回，我们可以将冒泡排序的最佳时间复杂度优化到 O(n)O(n)O(n) 。 插入排序每轮将未排序区间内的元素插入到已排序区间的正确位置，从而完成排序。虽然插入排序的时间复杂度为 O(n2)O(n^2)O(n2) ，但由于单元操作相对较少，因此在小数据量的排序任务中非常受欢迎。 快速排序基于哨兵划分操作实现排序。在哨兵划分中，有可能每次都选取到最差的基准数，导致时间复杂度劣化至 O(n2)O(n^2)O(n2) 。引入中位数基准数或随机基准数可以降低这种劣化的概率。尾递归方法可以有效地减少递归深度，将空间复杂度优化到 O(log⁡n)O(\log n)O(logn) 。 归并排序包括划分和合并两个阶段，典型地体现了分治策略。在归并排序中，排序数组需要创建辅助数组，空间复杂度为 O(n)O(n)O(n) ；然而排序链表的空间复杂度可以优化至 O(1)O(1)O(1)...

基数排序 上一节介绍了计数排序，它适用于数据量 nnn 较大但数据范围 mmm 较小的情况。假设我们需要对 n=106n = 10^6n=106 个学号进行排序，而学号是一个 888 位数字，这意味着数据范围 m=108m = 10^8m=108 非常大，使用计数排序需要分配大量内存空间，而基数排序可以避免这种情况。 基数排序（radix sort）的核心思想与计数排序一致，也通过统计个数来实现排序。在此基础上，基数排序利用数字各位之间的递进关系，依次对每一位进行排序，从而得到最终的排序结果。 算法流程 以学号数据为例，假设数字的最低位是第 111 位，最高位是第 888 位，基数排序的流程如下图所示。 初始化位数 k=1k = 1k=1 。 对学号的第 kkk 位执行“计数排序”。完成后，数据会根据第 kkk 位从小到大排序。 将 kkk 增加 111 ，然后返回步骤 2. 继续迭代，直到所有位都排序完成后结束。 下面剖析代码实现。对于一个 ddd 进制的数字 xxx ，要获取其第 kkk 位 xkx_kxk​...

计数排序 计数排序（counting sort）通过统计元素数量来实现排序，通常应用于整数数组。 简单实现 先来看一个简单的例子。给定一个长度为 nnn 的数组 nums ，其中的元素都是“非负整数”，计数排序的整体流程如下图所示。 遍历数组，找出其中的最大数字，记为 mmm ，然后创建一个长度为 m+1m + 1m+1 的辅助数组 counter 。 借助 counter 统计 nums 中各数字的出现次数，其中 counter[num] 对应数字 num 的出现次数。统计方法很简单，只需遍历 nums（设当前数字为 num），每轮将 counter[num] 增加 111 即可。 由于 counter 的各个索引天然有序，因此相当于所有数字已经排序好了。接下来，我们遍历 counter ，根据各数字出现次数从小到大的顺序填入 nums 即可。 代码如下所示： 123456789101112131415161718def counting_sort_naive(nums: list[int]): ...

桶排序 前述几种排序算法都属于“基于比较的排序算法”，它们通过比较元素间的大小来实现排序。此类排序算法的时间复杂度无法超越 O(nlog⁡n)O(n \log n)O(nlogn) 。接下来，我们将探讨几种“非比较排序算法”，它们的时间复杂度可以达到线性阶。 桶排序（bucket sort）是分治策略的一个典型应用。它通过设置一些具有大小顺序的桶，每个桶对应一个数据范围，将数据平均分配到各个桶中；然后，在每个桶内部分别执行排序；最终按照桶的顺序将所有数据合并。 算法流程 考虑一个长度为 nnn 的数组，其元素是范围 [0,1)[0, 1)[0,1) 内的浮点数。桶排序的流程如下图所示。 初始化 kkk 个桶，将 nnn 个元素分配到 kkk 个桶中。 对每个桶分别执行排序（这里采用编程语言的内置排序函数）。 按照桶从小到大的顺序合并结果。 代码如下所示： 123456789101112131415161718192021def bucket_sort(nums: list[float]): ...

堆排序 堆排序（heap sort）是一种基于堆数据结构实现的高效排序算法。我们可以利用已经学过的“建堆操作”和“元素出堆操作”实现堆排序。 输入数组并建立小顶堆，此时最小元素位于堆顶。 不断执行出堆操作，依次记录出堆元素，即可得到从小到大排序的序列。 以上方法虽然可行，但需要借助一个额外数组来保存弹出的元素，比较浪费空间。在实际中，我们通常使用一种更加优雅的实现方式。 算法流程 设数组的长度为 nnn ，堆排序的流程如下图所示。 输入数组并建立大顶堆。完成后，最大元素位于堆顶。 将堆顶元素（第一个元素）与堆底元素（最后一个元素）交换。完成交换后，堆的长度减 111 ，已排序元素数量加 111 。 从堆顶元素开始，从顶到底执行堆化操作（sift down）。完成堆化后，堆的性质得到修复。 循环执行第 2. 步和第 3. 步。循环 n−1n - 1n−1 轮后，即可完成数组排序。 实际上，元素出堆操作中也包含第 2. 步和第 3. 步，只是多了一个弹出元素的步骤。 tab 1tab 2tab 3tab 4tab 5tab 6tab 7tab 8tab 9tab...