算法 之 贪心算法（Greedy Algorithm）

算法 之 贪心算法（Greedy Algorithm）

1. 基础概念

1.1 贪心算法的定义

贪心算法是指在问题求解过程中，总是选择当前看起来最优的选项。其核心思想是通过局部最优解的累积，达到全局最优解。

1.2 贪心算法的特点

• 贪心选择性质：当前步骤的局部最优选择不会影响后续选择。
• 最优子结构：问题的最优解包含其子问题的最优解。
• 高效性：贪心算法通常比动态规划等方法更简单和快速。

1.3 使用场景

• 活动选择问题（Activity Selection Problem）
• 最小生成树算法（如 Kruskal 和 Prim 算法）
• 最短路径问题（如 Dijkstra 算法）
• 区间覆盖问题

2. 实现与操作

2.1 核心操作实现

以下代码以“活动选择问题”为例，实现贪心算法。

#include <stdio.h> #include <stdlib.h> // 活动结构体定义 typedef struct { int start; // 活动开始时间 int end; // 活动结束时间 } Activity; // 比较函数，用于按结束时间排序 int compare(const void *a, const void *b) { Activity *activityA = (Activity *)a; Activity *activityB = (Activity *)b; return activityA->end - activityB->end; } // 贪心算法实现活动选择问题 void activitySelection(Activity activities[], int n) { // 按结束时间排序活动 qsort(activities, n, sizeof(Activity), compare); printf("选定的活动如下：\n"); int lastEnd = -1; // 上一次选定活动的结束时间 for (int i = 0; i < n; i++) { if (activities[i].start >= lastEnd) { // 如果活动开始时间大于等于上一次选定活动的结束时间，则选择此活动 printf("活动[%d]: 开始时间=%d, 结束时间=%d\n", i, activities[i].start, activities[i].end); lastEnd = activities[i].end; // 更新最后选定活动的结束时间 } } } int main() { Activity activities[] = { {1, 3}, {2, 5}, {4, 6}, {6, 7}, {5, 8}, {8, 9} }; int n = sizeof(activities) / sizeof(activities[0]); activitySelection(activities, n); return 0; } </stdlib.h></stdio.h>

2.2 代码详解

• qsort：按活动结束时间对活动数组进行排序。
• 循环检查：选择开始时间大于或等于上一个选定活动结束时间的活动。
• 打印结果：输出选定的活动序列。

3. 时间与空间复杂度分析

3.1 时间复杂度

• 排序时间复杂度：O(n log n)。
• 遍历时间复杂度：O(n)。
• 总时间复杂度：O(n log n)。

3.2 空间复杂度

空间复杂度为O(1)，因为只使用了常量级额外空间。

4. 优缺点与局限性

4.1 优点

• 实现简单，代码简洁。
• 效率高，适用于大规模数据。

4.2 缺点与局限性

• 贪心选择可能无法保证全局最优解。
• 适用场景有限，需要满足贪心选择性质和最优子结构。

5. 常见应用场景

5.1 实际应用

“最小生成树”是贪心算法的经典应用。例如 Kruskal 算法和 Prim 算法。

6. 代码编译与运行

6.1 编译命令

gcc -o greedy_activity_selection greedy_activity_selection.c

6.2 测试用例

输入活动集：{1, 3}, {2, 5}, {4, 6}, {6, 7}, {5, 8}, {8, 9}

输出：

活动[0]: 开始时间=1, 结束时间=3
活动[2]: 开始时间=4, 结束时间=6
活动[3]: 开始时间=6, 结束时间=7
活动[5]: 开始时间=8, 结束时间=9