21-Day3.md

第三次课程小结

复杂度记号

O--表示时间复杂度，给出算法最坏情况；

排序算法

排序

复杂度 O(1/n!)，最坏可能是程序不结束

expected running time；

worst-case running time

快速排序

期望 O(nlog(n))

时间复杂度O（$n^2$）

伪代码：

对比：

桶排序

Sort on least significant digit, and then the 2nd

decision trees

时间考虑，一般将排序个数与桶的个数取成一样的

数据结构

基本定义

key value 数据对象（object）

存储的结构：1.sorted array 2.sorted linked lists(有头)

sorted arrays

插入数据：遍历数据（O(log(n))）折半查找、

二元搜索树

node、key，children（left/right）,parent,descendant,NIL

NIL相当于打出来；

实例：Fast Search/insert/delete

1.插入4.5

2.删除2

3.删除

如果是叶子节点，就直接删除（case1）；如果3只有一个子节点，move that up（case2）

如果是有两个节点，就比较复杂了如图（case3）

考虑3.1的不同情况同case1，2，3；

3.1有两个children是不会发生的，因为若3.1有两个节点，它就不符合immediate successor的要求了。

4.树如果是平衡的，最少O(log(n)），但是也存在最坏情况O(n)

上述二元查找树存在height比较大的可能

5.改善二元查找树：

方法一：旋转

方法二：proxy for balance

红黑树：自平衡

（其实就是对于二元的优化）

实现了旋转，能够自平衡，max height=2log(n+1)O(logn)

234树

能够实现完全的平衡