|
最坏情况下 |
|
平均情况下 |
|
|
查找 |
插入 |
查找 |
插入 |
顺序查找（无序链表） |
N |
N |
N/2 |
N |
二分查找（有序数组） |
log2n |
2N |
log2n |
N |
二叉树查找 |
N |
N |
1.39lgN |
1.39lgN |
2-3树查找（红黑树） |
2lgN |
2lgN |
1.00lgN |
1.00lgN |
拉链法（链表数组） |
<lgN |
<lgN |
N/2(M) |
N/m |
线性检测法（并行数组） |
clgN |
clgN |
<1.5 |
<2.5 |