贪心算法属于哪类算法

贪心算法是一种常见的算法设计方法，也是一类常见的算法实现模式。许多经典算法问题都可以用贪心算法求解，例如最短路径、最小生成树、任务调度、背包问题等。但是，贪心算法并不是所有问题的最优解，因此在实际应用中需要权衡时间和结果的效果。

一、算法定义

贪心算法是一种选择当前状态下最优解的算法，在每一步中，选择局部最优解，并且不考虑全局最优解。每一步的最优解可以称为“贪心策略”，用于推断出全局最优解。贪心算法通常有两个步骤：构造贪心策略和证明贪心策略的正确性。

二、算法分类

贪心算法可以分为以下四种类型：

1. 贪心选择性质：也称满足贪心选择性质，指当一个问题的最优解可以通过一系列局部最优选择得到时，即存在一个贪心策略使得每次选择最优解。

2. 最优子结构性质：指问题的最优解可以通过子问题的最优解得到。因为贪心算法每一步选择都是局部最优解，所以可以推断出全局最优解。

3. 子问题重叠性质：与动态规划算法的重叠子问题不同，贪心算法中的子问题不需要重叠，每个子问题只需要跟前一个子问题相关即可。

4. 反悔选择性质：也称无后效性，指在某个状态下，无论之前做了什么决策，当前状态的选择不会对之前做过的任何决策产生影响，只考虑当前决策对后续状态的影响。这也是贪心算法与回溯算法的一个区别。

三、算法应用

1.最小生成树问题：在一张无向图中，找到一棵包含每个节点的生成树，并且所有边的权值之和最小。Kruskal算法和Prim算法都是基于贪心策略的，时间复杂度为O(ElogE)和O（ElogV）。

2.背包问题：有n个物品和一个容量为W的背包，每个物品有重量w和价值v两个属性，要求在不超过容量的情况下，选择一些物品，使得总价值最大。贪心算法可以选择排序之后按照最大价值优先选择物品放入背包，但是这种贪心策略并不一定能得到最优解。

3.活动安排问题：有n个活动，每个活动有开始和结束的时间，求出最大活动集合。贪心算法基于结束时间排序，每次选择结束时间最早的活动加入集合中。

4.任务调度问题：有一些任务需要在相同的机器上完成，每个任务有启动时间和完成时间，要求在时间上不冲突的情况下，最大化完成任务的数量。贪心算法基于启动时间排序，每次选出最早开始的任务。

四、算法优点和局限性

贪心算法具有以下优点：

1.简单易懂，通俗易学，易于实现。

2.时间复杂度较低，常用于最优解不可用，而近似最优解可行的情况下。

3.在某些问题上能够得到最优解。

但是贪心算法还存在一些局限性：

1.贪心策略未必是全局最优解，因此需要证明贪心策略的正确性。

2.某些问题不存在贪心策略，例如背包问题。

3.某些问题的时间复杂度比贪心算法更低，例如动态规划算法，分支定界等。