当前位置：首页 > news >正文

网站标识描述可以填关键词吗百度知道首页网

news 2025/7/5 3:49:31

网站标识描述可以填关键词吗,百度知道首页网,平面设计网课推荐,旅游网站的设计栏目算法导论第二章：递归与分治的数学艺术本文是《算法导论》精讲专栏第二章，通过递归树可视化、主方法证明和随机化算法实战，结合完整C语言实现，深入解析算法分析的数学基础。包含递归式求解三大方法、堆排序原理证明、快速排序概率…

算法导论第二章：递归与分治的数学艺术

本文是《算法导论》精讲专栏第二章，通过递归树可视化、主方法证明和随机化算法实战，结合完整C语言实现，深入解析算法分析的数学基础。包含递归式求解三大方法、堆排序原理证明、快速排序概率分析等内容。

1. 递归式：算法分析的数学基石

1.1 递归式在算法中的应用

常见递归式与对应算法：

递归式	算法	时间复杂度
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.h>void proof_by_substitution(int n) {// 步骤1：假设T(k) ≤ ck log k 对所有k<n成立// 步骤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 i=0; i<5; i++) {proof_by_substitution(sizes[i]);}return 0;
}

输出验证：

n=4: T(n)=11.00, Bound=16.00, T(n) <= Bound: Yes
n=8: T(n)=32.00, Bound=64.00, T(n) <= Bound: Yes
n=16: T(n)=88.00, Bound=256.00, T(n) <= Bound: Yes
n=32: T(n)=224.00, Bound=1024.00, T(n) <= Bound: Yes
n=64: T(n)=544.00, Bound=4096.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, b>1

三大情况判定：

情况	条件	解	实例
1	f(n) = O(n^{log_b a-ε})	T(n) = Θ(n^{log_b a})	二分查找：T(n)=T(n/2)+Θ(1)
2	f(n) = Θ(n^{log_b a})	T(n) = Θ(n^{log_b a} log n)	归并排序：T(n)=2T(n/2)+Θ(n)
3	f(n) = Ω(n^{log_b a+ε})	T(n) = Θ(f(n))	快速排序：T(n)=2T(n/2)+Θ(n)

#include <stdio.h>
#include <math.h>void 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() {// 归并排序：a=2, b=2, f(n)=n^1printf("Merge Sort: ");master_theorem(2, 2, 1.0);// 二分查找：a=1, b=2, f(n)=1printf("Binary Search: ");master_theorem(1, 2, 0);// 矩阵乘法：a=7, b=2, f(n)=n^2printf("Strassen Matrix: ");master_theorem(7, 2, 2.0);return 0;
}

2. 堆排序：基于完全二叉树的魔法

2.1 堆的数据结构

最大堆性质：
父节点值 ≥ 子节点值

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[i+1], &A[high]);return i+1;
}// 示例：数组 [2,8,7,1,3,5,6,4]
// 划分过程：i初始为-1, 主元=4
// 步骤1: j=0, 2<=4 → i=0, 交换A[0]和A[0] → [2,8,7,1,3,5,6,4]
// 步骤2: j=1, 8>4 → 无操作
// 步骤3: j=2, 7>4 → 无操作
// 步骤4: j=3, 1<=4 → i=1, 交换A[1]和A[3] → [2,1,7,8,3,5,6,4]
// 步骤5: j=4, 3<=4 → i=2, 交换A[2]和A[4] → [2,1,3,8,7,5,6,4]
// 步骤6: j=5,5>4 → 无操作; j=6,6>4 → 无操作
// 最后：交换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-i+1)
// ∴ E[X] = Σ_{k=2}^n (2/k) * (n-k+1) ≈ 2n ln n = O(n log n)

性能对比实验：

数据特征	固定主元(ms)	随机主元(ms)	性能提升
完全有序	2560	45	56x
完全逆序	3120	52	60x
随机数据	185	175	1.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[k+1];// 初始化计数数组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]]--;}
}// 时间复杂度：Θ(n+k)，当k=O(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(n+k))
// 当d为常数且k=O(n)时，时间复杂度为Θ(n)

应用场景：

电话号码排序（d=11, k=10）
日期排序（年/月/日）
字符串字典序排序

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; i+=2) {if (A[i] < A[i+1]) {if (A[i] < *min) *min = A[i];if (A[i+1] > *max) *max = A[i+1];} else {if (A[i+1] < *min) *min = A[i+1];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, pi+1, 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ᵢ] = Σ_{i=1}^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() % (i+1);  // 生成[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;
}