贪心算法基础

简介

贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最好或最优的选择，从而希望导致结果是最好或最优的算法。

基本思想

1. 建立数学模型来描述问题
2. 把求解的问题分成若干个子问题
3. 对每个子问题求解，得到子问题的局部最优解
4. 把子问题的解局部最优解合成原来问题的一个解

适用条件

1. 最优子结构：问题的最优解包含子问题的最优解
2. 局部最优解能导致全局最优解：每一步的最优解能够导致最终的最优解

经典问题

1. 找零钱问题

function makeChange(amount, coins) {
    coins.sort((a, b) => b - a); // 从大到小排序
    let result = [];
    let remaining = amount;
    
    for (let coin of coins) {
        while (remaining >= coin) {
            result.push(coin);
            remaining -= coin;
        }
    }
    
    return result;
}

2. 区间调度问题

function intervalScheduling(intervals) {
    // 按结束时间排序
    intervals.sort((a, b) => a[1] - b[1]);
    
    let result = [intervals[0]];
    let lastEnd = intervals[0][1];
    
    for (let i = 1; i < intervals.length; i++) {
        if (intervals[i][0] >= lastEnd) {
            result.push(intervals[i]);
            lastEnd = intervals[i][1];
        }
    }
    
    return result;
}

优点与缺点

优点

1. 简单直观
2. 解题速度快
3. 适用于子问题相互独立的问题

缺点

1. 不能保证得到最优解
2. 可能得到次优解
3. 不能用来解决所有问题

应用场景

1. 最小生成树算法（Prim算法、Kruskal算法）
2. 单源最短路径（Dijkstra算法）
3. 哈夫曼编码
4. 任务调度
5. 背包问题的近似解

实现步骤

1. 创建数学模型来描述问题
2. 定义贪心策略
3. 证明贪心策略的正确性
4. 实现算法
5. 分析算法的时间复杂度和空间复杂度

复杂度分析

• 时间复杂度：取决于具体问题，通常为O(n)或O(nlogn)
• 空间复杂度：通常为O(1)或O(n)

注意事项

1. 在使用贪心算法之前，需要证明贪心选择性质
2. 贪心算法不一定能得到最优解
3. 有时需要与其他算法（如动态规划）进行比较
4. 在某些情况下可以作为其他算法的启发式方法

练习建议

1. 从简单的问题开始，如找零钱问题
2. 理解每个问题的贪心策略
3. 尝试证明贪心策略的正确性
4. 多做题，积累不同类型的贪心问题