第一节 绪论
算法是干什么用的？我们为什么要学习算法？算法重不重要呢？在这引用一下《算法导论》里面的回答：所谓算法就是一个明确的计算过程，它取一个或者一组值作为输入，并产生一个或者一组值作为输出。换句话说，算法就是一个给好路线图、界限明确的任务。因此，一坨计算斐波那契堆的代码就是一个特定算法的实现。甚至在某种意义上可以说，两个数的相加也是一个算法，不过它很简单罢了。
一些算法是直观易懂的，这会让你认为这种逻辑思维能力和解决问题的能力是我们与生俱来的，比如像斐波那契堆。然而，对于很多人来说，他们喜欢研究复杂的算法，因为他们将来可以用这些算法作为基石来解决更加有效的问题。事实上，当你每天在自己的机器上查看邮件或听歌或者干一些其它事情的时候，你是否会想知道自己每天会用多少种算法？基于此，本文将介绍一些算法分析的基本思想，然后用一些实际的例子说明算法为什么是重要的。
第二节 运行时间分析
算法最重要的方面之一就是它运行起来有多快。当我们遇到某个问题的时候，我们可能会很快的想出解决该问题的算法，但是如果这个算法执行起来太慢的话，那我们就得重新设计了。因为算法的具体速度取决于算法的运行，以及实施的具体细节，计算机科学家通常谈论的运行时间是相对的大小输入。举个例子，输入N个整数，算法的运行时间可能会是N * N。这就是说输入一个数N，根据某种算法来实现，运行需要花C * N * N秒（C是一个常数，不受输入值的影响）。
然而，许多复杂算法的执行时间是受其他因素影响的，而不是输入值的大小。比如：对于排序算法，一组有序的整数要比一组随机整数运行起来快的多。结果呢，你会经常听到人们谈论最坏情况下运行时间，或者平均情况运行时间。而最坏情况下的运行时间往往容易了解其原因，因此常用它来作为算法的一个基准。为一个给定的算法确定最坏情况运行时间和平均情况运行时间的过程可能会非常棘手，因为它不可能运行所有的输入情况。
排序为算法的学习提供了一个很好的例子，因为在计算机科学中我们会经常使用到它。最简单的排序方式：从一组数据中找到最小的数，然后把它放在队首；接下来找到第二小的数据并将其放在第二位上，这样依次做下去就OK了。然而不幸的是，上述算法的复杂度是O(N*N)，这就意味着进行排序操作所花费的时间近似等于成员个数的平方。此时假设你要对十亿个数排序，那么将需要1018 次操作。从这个角度看，一台PC每秒可以进行109 次操作，那么想要对这些数进行排序，照此算法那将要数以年计的时间。真是不算不知道，一算可吓了一大跳啊！
不过非常幸运的是，一些神人创造了一些效率更好的排序算法，比如：快速排序、堆排序、归并排序等，这些算法的执行时间是O(N * Log(N))。这些算法使得对10亿个数排序的操作下降到了一个合理的范围，就是一般的PC就可以搞定这个问题。
最短路径问题已经研究了好多年了。当然，在这期间那些牛逼的程序员创造出了一些很经典的最算路径算法。
解决最短路径问题的算法中，其中最快的算法之一需执行O(E * V * Log(V))，其中E是可能路线的个数，V是可能经过的转折地点数。从这个角度看，当V = 1000，E = 20000时，该算法需要2秒来找到这条最短路径。（说的通俗一点，两个V构成一个E）。OK，我们来看看所描述的算法---Djikstra Algorithm（迪杰斯特拉算法），这个算法还是比较复杂的，它所使用的数据结构涉及到优先队列。然而在一些应用中，它的运行时间太慢了（假设我们想找到从纽约到旧金山的最短路，这两个城市之间的转折地点数是数以百万的）。用Djikstra太慢了，怎么办呢？程序员通过启发式方法让这一切变得好了。启发式方法在某种程度上和最短路径这个问题是相关的，并且它往往通过自身的算法来计算。在最短路径问题中，知道两点之间近似的距离是很有用的，因此也催生了更快的算法，如A* Algorithm。通常A*的运行速度要快于Djikstra。基于此，程序员提出了用启发式算法来估算值。这样做虽然不能提高算法在最坏情况下的运行时间，但是在实际应用中它确实提高了算法的速度。
几种最短路径算法：http://blog.csdn.net/fengchaokobe/article/details/7478774
第五节 近似算法
通常情况下，即使你有最高效的算法，即使这个算法拥有最良好的启发性，即使它跑在最快的计算机上，但是它却运行的很慢。那怎么办呢？这种情况下，你必须做一些必需的牺牲才能得到正确的结果。此时，程序员会找到一种方法，这种方法找到的路径可能比原来算法找到的最短路径长%10，但是我们却以此来得到预期的结果。
实际上，能为那些重要问题产生最优解的优秀算法，他们对于大多数问题是比较快的。这些中最著名的问题就算是NP了，它指的是非确定性多项式。当一个问题被叫做NP完全问题或者NP难题的时候，那就意味着没有人能用一个最优的方法来解决这个问题。进一步说，如果可以找出一个能高效的解决NP难题的算法，那么这个算法对所有的NP难题问题都是通用的。
对于NP难题问题有一个很经典的例子，即推销员旅行问题。说的是一个推销员想去N个城市旅行，他也知道从一个城市到另一个城市需要多长时间。现在的问题是：当他旅行完所有的城市时需要多长时间？由于已知解决这一问题最快的算法是很慢的，于是程序员便找出了一些更有效、更快的算法，这些算法的效果是很不错的，但是他们都不是最优的。
第六节 随机算法
有些问题我们可以用随机算法来解决。但是这样做并没有提高算法在最坏情况下的运行时间，而使得算法在平均情况下的运行变得很优秀。快速排序就是随机算法应用的一个很好的例子。在最坏情况下，快速排序执行需O(N * N)。如果将随机纳入快速排序，那么最坏情况发生的机会将会变小。对于平均情况，快速排序运行时间需O(N * Log(N))，然而其他一些算法也能保证O(N * Log(N))的运行时间，但是相对的快速排序还是比其他算法要快一些。这么说吧，令time = C * N *Log(N)，当快速排序需要C * N *Log(N)次操作时，其它算法则需要2 *C * N *Log(N)次操作（C是个常数）。
另一个使用随机数的算法是找出一组数的中位数，它的平均运行时间为O（N），这是对一组数排序和找出中位数的重大改进。进一步说，随机算法不仅简单，而且常常快于确定性（非随机）的算法。
在一组随机数中想找到中位数，并且统计有多少数小于这个中位数。我们假设有N个数，其中有K个数小于或者等于我们随机在这一组数中选中的一个数。如果 K < N/2，那么这个中位数在这组数中的位置是：(N/2 - K)，并且这个中位数大于那个随机数，所以我们就可以忽略这K个小于或等于随机数的数了。现在我想找出第(N/2 - K)小的树，怎么做呢？很简单，还是像找中位数一样，现在数组中找出一个随机数，然后重复上述的过程即可。
第七节 压缩算法
有一类算法的目的是进行数据压缩。这类算法并没有预期的输出，它的目的是做一些优化的规则。当进行数据压缩时，该算法（比如LZW 压缩算法）会用尽量少的字节来表数据。相反，通过这样的方式也能解压缩出原始的数据。在某些情况下，这种类型的算法可使用相同的技术应用到其它算法上，输出的结果也是好的，但是存在潜在的次优解。举个例子，对于JPG和MP3压缩，这两个数据压缩的方式，压缩后结果的质量略低于原来的，但是用这种方式可以创建更小的文件。MP3压缩不保留原来的歌曲文件的每一个功能特征，但是它尽量保持足够多的信息以此来保证基本的质量，同时确保大大的减少文件的大小。JPG格式的文件遵循相同的规则，但是细节肯定是不同的，因为我们的目标图像而不是音频压缩。
扩展阅读：
哈弗曼编码压缩算法：http://coolshell.cn/articles/7459.html
哈弗曼编码：http://blog.csdn.net/fengchaokobe/article/details/6969217
第八节 学习算法的重要性
作为一个计算机科学家，如果你懂得各种类型的算法，那么在用的时候就能运用自如了。如果你负责软件方面的一块重要工作，你可能要估计它运行的到底有多快。没有对运行时的分析，那么这样的估计是不准确的。进一步说，你需要了解涉及到算法的相关内容，这样你才能对特殊的情况作出预计，这些特殊的情况是否会影响到运行时的性能，是否会产生不可预期的结果。
当然，你常常会遇到一些以前没有见过的问题。这个时候，你得想出一种新的算法或者在就算法中应用一种新的方式。因此，你了解的算法越多，你找到一种新的方法的机会就越大。许多情况下，一个新问题可以转换成一个旧问题，但是这需要你对就问题理解的很透彻。
举个例子，一台交换机上有N个端口，从这些端口上通过网线可以收发数据包。而交换机首先会去分析这些数据包，然后发送给对应的端口。那么一台交换机就像计算机一样，数据包是在离散的时间间隔发送，而不是连续的。我们希望在一个快速的交换机上，每个间隔期间能发送尽可能多的数据包，以免数据的丢失。我们设计算法的目的也是为了在每个间隔期见能够发送尽可能多的数据包，也是为了让先前到达的数据包更早的发送出去。
第九节 更多实际的例子
现实生活中类似于上述的例子比比皆是，需要优秀的算法来解决。几乎所有和计算机相关的事情在某种程度上都和算法都关，而这些算法需要我们人类经过艰苦卓绝的努力才能设计出来。即使当今计算机上面最简单的应用也不可能没有算法，比如内存管理和从硬盘加载数据。
生活中有很多复杂算法的应用，但在这我只想讨论其中的两个问题。第一个就是最大流问题，第二个是动态规划，它们都能让一些不可能解决的问题变为现实。
第十节 最大流问题
最大流问题我在以前翻译过一篇很不错的文章，我将在下面给出原文和译文的链接，在这我仅用本文所举的例子描述一下最大流问题。
如果你要雇N个工人去做N项工作，但不是每个人都能做这N项工作，也就是说一个人只能做这N项工作中的某一项或者某几项，而且要使花费尽量的小。那么此时最大流算法就派上用场了，它会告诉你针对这N项工作怎样分配这N个人，并且会保证这N项工作都被完成。
扩展阅读：
最大流问题原文地址：http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlowRevisited
最大流问题译文地址：http://blog.csdn.net/fengchaokobe/article/details/7584781
第十一节 序列的比较、匹配
许多程序员在多年编程中从来没有用过动态规划，这是有可能的。然而，许多重要的算法中都融入了DP，你会在程序中经常使用这个算法，只是你没有去关注过它罢了。那么说到序列的比较和匹配，这里有两个序列：“AABAA”和“AAAB”，首先让你比较一下两个序列不同的地方，然后要求降低一个序列转变成第二个序列。比较的话很简单，一个字符一个字符比较就行了。那么对于将第一个序列转换成第二个序列，最简单的做法就是删除中间的B，然后把最后一个A编程B就行了。不要看这个算法简单，它的用处可大着呢！比如一些DNA的问题和抄袭检测等等。
上面的方法对于比较两个文件也是可行的。它会帮你找到哪一行是插入的，哪一行被删了，哪一行是修改过的等等。
扩展阅读：
字符串匹配算法：http://blog.csdn.net/fengchaokobe/article/details/7404247
第十二节 总结
人们研究和学习不同的算法就是为了解决不同的问题。有时候你会很幸运，你正在解决的问题正好和另一个问题在某些方面很相似，你能做的只是偷着乐！所以说只有你学习并掌握了一些甚至更多的算法，当你遇到问题的时候，你就可以有选择性的运用这些算法并很快的解决问题。
我们甚至可以这样说，正因为有了算法，我们可以让一些看起来不是很可能事情变成了现实！
本文原文地址：http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=importance_of_algorithms