就算是科普书，也不能有这么多错误吧？
这篇书评可能有关键情节透露
由于时间原因我只简单读了书前面的一部分，就已经发现这么多错了，这书错误是不是太多了？而且很多还是低级的知识性错误。
P34:
另外, 如果一个算法的复杂度由一高一低的两部分 f(N) 和 g(N) 组成, 即 f(N)+g(N), 后面数量级低的那部分可以直接省略, 也就是说 O(f(N)+g(N))=O(f(N)).
这在数学上显然不成立, 但是在计算机算法上是被认可的. 这等于说一个西瓜加上两粒芝麻还等于原来的西瓜, 其目的是让计算机科学家们能够把注意力放在数量级的差异上.
数学上显然不成立? 这简直瞎扯。这个比喻也是荒谬。f(N)+g(N) 与 f(N) 并不是等同的关系，O(f(N)+g(N))=O(f(N)) 并不代表 f(N)+g(N) 与 f(N) 相等。
P35 页:
......在每一种组合, 计算 S(p,q) 平均要做 K/4 次加法, 这是又一重循环. 因此这种算法的复杂度是 O(K).
错了. 在每一种组合, 计算 S(p,q) 平均要做 (K-1)/3 次加法而不是 K/4 次. 这不难算.
P37 页:
2. 前后两个子序列的总和最大区间中间有间隔, 我们假定这两个子序列的总和最大区间分别是[p_1,q_1] 和 [p_2,q_2]. 这时, 整个序列的总和最大区间是下面三者中最大的那一个:
(1) [p_1,q_1];
(2) [p_2,q_2];
(3) [p_1,q_2].
至于为什么, 这是本节的思考题.
这是非常经典的问题, 古老如《编程珠玑》都有. 但是这种经典问题都犯低级错误是不是说不过去?
书上的 (3) 是不对的, 跨越边界的最大区间并不是 [p_1,q_2]. 以下序列是反例:
● 3 -9 2 2 -9 3
按图中算法, p_1=q_1=1, p_2=q_2=6, 最大区间为 [1,1], [6,6], [1,6] 中最大的那个. 这显然错了, 因为这里的最大区间应为 [3,4]. 错误结论当思考题? 思考什么?
P48:
其次，选择排序做了很多无谓的位置互换。举一个极端的例子，如果数组a已经逆序排好了，也就是说a[1]最大，a2]次之，a[N] 最小，a[1] 和 a[2] 的有效移动都应该是往后移。但是，第一遍扫描时，先将 a[2] 往前移到了第一个位置，这是个无用功。在一个序列一开始次序是完全随机的状态下，排序时这种无用的位置互换非常多。
书本所讲的所谓选择排序应该是冒泡排序。选择排序最多 N-1 次交换元素。
Selection Sort: The algorithm divides the input list into two parts: a sorted sublist of items which is built up from left to right at the front (left) of the list and a sublist of the remaining unsorted items that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.
插入排序的实现也是不合适的，本来插入排序对几乎有序的数组排序是极其高效的 ( O(n) )，按书中的处理方法直接变 O(n²).
P326:
https://book.douban.com/subject/35641088/discussion/637268598/
把泰勒公式写成斯特林公式。
前面是发现的一些错误，后面我应该不会再看了。就算把它当科普书，也不能有这么多错吧？感觉答案能回答本书的思考题 1.2 了。
思考题1.2
如果一个程序只运行一次，在编写它的时候，你是采用最直观但是效率较低的算法，还是依然寻找复杂度最优的算法?
错误的算法再高效都没任何意义，还不如写个暴力的算法。（时间复杂度优的算法不代表能在实践中使用，参考galactic algorithm）.
