《算法技術手冊》一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)，例如上文提到的選擇排序，那麼總體的時間複雜度将會是