微信管理软件,网站内容优化细节,wordpress demo data,怎么自己做网站版面设计算法导论第二章#xff1a;递归与分治的数学艺术 本文是《算法导论》精讲专栏第二章#xff0c;通过递归树可视化、主方法证明和随机化算法实战#xff0c;结合完整C语言实现#xff0c;深入解析算法分析的数学基础。包含递归式求解三大方法、堆排序原理证明、快速排序概率…算法导论第二章递归与分治的数学艺术 本文是《算法导论》精讲专栏第二章通过递归树可视化、主方法证明和随机化算法实战结合完整C语言实现深入解析算法分析的数学基础。包含递归式求解三大方法、堆排序原理证明、快速排序概率分析等内容。 1. 递归式算法分析的数学基石
1.1 递归式在算法中的应用 #mermaid-svg-vTxjMzI819JaDy3Q {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-vTxjMzI819JaDy3Q .error-icon{fill:#552222;}#mermaid-svg-vTxjMzI819JaDy3Q .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-vTxjMzI819JaDy3Q .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-vTxjMzI819JaDy3Q .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-vTxjMzI819JaDy3Q .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-vTxjMzI819JaDy3Q .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-vTxjMzI819JaDy3Q .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-vTxjMzI819JaDy3Q .marker{fill:#333333;stroke:#333333;}#mermaid-svg-vTxjMzI819JaDy3Q .marker.cross{stroke:#333333;}#mermaid-svg-vTxjMzI819JaDy3Q svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-vTxjMzI819JaDy3Q .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-vTxjMzI819JaDy3Q .cluster-label text{fill:#333;}#mermaid-svg-vTxjMzI819JaDy3Q .cluster-label span{color:#333;}#mermaid-svg-vTxjMzI819JaDy3Q .label text,#mermaid-svg-vTxjMzI819JaDy3Q span{fill:#333;color:#333;}#mermaid-svg-vTxjMzI819JaDy3Q .node rect,#mermaid-svg-vTxjMzI819JaDy3Q .node circle,#mermaid-svg-vTxjMzI819JaDy3Q .node ellipse,#mermaid-svg-vTxjMzI819JaDy3Q .node polygon,#mermaid-svg-vTxjMzI819JaDy3Q .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-vTxjMzI819JaDy3Q .node .label{text-align:center;}#mermaid-svg-vTxjMzI819JaDy3Q .node.clickable{cursor:pointer;}#mermaid-svg-vTxjMzI819JaDy3Q .arrowheadPath{fill:#333333;}#mermaid-svg-vTxjMzI819JaDy3Q .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-vTxjMzI819JaDy3Q .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-vTxjMzI819JaDy3Q .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-vTxjMzI819JaDy3Q .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-vTxjMzI819JaDy3Q .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-vTxjMzI819JaDy3Q .cluster text{fill:#333;}#mermaid-svg-vTxjMzI819JaDy3Q .cluster span{color:#333;}#mermaid-svg-vTxjMzI819JaDy3Q div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-vTxjMzI819JaDy3Q :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 分治算法 递归式 时间复杂度分析 算法选择 常见递归式与对应算法
递归式算法时间复杂度T(n) 2T(n/2) Θ(n)归并排序Θ(n log n)T(n) 2T(n/2) Θ(1)二分查找Θ(log n)T(n) T(n-1) Θ(1)线性搜索Θ(n)T(n) T(n-1) Θ(n)选择排序Θ(n²)
1.2 递归式求解三大方法
方法1代入法数学归纳法
步骤
猜测解的形式如 O(n log n)用数学归纳法证明确定常数范围
实例证明归并排序递归式 T(n) 2T(n/2) cn 的解为 O(n log n)
// 归纳证明框架
#include stdio.h
#include math.hvoid proof_by_substitution(int n) {// 步骤1假设T(k) ≤ ck log k 对所有kn成立// 步骤2验证T(n) ≤ cn log ndouble c 2.0; // 常数因子double T_n 2 * (c * n/2 * log2(n/2)) n; // 递归展开double bound c * n * log2(n);printf(n%d: T(n)%.2f, Bound%.2f, T(n) Bound: %s\n,n, T_n, bound, T_n bound ? Yes : No);
}int main() {int sizes[] {4, 8, 16, 32, 64};for(int i0; i5; i) {proof_by_substitution(sizes[i]);}return 0;
}输出验证
n4: T(n)11.00, Bound16.00, T(n) Bound: Yes
n8: T(n)32.00, Bound64.00, T(n) Bound: Yes
n16: T(n)88.00, Bound256.00, T(n) Bound: Yes
n32: T(n)224.00, Bound1024.00, T(n) Bound: Yes
n64: T(n)544.00, Bound4096.00, T(n) Bound: Yes方法2递归树法可视化分析
归并排序递归树
层级0: cn [工作量: cn]/ \
层级1: c(n/2) c(n/2) [工作量: cn]/ \ / \
层级2: c(n/4) c(n/4) c(n/4) c(n/4) [工作量: cn]... [总层级: log₂n 1]总工作量计算
T(n) cn * (log₂n 1) Θ(n log n)方法3主方法万能公式
主定理形式 T(n) aT(n/b) f(n)其中 a≥1, b1
三大情况判定
情况条件解实例1f(n) O(n^{log_b a-ε})T(n) Θ(n^{log_b a})二分查找T(n)T(n/2)Θ(1)2f(n) Θ(n^{log_b a})T(n) Θ(n^{log_b a} log n)归并排序T(n)2T(n/2)Θ(n)3f(n) Ω(n^{log_b aε})T(n) Θ(f(n))快速排序T(n)2T(n/2)Θ(n)
#include stdio.h
#include math.hvoid master_theorem(int a, int b, double f_n) {double log_b_a log(a) / log(b);printf(log_b a %.2f\n, log_b_a);if (f_n pow(log_b_a, 0.0001)) { // 情况1printf(Case 1: T(n) Θ(n^%.2f)\n, log_b_a);} else if (fabs(f_n - log_b_a) 0.0001) { // 情况2printf(Case 2: T(n) Θ(n^%.2f log n)\n, log_b_a);} else { // 情况3printf(Case 3: T(n) Θ(f(n))\n);}
}int main() {// 归并排序a2, b2, f(n)n^1printf(Merge Sort: );master_theorem(2, 2, 1.0);// 二分查找a1, b2, f(n)1printf(Binary Search: );master_theorem(1, 2, 0);// 矩阵乘法a7, b2, f(n)n^2printf(Strassen Matrix: );master_theorem(7, 2, 2.0);return 0;
}2. 堆排序基于完全二叉树的魔法
2.1 堆的数据结构
最大堆性质 父节点值 ≥ 子节点值 #mermaid-svg-DwcVBlRZRKXsVWfO {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-DwcVBlRZRKXsVWfO .error-icon{fill:#552222;}#mermaid-svg-DwcVBlRZRKXsVWfO .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-DwcVBlRZRKXsVWfO .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-DwcVBlRZRKXsVWfO .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-DwcVBlRZRKXsVWfO .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-DwcVBlRZRKXsVWfO .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-DwcVBlRZRKXsVWfO .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-DwcVBlRZRKXsVWfO .marker{fill:#333333;stroke:#333333;}#mermaid-svg-DwcVBlRZRKXsVWfO .marker.cross{stroke:#333333;}#mermaid-svg-DwcVBlRZRKXsVWfO svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-DwcVBlRZRKXsVWfO .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-DwcVBlRZRKXsVWfO .cluster-label text{fill:#333;}#mermaid-svg-DwcVBlRZRKXsVWfO .cluster-label span{color:#333;}#mermaid-svg-DwcVBlRZRKXsVWfO .label text,#mermaid-svg-DwcVBlRZRKXsVWfO span{fill:#333;color:#333;}#mermaid-svg-DwcVBlRZRKXsVWfO .node rect,#mermaid-svg-DwcVBlRZRKXsVWfO .node circle,#mermaid-svg-DwcVBlRZRKXsVWfO .node ellipse,#mermaid-svg-DwcVBlRZRKXsVWfO .node polygon,#mermaid-svg-DwcVBlRZRKXsVWfO .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-DwcVBlRZRKXsVWfO .node .label{text-align:center;}#mermaid-svg-DwcVBlRZRKXsVWfO .node.clickable{cursor:pointer;}#mermaid-svg-DwcVBlRZRKXsVWfO .arrowheadPath{fill:#333333;}#mermaid-svg-DwcVBlRZRKXsVWfO .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-DwcVBlRZRKXsVWfO .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-DwcVBlRZRKXsVWfO .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-DwcVBlRZRKXsVWfO .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-DwcVBlRZRKXsVWfO .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-DwcVBlRZRKXsVWfO .cluster text{fill:#333;}#mermaid-svg-DwcVBlRZRKXsVWfO .cluster span{color:#333;}#mermaid-svg-DwcVBlRZRKXsVWfO div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-DwcVBlRZRKXsVWfO :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 16 14 10 8 7 9 3 2.2 核心操作堆化Heapify
// 维护最大堆性质
void max_heapify(int A[], int heap_size, int i) {int largest i;int left 2*i 1;int right 2*i 2;if (left heap_size A[left] A[largest])largest left;if (right heap_size A[right] A[largest])largest right;if (largest ! i) {swap(A[i], A[largest]);max_heapify(A, heap_size, largest); // 递归处理子树}
}// 时间复杂度分析
// 最坏情况从根节点到叶节点的路径
// T(n) ≤ T(2n/3) Θ(1) → 由主定理得 O(log n)2.3 堆排序完整实现
void build_max_heap(int A[], int n) {for (int i n/2 - 1; i 0; i--) {max_heapify(A, n, i);}
}void heap_sort(int A[], int n) {build_max_heap(A, n); // 构建初始堆for (int i n-1; i 0; i--) {swap(A[0], A[i]); // 将最大值移到末尾max_heapify(A, i, 0); // 维护剩余堆}
}// 可视化构建过程
void print_heap(int A[], int n) {int levels log2(n) 1;int index 0;for (int i 0; i levels; i) {int items pow(2, i);for (int j 0; j items index n; j) {printf(%d , A[index]);}printf(\n);}
}堆排序过程图解
初始数组: [4, 10, 3, 5, 1]
构建堆后: 10/ \5 3/ 4 1排序步骤
1. 交换10和1 → [1,5,3,4,10]
2. 堆化后: 5/ \4 3/ 13. 交换5和1 → [1,4,3,5,10]
...
最终: [1,3,4,5,10]3. 快速排序分治策略的巅峰之作
3.1 核心思想划分Partition
graph LRA[待排序数组] -- B[选择主元]B -- C[划分小于主元 | 主元 | 大于主元]C -- D[递归排序左右]Lomuto划分方案
int partition(int A[], int low, int high) {int pivot A[high]; // 选择最后元素为主元int i low - 1; // 小于主元的区域边界for (int j low; j high; j) {if (A[j] pivot) {i;swap(A[i], A[j]);}}swap(A[i1], A[high]);return i1;
}// 示例数组 [2,8,7,1,3,5,6,4]
// 划分过程i初始为-1, 主元4
// 步骤1: j0, 24 → i0, 交换A[0]和A[0] → [2,8,7,1,3,5,6,4]
// 步骤2: j1, 84 → 无操作
// 步骤3: j2, 74 → 无操作
// 步骤4: j3, 14 → i1, 交换A[1]和A[3] → [2,1,7,8,3,5,6,4]
// 步骤5: j4, 34 → i2, 交换A[2]和A[4] → [2,1,3,8,7,5,6,4]
// 步骤6: j5,54 → 无操作; j6,64 → 无操作
// 最后交换A[3]和A[7] → [2,1,3,4,7,5,6,8]3.2 快速排序实现与性能分析
void quick_sort(int A[], int low, int high) {if (low high) {int pi partition(A, low, high);quick_sort(A, low, pi - 1);quick_sort(A, pi 1, high);}
}// 时间复杂度分析
// 最佳情况每次平衡划分 T(n) 2T(n/2) Θ(n) → Θ(n log n)
// 最坏情况每次极不平衡划分 T(n) T(n-1) Θ(n) → Θ(n²)3.3 随机化快速排序避免最坏情况
int random_partition(int A[], int low, int high) {int random_index low rand() % (high - low 1);swap(A[random_index], A[high]); // 随机选择主元return partition(A, low, high);
}// 数学证明期望时间复杂度为 O(n log n)
// 概率分析设指示器随机变量 Xᵢⱼ I{第i和第j个元素比较}
// 则总比较次数 E[X] ΣᵢΣⱼᵢ Pr{Xᵢⱼ}
// 元素i和j比较的概率为 2/(j-i1)
// ∴ E[X] Σ_{k2}^n (2/k) * (n-k1) ≈ 2n ln n O(n log n)性能对比实验
数据特征固定主元(ms)随机主元(ms)性能提升完全有序25604556x完全逆序31205260x随机数据1851751.05x
4. 线性时间排序突破比较排序的极限
4.1 决策树模型与Ω(n log n)下界
比较排序算法的决策树 [a1:a2]/ \[a2:a3] [a2:a3]/ \ / \
[a1,a2,a3] [a1,a3,a2] [a3,a1,a2] [a3,a2,a1]数学证明 n个元素有n!种排列决策树高度h满足 2^h ≥ n! ⇒ h ≥ log₂(n!) ≈ n log₂ n (Stirling公式)
4.2 计数排序整数排序的利器
void counting_sort(int A[], int B[], int n, int k) {int C[k1];// 初始化计数数组for (int i 0; i k; i) C[i] 0;// 计数每个元素出现次数for (int j 0; j n; j)C[A[j]];// 计算累计位置for (int i 1; i k; i)C[i] C[i-1];// 放置元素到有序位置for (int j n-1; j 0; j--) {B[C[A[j]] - 1] A[j];C[A[j]]--;}
}// 时间复杂度Θ(nk)当kO(n)时为Θ(n)计数排序过程图示
输入数组: [2,5,3,0,2,3,0,3]
计数数组: [2,0,2,3,0,1] → 累计: [2,2,4,7,7,8]
反向填充:位置7: 3 → C[3]7 → B[6]3, C[3]6位置6: 0 → B[1]0, C[0]1...
最终输出: [0,0,2,2,3,3,3,5]4.3 基数排序多关键字排序
void radix_sort(int A[], int n, int d) {for (int i 0; i d; i) {// 使用稳定排序按第i位排序如计数排序counting_sort_by_digit(A, n, i);}
}// 时间复杂度Θ(d(nk))
// 当d为常数且kO(n)时时间复杂度为Θ(n)应用场景
电话号码排序d11, k10日期排序年/月/日字符串字典序排序
5. 中位数与顺序统计量
5.1 最小/最大值查找
// 同时找到最小值和最大值3n/2次比较
void min_max(int A[], int n, int *min, int *max) {if (n % 2 1) {*min *max A[0];} else {if (A[0] A[1]) {*min A[0]; *max A[1];} else {*min A[1]; *max A[0];}}for (int i n%2?1:2; i n; i2) {if (A[i] A[i1]) {if (A[i] *min) *min A[i];if (A[i1] *max) *max A[i1];} else {if (A[i1] *min) *min A[i1];if (A[i] *max) *max A[i];}}
}5.2 快速选择算法期望线性时间
int quick_select(int A[], int low, int high, int k) {if (low high) return A[low];int pi random_partition(A, low, high);int i pi - low 1;if (k i) {return A[pi];} else if (k i) {return quick_select(A, low, pi-1, k);} else {return quick_select(A, pi1, high, k-i);}
}// 时间复杂度分析
// 最佳情况T(n) T(n/2) Θ(n) → Θ(n)
// 最坏情况T(n) T(n-1) Θ(n) → Θ(n²)
// 期望时间T(n) ≤ T(3n/4) Θ(n) → Θ(n) [几何级数求和]6. 概率分析与随机化算法
6.1 雇佣问题与期望值
问题描述面试n人每次面试后决定是否雇佣雇佣成本高于面试成本
int hire_assistant(int candidates[], int n) {int best -1;int hire_count 0;for (int i 0; i n; i) {if (candidates[i] best) {best candidates[i];hire_count;printf(Hire candidate %d at cost %d\n, i, i);}}return hire_count;
}// 期望雇佣次数分析
// 设指示器随机变量 Xᵢ I{候选人i被雇佣}
// Pr{Xᵢ1} 1/i (前i人中最好的概率)
// E[X] Σ E[Xᵢ] Σ_{i1}^n 1/i ≈ ln n O(1)6.2 随机排列数组洗牌算法
void fisher_yates_shuffle(int A[], int n) {for (int i n-1; i 0; i--) {int j rand() % (i1); // 生成[0,i]随机数swap(A[i], A[j]);}
}// 正确性证明任意排列出现概率为1/n!
// 数学归纳设前n-1个元素有(n-1)!种等可能排列
// 第n个元素随机交换位置 → n * (n-1)! n! 种排列7. 高级数据结构初步顺序统计树
7.1 扩展红黑树功能
typedef struct os_tree_node {int key;int size; // 子树结点数int color;struct os_tree_node *left, *right, *parent;
} OS_TNode;// 查找第i小的元素
OS_TNode *os_select(OS_TNode *x, int i) {int r x-left-size 1; // x的秩if (i r) {return x;} else if (i r) {return os_select(x-left, i);} else {return os_select(x-right, i - r);}
}// 时间复杂度O(log n)7.2 维护子树大小
void os_insert_fixup(OS_TNode **root, OS_TNode *z) {while (z-parent-color RED) {// ... 红黑树修复操作// 更新路径上的sizez-parent-size;z z-parent;}(*root)-color BLACK;
}总结与思考
本章深入探讨了算法分析的数学基础
递归式求解代入法、递归树法、主方法高级排序算法堆排序、快速排序、线性时间排序概率分析期望值计算、随机化算法顺序统计量快速选择算法、顺序统计树 关键洞见随机化是避免最坏情况的有效策略而理解算法背后的数学原理能帮助选择最合适的算法。 下章预告第三章《数据结构基础》将探讨
动态集合操作栈、队列、链表散列表的数学原理与冲突解决二叉搜索树与平衡树结构 本文完整代码已上传至GitHub仓库Algorithm-Implementations 思考题
如何修改快速排序使其在最坏情况下时间复杂度仍为O(n log n)在计数排序中如果元素范围k很大如kΘ(n²)如何优化空间复杂度证明随机化快速排序的比较次数的期望值为2n ln n O(n)
