算法的概念就不必多讲了，这里要指出的是：一般情况下，我们讲算法是面向大数据量的，算法的优劣通常是由其执行的时间复杂度来决定的（当然实际中还包括编程复杂度、计算机资源限制等等）。

举个例子，对n个数据进行排序操作，算法1需2n2条指令，算法2需50nlgn条指令，若n=8，显然算法1更好，若n=1000000，假设计算机执行速度为109条指令/s，则

算法1需要时间              2*(106)2/109 = 2000s

算法2需要时间              50*106*lg106/109 = 100s

显然算法2的效率更高，一般在评价上述两算法时，肯定会认为算法2的时间复杂度更优，因为复杂度是f(n)的多项式大小，说白了就是：n趋于很大后，多项式的大小比较。

         分治法是算法中最常用的方法，以一个简单的排序例子说明，对n个数据排序的时间为T(n)，则对n/2个数据排序的时间为T(n/2)，把两个n/2序列合并到一起又需要时间n/2（最坏的情况是两序列逐个比较一遍），这样就可以得到

T(n) = 2T(n/2) + n/2

这就是分治法的基本模型，若一个算法问题可以用分治法来解决，那么它的时间复杂度常常可以用主定理来直接得出，下面就是大名鼎鼎的主定理：

         （主定理）设a>=1,b>1为常数，T(n)有递归式T(n) = a*T(n/b) + f(n)定义，则t(n) = nlogb a，

         实际中，为了尽量使每层划分均匀一点，会对输入数组进行一个随机化，可以证明，对于随机输入序列，QUICKSORT的期望复杂度为nlgn，证明过程要用到概率知识，推导蛮复杂的，这里不深究。

         通常会有这样一个理论，时间来不及时，可以用空间来换取时间，这在排序算法中也适用。前面讲的两种算法都是在原地排序，通过相互比较来得到结果，这种策略通常通过递归划分来实现，由主定理这种方法的复杂度为nlgn。那么，怎么在空间上做文章，不用相互比较，并在更短的时间内完成排序呢。

2.3.1计数排序

         思想很简单，对n个数排序，若n个数在1~m的范围内（m>>n），则大可以建立一个m长的数组，把n个数据按key值塞入数组中，然后遍历该数组，每个元素的位置应该就是该元素之前的元素个数+1，这样就能直接得到序列的排序。总时间应该就是n+m，一般我们取m=kn，所以该算法的复杂度为线性时间。

         明显，n很大时，这种方法很浪费存储。

2.3.2基数排序

         对整数而言，不管有多少位，没位上无非是0-9这十个数字中的一个，从低位开始（注意是低位开始），依次用该位上的数字来排序（这可以用计数排序），最后就能得到结果。

         很明显该算法的复杂度为n。

2.3.3桶排序

         思想是，把n个数据按规则（如10,20,30.。。这样一段段的）划分成一个个的桶，每个桶里的数据就非常小了，分别对它们排序，可以用已有的方法（如复杂度为klgk，k1+k2+。。。=n），最后把这一段段的拼接起来即可。

         这与后面要讲的hash散列的思想类似。

         可以证明出，及时划分桶后使用复杂度为k2的算法排序，总的排序复杂度的期望值仍能保持在线性时间内，关键就是证明E(sum（k2）) = n。

         很多时候，我们并不需要对整个序列排序，而仅是要找到其中第几大的元素。很容易联想到利用QUICKSORT的方法，随机选一个元素为基准，进行PARTITION，得到该基准数是第几个，若偏大，则在左序列中递归PARTITION；若偏小，则在右序列中递归PARTITION。

         最坏情况下，每次都得到的基准数都市子序列中的最后一个，那么总时间为n-1+n-2+n-3+…1，是n2复杂度，而期望的复杂度则只有n。

         最简单的中位数就是MAX,MIN，那就大可不比用上述方法，只要进行依次遍历比较即可得到，复杂度为n。

         学习了解了算法问题的一些基本概念，和研究方法。着重以排序算法为例，练习了算法问题的解决方法，并动手编写了相应的代码实现。

         对于其中期望复杂度的问题，即概率分析法的适用还不是很熟，以后加强。

---读《算法导论》3、4部分小结

很多问题都可归结为对一个集合的一系列操作，这些操作包括查询、插入、删除，支持这些操作的动态集合称为字典。另一些问题可能还需要支持更复杂的操作，为了支持这些操作，并且使得操作效率很高，以怎样的方式来组织这个集合就至关重要了，这就是数据结构所研究的内容。

         最容易想到的数据结构当然是把集合的所有数据组合一个序列，这种方式几乎不要额外添加任何枝节，很简单。我们常用到的栈和队列就是这种结构。

         栈是单出口的，采用先进后出的方式，在计算机系统中经常用到。

         队列是双出口的，采用先进先出的方式。

         这样的简单结构，注定它的查询复杂度大，为n。

         散列表是数组的扩展，其主要目的是对一个有零散元素构成的集合进行快速寻址。举例来讲，如果一个集合的key值是1,2,3…n，那么只需要建立一个数组即可对其中每个元素进行直接寻址。但若集合的key值是1,5,7,101,84,…怎么办呢？也建立一个数组，那么数组会很大，而其中真正存储元素的却很少，造成存储浪费。

         散列表正是解决这样的问题的。如上面的问题，还是建立一个数组表，但仅有m长，对每个key值，不是直接映射到表中，而是通过一个散列函数h计算后，再映射到表中。

         这时就可能发生这样的情况，两个key值不同的元素，被h计算后，映射到了表的同一位置。如共有n个元素，表长m，则定义装载因子a=n/m，若散列函数h对每个key值的映射都是独立的，那么平均来看，表的每个槽中有a个元素，若a>1，那么必然有些槽中会有碰撞。

         解决碰撞的最直接的方法就是列表，即把有碰撞的槽内的元素构成一个列表，很容易得出寻址一个元素需要的平均时间为1+a/2。真正证明还是需要用到概率的知识，稍复杂。

         其实还有很多其它方法，如数组，如后面要讲到的二叉树等等，散列的真正含义就在于把一个凌乱的集合先通过h归归类，然后每个类中的元素就少很多，可以用其它一些结构组织，以满足实际需求。

1.2.1散列函数

         散列表的优劣关键在于散列函数，首先看一下散列函数一定要满足的条件：对于每个key值，其散列结果不能超过表长。例如一个散列表长3，则设计一个最简单的散列函数为h(k)=k mod 3。

         散列函数应（近似地）满足简单一致散列的建设：每个关键字都等可能地被散列到m个槽中去，并与其它关键字散列到哪个槽中无关。这个条件一般很难被满足，因为你设计h时并不知道输入数据的概率分布。比如上述的h(k)，若输入数据是1,4,7,10…，那么所有数都会被散列到槽1中去。

         除法散列是一种简单的散列方法，其实就是上面的h(k)=k mod m，m的选择尽量为质数，且离2p不是很近。

         乘法散列法为 h(k) = floor(m*(kA mod 1))，0