《算法技术手册》一3.6.1 贪心

对于一个规模为n个单位的问题，可以使用贪心算法分步解决。每一步，贪心算法都会根据当前能够得到的信息做出最优解，这样可以让问题的规模下降1个单位。一旦n个步骤全部完成，算法就可以返回计算出的结果。

例如，对包含n个数的数组A进行排序，贪心选择排序就是找到A[0, n－1]中最大的值，然后和A[n－1]交换。接着重复这个过程，寻找A[0, n－2]中最大的值，然后和A[n－2]交换。这个过程会持续到整个数组排序完成。第4章介绍了关于这个算法的更多细节。

贪心算法在减小问题规模上其实是比较慢的。当每一步需要O(log n)的时间时，贪心算法将会有O(n log n)的时间复杂度。如果每一步的时间复杂度是O(n)，例如上文提到的选择排序，那么总体的时间复杂度将会是