（1）一个算法应该具有以下五个重要的特征： 1、有穷性（Finiteness） 2、确切性(Definiteness) 算法的每一步骤必须有确切的定义； 3、输入项(Input) 一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件； 4、输出项(Output) 一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的； 5、可行性(Effectiveness) 算法中执行的任何计算步都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成。（也称之为有效性） （2）算法原地工作的含义是指不需要任何额外的辅助空间 (x). 算法原地工作的含义是指不需要任何额外的辅助,算法所需要的辅助空间不随着问题的规模而变化，是一个确定的值。
(1) 折半查找与二元查找树的时间性能在最坏的情况下是相同的(x) 数列有序，树只有左孩子或只有右孩子，退化为线性表。
(2) 假设某算法的计算时间可用递推关系式T(n)=2T(n/2)+n表示，则该算法的时间复杂度为（） O(n*logn)
T(n)= 2^k*(T(n/(2^k)))+2^(k-1)*n/(2^(k-1))+2^(k-2)*n/(2^(k-2))+ ··· +2^0*n/(2^0)) = 2^k*(T(n/(2^k)))+k*n 令2^k = n,则k = log(n) (以2为底) T(n)= n*T(1)+n*log(n)<= c*n*log(n) (c为常数） 所以是O(n*logn)P: 能在多项式时间内解决的问题 NP: 不能在多项式时间内解决或不确定能不能在多项式时间内解决，但能在多项式时间验证的问题 NPC: NP完全问题，所有NP问题在多项式时间内都能约化(Reducibility)到它的NP问题 ，即解决了此NPC问题，所有NP问题也都得到解决。NP ——> NP属于NPC NP hard: NP难问题， 所有NP问题在多项式时间内都能约化(Reducibility)到它的问题(不一定是NP问题)。NP ——> NP hard
元素的移动次数与关键字的初始排列次序无关的是：基数排序
元素的比较次数与初始序列无关是：选择排序
算法的时间复杂度与初始序列无关的是：选择排序
排序算法的稳定性
不稳定：快选堆希稳 定 ： 插冒归基与数据有序与否的关系：
与数据排序无关的有： 基选归堆
直接插入排序是数据越有序越快，最快时间复杂度可达到O(n) .选择排序无论何时都是O（n^2）快速排序越有序越慢基于比较的排序算法的平均时间复杂度最少为？
1、基于比较的排序算法有：（1）直接插入排序；（2）冒泡排序；（3）简单选择排序；（4）希尔排序；（5）快速排序；（6）堆排序；（7）归并排序。 2、基数排序、桶排序都属于分配式排序，且都是稳定排序算法。
不能低于O(NlogN) N个数有N!个可能的排列情况，也就是说基于比较的排序算法的判定树有N!个叶子结点，比较次数至少为log(N!)=O(NlogN)。
总结： 堆排序最坏情况下比较次数为 O(nlog2n) ， 快速排序、简单插入排序、冒泡排序最坏情况下比较次数为 n(n-1)/2 。 1.外部排序 指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。 一般用归并排序, 空间复杂度是O（n）。
2.初始序列有序时，快速排序效率最低。
3.折半查找属于随机访问特性 链表不行
折半查找表必须有序,表可以顺序方式存储,也可以链表方式存储（x）4.拓扑排序 http://blog.csdn.net/lisonglisonglisong/article/details/45543451
在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。 该序列必须满足下面两个条件：
每个顶点出现且只出现一次。若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。有向无环图（DAG）才有拓扑排序，非DAG图没有拓扑排序一说。
通常，一个有向无环图可以有一个或多个拓扑排序序列。
拓扑排序通常用来“排序”具有依赖关系的任务。
拓扑排序还可以采用 深度优先搜索（DFS）的思想来实现
题目： 1) 在用邻接表表示图时，拓扑排序算法时间复杂度为 o(n+e);
分块查找
数据分成若干块 每块内数据不必有序,但块间必须有序 每块内最大(或最小)的数据组成索引块
