全部博文（124）
分类： C/C++
2010-07-15 13:55:08
检索（查询）
|
静态检索 |
动态检索 |
Hash检索 |
|
顺序存储结构 |
随机存储结构 |
消除地址冲突： 1. 开放定址法 2. 拉链法 |
|
不适合做插入/删除操作 |
检索表在检索过程中动态生成，检索成功即返回，不成功则插入 | |
|
二分法检索 分块检索 |
二叉检索树 B+树 |
|
大规模数据（排序）
|
方法 |
平均时间复杂度 |
最坏时间复杂度 |
空间复杂度 |
改进 |
|
快排 |
O(nlogn) |
O(n2) |
O(1) |
|
|
堆排 |
O(nlogn) |
O(nlogn) |
O(1) |
|
|
二路归并 |
O(nlogn) |
O(nlogn) |
O(1) |
先用直接插入排序求得较长有序子序列，然后归并 |
数据量较大时为避免记录移动，可采用链式存储结构
——插入排序(直接插入/希尔排序) + 归并排序
难于在链表上实现的排序方法：——快排 + 堆排
2 强用链表存储，改进的方法为：
1. 建立关键字索引，对索引表排序，结束后花O(n)时间代价重排记录。
2. 引入整形数组t[]，t[i]=I；交换R[i]和R[j]的时候只交换t[i]和t[j]。结束后花O(n)时间按t中次序重排记录。
=======================================================================================
BloomFilter Bitmap 数据判重/集合求交集、节省内存 Couting BloomFilter 支持元素删除 d-left BloomFilter 支持负载均衡 n-bit BloomFilter Couting的简单扩展
|
堆 |
求小规模海量数据中前n大/小的值、中位数 |
最大堆 |
前n小 |
|
最小堆 |
前n大 | ||
|
双堆 |
中位数 |
|
索引 |
数据库系统/文件系统 |
B树 |
聚集索引与非聚集索引 |
|
B+树 |
