算法导论Lesson1
课程简介：
内容主要包括：
- 算法的含义、意义的简要介绍；
- 算法的分析；
- 插入排序、合并排序
如下图：
基本内容：
算法的含义和分析：
Informally, an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some values, or set of values, as output. An angorithm is thus a sequence of computational steps that transform the input to outpout.（Page 5, 1.1 Algorithms）
算法是一种处理技术，是对某个给定问题的一种实现。这个问题包括输入，受限条件以及想要的输出，至于中间的处理过程，则由算法来规划。
非降排序问题如下，其输入规模为n：
既然想要正确的输出，那么算法的一个重要指标，就是正确性( correctness )，通常必须保证算法对于任何可能出现的输入实例( instance )都有与之相应的正确输出。但也有例外，有一些算法可以控制其错误发生的概率，使得它在一定程度上是有用的。
对同一个问题，可能会存在多个算法可用，但是如何找到其中最合适的那些也是需要考察的。因为除了正确性，算法需要考虑的东西还有很多，比如时间和空间上的成本( cost )，对输入的规模n和输入自身的特性的反应。时间上的成本就是运行一个实例所花费的时间，空间上的成本则是存储器如内存、磁盘、网络等资源的消费。输入的规模越大，一般成本的消费也将越大，从道理上至少不会反而减少。至于输入本身的特性，同一规模下，这种特性的不同会影响成本的大小。所以，选取何种算法更具效率往往就是统计出或者假设出输入存在且偏向某些特性，继而选择那些更亲和于这些特性的算法。
以上所说的成本，不是很好进行量化的比较。比如说运行时间( running time )，如果在不同性能的机器上分别用同一批实例运行同一个算法，时间成本也许是不一样的。那么在不同性能的机器上比较两个算法的运行速度，显然就不一定靠谱了。这种就叫做绝对速度( absolute speed )，如果使用相同的物理条件，就叫做相对速度( relative speed )。
并且，同一个算法，对不同的输入的成本也是不一样的。比如说运行时间，就有三种度量，最坏运行时间( worst-case )，最少运行时间( best-case )和平均运行时间( averge-case )。对用户的保证，是告诉他我的算法最坏情况不会超过多少，而不是告诉他我这个算法最快可以达到多少。对于平均运行时间来说，就存在对输入的概率分布的估计了，当对输入的可能性未知时，这种估计就是一种假设( assumption )，比如假设它是均匀分布( uniform )的。它们存在的原因正是输入的某种特性造成的，比如排序中的输入现有的排列状态，对插排来说，显然完全逆序和已然排好序就是两个极端情况，分别对应worst-case和best-case，它们的处理效率是不一样的。
所以，聪明的做法就是不去关注某一些实例的实际运行成本，而是去关注随着输入规模增长成本的增长趋势，叫做渐进分析( asymptotic analysis )。它揭示了算法的性能。
这样做的好处在于，虽然可能在输入规模较小的时候，高渐进算法的成本比低渐进算法的成本低，但是肯定存在一个临界点，一旦输入规模超过这个临界点，低渐进算法的成本将会低于高渐进算法。所以，输入的规模也会影响选用何种算法。有时候，实际输入的规模小于这个临界点，那么选用的其实是高渐进的算法。
渐进符号：
order of growth
asaymptotic upper bound
asaymptotic lower bound
还值得一提的是数据机构和算法的关系。数据结构是一种数据的存储和操作的设定，操作可以是访问（ access ）和修改（ modification ）。它本身也自然限定出了一些特性，比如队列的FIFO等。算法则可以根据这些特性来运用合适的数据结构完成目标，所以算法和数据结构密不可分。
算法的意义
除了算法这类技术之外，计算机还有许许多多的其他技术，如体系结构、GUI、物件导向、网络技术等等。算法就是它们的基石，没有算法和它的效率，其他的追求也将无从谈起。
两种排序算法
对于排序问题，本节课提供了两种算法，分别是插入排序和合并排序。
插入排序是O(n*n)，合并排序是O(nlgn)
其中合并排序运用了递归调用和分治策略，这两个内容将分别在后续两节中介绍。
伪代码分别如下：
插入排序
合并排序
