知乎上的一个问题，"为什么有人说弄懂了《算法导论》的 90%，就超越了 90%的程序员？"。
说这句话的人，我估计连《算法导论》的20%都还没理解，甚至都还没读完。
读90%，就超过90%程序员，这数字可真有零有整，编的甚至都不走心，两个90%。。。
对程序员来说，学算法只有三个目的：
面试需要，君不见Google、Facebook、字节、微信考的都是算法题； 基础需要。毕竟对于栈、堆、二叉树、图基本数据结构还是要理解的； 兴趣专业。更专业的游戏引擎、程序图形需要。
我倒是相信90%的程序员只需要前两项。
好了，对于前两项，《算法导论》有用吗？有，但作用不大。
真的， 真不需要看数学证明的，你不是做理论计算机科学：
Facebook、Google、外企，想的是通过LeetCode算法题，让你表达怎么做的，怎么跟面试官沟通的，基础过关不。 字节、微信，有样学样学外企，但学错了。他们只想给你一道题，让你弄清题意后直接写完答案，最好都还是能跑的。
然后给一下时间、空间复杂度就OK了。
真需要证明吗？完全不用。以上公司我全都面试过，大多数拿到过offer，所以我能理直气壮的说，真没必要。
所以，你只要找一本算法书入门，按着LeetCode，把常见题目刷完，理解了数据结构，这辈子估计都没啥需要《算法导论》的时候。
痛快打脸
下次再有人讲这些话，你可以这样子问他：如何证明一个算法，比如插入排序，是正确的？
我相信，他就会支支吾吾了。
这时候，你学完这个，就可以啪啪啪的狠狠的打醒他，因为算法导论前几章就有教这个：
数学归纳法证明验证以下算法是对的
#define LEN 5
int a[LEN] = { 10, 5, 2, 4, 7 };
void insertion_sort(void)
{
int i, j, key;
for (j = 1; j < LEN; j++) {
printf("%d, %d, %d, %d, %d\n",
a[0], a[1], a[2], a[3], a[4]);
key = a[j];
i = j - 1;
while (i >= 0 && a[i] > key) {
a[i+1] = a[i];
i--;
}
a[i+1] = key;
}
}
如何严格证明这个算法是正确的？换句话说，只要反复执行该算法的for循环体，执行LEN-1次，就一定能把数组a排好序，而不管数组a的原始数据是什么，如何证明这一点呢？我们可以借助Loop Invariant的概念和数学归纳法来理解循环结构的算法，假如某个判断条件满足以下三条准则，它就称为Loop Invariant：
第一次执行循环体之前该判断条件为真。 如果“第N-1次循环之后（或者说第N次循环之前）该判断条件为真”这个前提可以成立，那么就有办法证明第N次循环之后该判断条件仍为真。 如果在所有循环结束后该判断条件为真，那么就有办法证明该算法正确地解决了问题。
只要我们找到这个Loop Invariant，就可以证明一个循环结构的算法是正确的。上述插入排序算法的Loop Invariant是这样的判断条件：第j次循环之前，子序列a[0..j-1]是排好序的。在上面的打印结果中，我把子序列a[0..j-1]加粗表示。下面我们验证一下Loop Invariant的三条准则：
第一次执行循环之前， j=1，子序列a[0..j-1]只有一个元素a[0]，只有一个元素的序列显然是排好序的。第 j次循环之前，如果“子序列a[0..j-1]是排好序的”这个前提成立，现在要把key=a[j]插进去，按照该算法的步骤，把a[j-1]、a[j-2]、a[j-3]等等比key大的元素都依次往后移一个，直到找到合适的位置给key插入，就能证明循环结束时子序列a[0..j]是排好序的。就像插扑克牌一样，“手中已有的牌是排好序的”这个前提很重要，如果没有这个前提，就不能证明再插一张牌之后也是排好序的。当循环结束时， j=LEN，如果“子序列a[0..j-1]是排好序的”这个前提成立，那就是说a[0..LEN-1]是排好序的，也就是说整个数组a的LEN个元素都排好序了。
可见，有了这三条，就可以用数学归纳法证明这个循环是正确的。
----
麻烦各位给我点个赞、好看和转发啊，这是对我创作优质内容的鼓励
