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)，例如上文提到的选择排序，那么总体的时间复杂度将会是
继续阅读与本文标签相同的文章
下一篇 :
一座倒闭了的老商场，引入系列黑科技后
-
5G远程驾驶和微公交首秀互联网大会
2026-05-14栏目： 教程
-
学宏程序编程，这些知识必不可少！
2026-05-14栏目： 教程
-
华为准备卖出“落后”的5G，多家美企极力竞争！任正非格局太大！
2026-05-14栏目： 教程
-
百度：飞桨深度学习平台已累计服务150多万开发者
2026-05-14栏目： 教程
-
滴滴公布安全功能数据：近2亿用户添加紧急联系人
2026-05-14栏目： 教程