数据库的查找的复杂度怎样计算？

Question

如题所述

Answer 1

1、顺序查找：

（1）最好情况：要查找的第一个就是。时间复杂度为：O(1)

（2）最坏情况：最后一个是要查找的元素。时间复杂度未：O(n)

（3）平均情况下就是：（n+1）/2。

所以总的来说时间复杂度为：O(n)

2、二分查找：O(log2n)->log以2为底n的对数

解释：2^t = n; t = log(2)n;

3、插值查找：O(log(2)(log(2)n))->log以2为底的（log以2为底的n的对数）的对数

4、斐波那契查找：O(log2n)->log以2为底n的对数

5、树表查找：

（1）二叉树：O(log2n)~O(n)之间

（2）红黑树：O(lgn)

（3）B和B+树：O(log2n)

6、分块查找：O(log2n)~O(n)之间

7、哈希查找：O(1)