目录
前言
A.建议
B.简介
一 代码实现
二 时空复杂度
A.时间复杂度：
B.空间复杂度：
三 优缺点
A.优点：
B.缺点：
C.总结
四 现实中的应用
前言
A.建议
1.学习算法最重要的是理解算法的每一步，而不是记住算法。
2.建议读者学习算法的时候，自己手动一步一步地运行算法。
tips：文中的（如果有）对数，则均以2为底数
B.简介
贪心算法是一种通过在每一步选择中选择当前状态下的最佳解决方案来达到全局最优解的算法。
一 代码实现
以下是一个简单的C语言实例，演示了贪心算法的应用，该例子解决的是找零钱的问题：
#includevoid greedyCoinChange(int coins[], int n, int amount) { // 对硬币面额进行排序，假设已经按降序排列 // 这里为了演示，假设 coins 已经按降序排列，实际中可能需要先进行排序 int i = 0; while (amount > 0 && i < n) { // 如果当前面额的硬币可以被使用 if (coins[i] <= amount) { // 计算可以使用当前面额的硬币数量 int count = amount / coins[i]; printf("Use %d coin(s) of denomination %d\n", count, coins[i]); // 更新剩余金额 amount -= count * coins[i]; } // 移动到下一个面额的硬币 i++; } if (amount > 0) { printf("Cannot provide exact change.\n"); } } int main() { // 假设硬币面额已经按降序排列 int coins[] = {25, 10, 5, 1}; int n = sizeof(coins) / sizeof(coins[0]); int amount = 63; // 需要找零的金额 printf("Greedy approach to make change for %d: \n", amount); greedyCoinChange(coins, n, amount); return 0; }
这个例子中，我们假设硬币面额已经按降序排列。贪心算法每次选择当前最大面额的硬币，直到凑够所需的金额。请注意，贪心算法并不总是能够找到全局最优解，但在某些问题上，它可以提供足够接近最优解的解决方案。在实际应用中，需要谨慎选择问题和算法，并进行适当的分析。
二 时空复杂度
A.时间复杂度：
选择最佳解决方案： 在贪心算法中，时间复杂度主要取决于选择最佳解决方案的步骤。对于每一步，我们需要找到当前状态下的最佳选择，这可能需要遍历一些元素或执行一些简单的计算。如果有 
个元素，贪心算法的时间复杂度通常是
。
整体算法的时间复杂度： 如果贪心算法包含
步，则整体算法的时间复杂度是 
，其中 n 是问题规模。在某些情况下，贪心算法可能包含嵌套循环或递归，因此需要注意算法的具体结构。
B.空间复杂度：
数据结构的空间复杂度： 贪心算法通常不需要使用额外的数据结构，除非问题本身需要。在上述找零钱的例子中，我们只使用了一些基本变量，因此空间复杂度是 
。
递归调用的空间复杂度： 如果贪心算法采用递归的方式实现，那么递归调用的深度可能会影响空间复杂度。在实际应用中，需要确保递归深度不会太大，否则可能会导致栈溢出。通常来说，可以通过迭代方式避免递归的空间开销。
三 优缺点
A.优点：
简单易实现： 贪心算法通常相对简单，易于实现和理解。算法的设计思路清晰，一步一步地选择当前局部最优解。
高效性： 贪心算法通常执行速度较快，因为它只需进行一次或几次的遍历，不需要考虑所有可能的组合。
适用范围广： 贪心算法适用于一些特定类型的问题，例如涉及到最小生成树、最短路径等问题。在这些问题中，局部最优解可以导致全局最优解。
B.缺点：
不能保证全局最优解： 贪心算法的主要缺点在于它不能保证得到全局最优解。由于每步选择都是基于局部最优，可能会导致最终的解并非全局最优。
问题依赖性： 贪心算法的适用性受到问题的依赖性的影响。有些问题适合贪心策略，而有些则不适用。需要进行仔细的问题分析，以确定贪心算法是否是解决问题的合适选择。
难以回退： 一旦做出选择，贪心算法通常难以回退。这意味着如果之后的选择导致问题无法解决，那么整体解决方案可能无效。
不同策略导致不同结果： 在某些情况下，不同的贪心策略可能导致不同的结果。选择不同的局部最优解可能会得到不同的全局结果。
C.总结
在使用贪心算法时，需要根据具体问题的特性和要求来评估其适用性。有时候，贪心算法可以作为解决问题的一部分，结合其他算法来得到更好的结果。在实际应用中，谨慎选择算法，并进行合适的分析是至关重要的。
四 现实中的应用
货物装载问题： 在物流领域，贪心算法可用于优化货物装载，选择每次装载中质量或体积最大的货物，以减少运输次数。
最小生成树问题： 在网络设计、通信网络、城市规划等领域，贪心算法被用于构建最小生成树，以确保网络的连通性，同时减少总体成本。
最短路径问题： 在导航系统和通信网络中，贪心算法可以用于寻找局部最短路径，以优化通信或导航的效率。
活动选择问题： 在时间调度和项目管理中，贪心算法可用于选择一组相互兼容的活动，以最大化完成的活动数量。
哈夫曼编码： 在数据压缩中，贪心算法被用于生成哈夫曼树，以构建有效的可变长度编码，实现数据的高效压缩。
零钱找零问题： 如前面提到的例子，贪心算法可以用于找零钱，选择面额最大的硬币来凑够特定金额。
背包问题的一些变体： 在背包问题中，贪心算法可以应用于一些变体，如分数背包问题，其中物品可以被分割以达到最优解。
任务调度问题： 在分布式系统和云计算中，贪心算法可以用于调度任务，选择最优的任务顺序以最大程度地减少完成所有任务所需的总时间。
车辆路径规划： 在物流和运输领域，贪心算法可用于规划车辆的路径，以最小化总体行驶距离或时间。