最近在读吴军老师的《计算之魂》,这是我读过唯一一本没有代码参考的算法书,也许以后会专门出一本《代码之魂》吧。 书中1.3 怎样寻找最好的算法,列举了使用不同方法求一个数列总和最大区间的不同算法,使得时间复杂度从O(N^3)降到O(N),书中的序列如下 1.5, -12.3, 3.2, -5.5, 23.2, 3.2, -1.4, -12.2, 34…
贪心算法是一种在每一步选择中都做出在当前看来最佳的选择,从而希望导致结果是最优的算法。 举个例子,假设我们有一个可以装下重量不超过 W 的背包,并有 n 件物品,第 i 件物品的重量为 w[i],价值为 v[i]。我们希望从中选出若干件物品,装到背包中,使得装入背包中物品的总价值最大。 这个问题就可以使用贪心算法来解决。考虑按照价值与重量的比值来排…