面试时这样介绍算法，想不高薪都难，排序算法（贪心算法）_贪心算法复杂度

贪心算法介绍

贪心算法是一种以最优化搜索空间，以期待获得最优解的近似算法。它使用迭代原则，在每一步中都选取当前最佳解决方案，以期望最终达到全局最优解。

算法背景

贪心算法旨在以期望获取最优解，是一种常用的近似算法，可用于解决复杂问题。

算法流程

贪心算法的流程为：

根据决策准则，在当前的情况下，选取最优的本地解决方案，再根据该本地解决方案作 为新的初始状态，进行下一步迭代，直至最终收敛为全局最优解。

时间复杂度

贪心算法的时间复杂度一般为O(n^2)，也有O(nlogn)的特例。

空间复杂度

贪心算法的空间复杂度一般为O(1)。

优点和缺点

优点

1、算法简单，执行效率较高。

2、只追求当前最优解，求解过程便捷。

缺点

1、仅针对某一准则的优化，可能缺乏最优化措施。

2、不保证全局最优解，而只保证最终收敛到一个局部最优解。

示例代码

Java示例

public class GreedyAlgorithm {
 
    public int[] solution(int[] arr){
        // 获取最优子集
        int maxSubsetSum = 0;
        int[] maxSubset = new int[arr.length];
        // 遍历贪心算法
        for (int i = 0; i < arr.length; i++) {
            // 判断是否符合贪心准则
            if (maxSubsetSum + arr[i] > arr[i]) {
                // 添加最优子集
                maxSubset[i] = arr[i];
                maxSubsetSum += arr[i];
            }
        }
        return maxSubset;    
    }
}

Python示例

def greedy_algorithm(arr):
    # 获取最优子集
    max_subset_sum = 0
    max_subset = [0]*len(arr)
    # 遍历贪心算法
    for i in range(len(arr)):
        # 判断是否符合贪心准则
        if max_subset_sum + arr[i] > arr[i]:
            # 添加最优子集
            max_subset[i] = arr[i]
            max_subset_sum += arr[i]
            
    return max_subset

C#示例

public int[] GreedyAlgorithm(int[] arr){
        // 获取最优子集
        int maxSubsetSum = 0;
        int[] maxSubset = new int[arr.Length];
        // 遍历贪心算法
        for (int i = 0; i < arr.Length; i++){
            // 判断是否符合贪心准则
            if (maxSubsetSum + arr[i] > arr[i]){
                // 添加最优子集
                maxSubset[i] = arr[i];
                maxSubsetSum += arr[i];
            }
        }
        return maxSubset;
    }

应用场景

贪心算法可用于求解NP完全问题，如求解最小生成树，最短路径等问题，也可用于求解资源分配问题，选择问题等。

正面例子

比如用贪心算法求解最小生成树的时候，可将每次都选取最小权重的边加入到最小生成树中。

反面例子

比如用贪心算法求解最短路径时，因为仅考虑当前最短路径，可能会出现最终并不是最短的路径。

参考文献

[1] 王云, 贪心算法通俗与严谨的结合, 科学出版社, 2019.

[2] 王建强, 算法设计与分析基础, 清华大学出版社, 2012.