Question

你不知道的：贪婪算法

Answer 1

  贪婪算法是关注局部最优而非全局最优的算法策略，在对问题求解时， 每次选择，都是当前最佳 。当找出一个大致能解决问题的优秀解，而不需要要找出最完美的解的情况下，贪婪算法还是不错的。优秀和完美之间，需要考虑实现代价。例如：精确算法的时间复杂度是冥函数或阶乘函数，其实现代价将远远高于结果还不错的贪婪算法

  NP完全问题：不能在确定的多项式时间内解决的问题，为NP完全问题，例如：集合覆盖问题、旅行商问题(经由几个点的最短路径)、所有涉及排列组合的问题。NP完全问题，在数据量少的时候，还可求解；在数据量大的时候，求解时间不可控，速度非常慢；遇到NP完全问题，直接放弃求最优解，直接用贪婪算法求近似解即可。

集合覆盖/排列组合问题计算公式参考：