Java中的数据结构

读书笔记

【MARK A W. 数据结构与算法分析: Java 语言描述[J]. 2008.】
1. 若存在正常数$c$和$n_0$使得当$N≥n_0$时$T（N）≤cf（N）$，则记为$T（N）=O（f（N））$；若存在正常数$c$和$n_0$使得当$N≥n_0$时$T（N）≥cg（N）$，则记为$T（N）=Ω（g（N））$；$T（N）=Θ（h（N））$当且仅当为$T（N）=O（h（N））$且$T（N）=Ω（h（N））$；如果$T（N）=O（p（N））$且$T（N）≠Θ（p（N））$则$T（N）=o（p（N））$。
2. 法则：
i）如果$T_1（N）=O（f（N））$且$T_2（N）=O（g（N））$，那么$T_1（N）+T_2（N）=O（f（N）+g（N））$；$T_1（N）*T_2（N）=O（f（N）*g（N））$
ii）如果$T（N）$是一个k次多项式，则$T（N）=Θ（N^k）$
iii）对任意常数$log^kN=O(N)$(它告诉我们对数增长缓慢)
3. 计算算法时间复杂度的法则为：一，for循环，一个for循环的运行时间至多是该for循环内部那些语句（包括测试）的运行时间乘以迭代次数；二，嵌套的for循环，从里到外分析这些循环；三，顺序语句，将各个语句的运行时间求和即可（这意味着其中最大值就是所得的运行时间）；四，if/else语句，对于if（condition） $S_1$ else $S_2$而言，其运行时间从不超过判断的运行时间再加上$S_1$和$S_2$的较长者。
4. 对数最长出现的规律可概括为下列一般法则：如果一个算法用常数时间$O(1)$将问题的大小消减为其一部分（通常是$1/2$），那么改算法就是$O（logN）$。另一方面，如果使用常数时间只是把时间减少一个常数的数量（如减少1），则这种算法就是$O（N）$的。
5. Iterator中的remove（）比collection的remove（）更高效。
6. 栈是限制插入和删除只能在一个位置上进行的表，因此有时栈又被叫做后进先出表（LIFO）。栈的第一种实现是使用单链表，通过在表的顶端插入实现push，通过删除顶端元素实现pop。另一种实现是基于数组，与每个栈相关联的是theArray和topOfStack，当将x压入栈中时，使topOfStack加1，然后置theArray[topOfStack]=x，出栈则反之。
7. 栈的许多应用中，有三个比较常见，分别为平衡符号，后缀表达式，中缀到后缀的转换。【注1】
8. 像栈一样，队列也是表。然而，使用队列时插入在一端进行而删除在另一端进行。队列也可以由数组或链表实现。
9. 使用队列的高效算法常见于图论中。
10. 树是N个节点和N-1条边的集合，其中一个节点叫做根。对于任意节点$n_i$，$n_i$的深度为从根到$n_i$的唯一路径的长。$n_i$的高是从$n_i$到一片树叶的最长路径的长。
11. 数有一种表达方法是通过表示数的第一儿子以及下一个兄弟。【注2】
12. 使二叉树（儿子数不多于两个）成为二叉查找树的性质是：对于数中每个节点x，其左子树所有项小于x，右子树所有项大于x。
13. 二叉树的删除操作的实现。【注3】
14. 假设所有的插入序列都是等可能的，则数所有节点的平均深度为$O（logN）$。
15. 一棵AVL树是其每个节点的左子树和右子树的高度最多差1的二叉查找树（更进一步扩展还有伸展树）。
16. 由于CPU运行时间与磁盘访问时间相比的巨大优势，在二叉树中一次成功查找需要$O（logN）$次磁盘访问，而在M叉树中，其高度降为$O（log_mN）$，则磁盘访问次数相应减少，B树应运而生，降为M的B树是一棵具有下列特征的树：数据项存储在树叶上；非叶节点存储直到M-1个关键字以指示搜索的方向（关键字i代表子树i+1中的最小的关键字）；树的根或者是一片树叶，或者其儿子树在2和M之间；除根外，所有非树叶节点的儿子数在[M/2]和M之间；所有的树叶都在相同的深度上并有[L/2]和L之间个数据项，L有其确定方式。
17. Java要求TreeSet和TreeMap支持基本的add，remove和contain操作以对数最坏的情形时间完成，因此，基本的实现方法就是平衡二叉查找树。
18. 散列表的实现常常叫做散列。散列是一种用于以常数平均时间执行插入、删除和查找的技术。散列函数理想情况下应该是计算简单，并且应该保证两个不同的关键字映射到不同的单元。
19. 定义散列表的装填因子λ为散列表中元素个数对该表大小的比。
20. 散列表根据解决冲突的不同有多种分类：分离链接法和开放定址法【注4】。其标准库中的实现即HashSet和HashMap。
21. 优化队列（堆）的一种实现为二叉堆（简称堆）：堆是一棵被完全填满的二叉树，有可能的例外是在底层，底层上的元素从左到右填入。这样的树称为完全二叉树。
22. 完全二叉树是非常有规律的，所以它可以用一个数组表示而不需要使用链，只要在数组中从上至下，从左至右的排布就可以了。
23. 堆在完全二叉树的基础上，还需满足另一个性质：任意节点都小于它的所有后裔。
24. 堆上的插入、删除等的实现（上滤、下滤）【注5】。堆的推广有：d-堆、左式堆、斜堆。
25. 二项队列不是一颗排序的树，而是排序的树的集合，称为森林。每一棵排序树都有约束，叫做二项树。
26. 内部排序的分类有：插入排序（直接插入排序、二分插入排序、希尔排序）；选择排序（简单选择排序、堆排序）；交换排序（冒泡排序、快速排序）；归并排序；基数排序。【注6】
27. 外部排序：处理数量很大的输入数据（一般都是太大装不进内存）类似Map-Reduce的思路。
28. 等价关系R是满足以下三个性质的关系：自反性，即对于所有的$a∈S$，$aRa$；对成型，即$aRb$当且仅当$bRa$；传递性，即$aRb$且$bRc$则$aRc$。
29. 图的表示：标准方法为邻接法。对于每个定点，我们使用一个表存放所有邻接的定点。
30. 对于无权图求最短路径：广度优先搜索，按层处理定点，距开始点最近的那些定点首先被求值，而最远的那些顶点最后被求值；深度优先搜索，对先序遍历的推广。【注7】
31. 对于有权图，解决单源最短路径问题的一般方法叫做Dijkstra算法，它是贪婪算法最好的例子，只要没有负值边，则算法总能正确工作。【注8】
32. 最小生成树：大体来说，一个无向图G的最小生成树就是由该图的那些连接G的所有顶点的边构成的树，且其总价值最低。最小生成树存在当且仅当G是连通的。
33. 最小生成树的实现算法：Prim算法，使其连续地一步步长成，在每一步，都要把下一个节点当做根并往上加边，这样也把相关联的顶点加到增长的树上；Kruskal算法，连续地按照最小的权选择变，并且当所选的边不产生圈时就把它作为所取定的边。【注9】
34. NP完全性。可以证明，计算机不可能解决碰巧发生的每一个问题。这些“不可能”解决的问题叫做“不可判定问题”，如停机问题。而NP类是在难度上逊于不可判定问题的类。NP代表非确定型多项式时间。在已知的属于NP的所有问题中，存在一个子集，叫做NP-完全问题，它包含了NP中最难的问题。NP-完全问题有一个性质，即NP中任一问题都能够以多项式时间归约成NP-完全问题。【注10】
35. 贪婪算法分阶段工作。在每一个阶段，可以认为所做决定是好的，而不考虑将来的后果。
36. 满树：所有节点要么是树叶，要么有两个儿子。如果字符都只放在树叶上，那么任何比特序列总能够毫不含糊地译码。这种编码方式得字符代码长度是否不同并不要紧，关键是只要没有字符代码是别的字符代码的前缀就行，这样一种编码叫做前缀码。而哈弗曼算法就是：算法对由树组成的森林进行，一棵树的权等于它的树叶的频率的和。任意选取最小权的两棵树$T_1$和$T_2$，并任意形成以$T_1$和$T_2$为子树的新树，将这样的过程进行C-1次。【注11】

【注1】http://blog.csdn.net/zlhy_/article/details/8518699
【注2】

class TreeNode{
    Object element；
    TreeNode firstChild；
    TreeNode nextSibling；
}

【注3】http://marcospring.iteye.com/blog/1623571
【注4】http://blog.csdn.net/jnu_simba/article/details/9632675
http://blog.csdn.net/jnu_simba/article/details/9664053
http://blog.csdn.net/jnu_simba/article/details/9668369
【注5】http://blog.csdn.net/xiahouzuoxin/article/details/8267076
【注6】http://www.cnblogs.com/liuling/p/2013-7-24-01.html
【注7】http://blog.csdn.net/andyelvis/article/details/1728378
【注8】http://blog.csdn.net/v_JULY_v/article/details/6096981
【注9】http://www.cnblogs.com/biyeymyhjob/archive/2012/07/30/2615542.html
【注10】http://www.cnblogs.com/Gavin_Liu/archive/2011/05/04/2012284.html
http://www.tuicool.com/articles/3uYbYvJ
【注11】http://www.cnblogs.com/junyuhuang/p/4127095.html