顺序查找算法的时间复杂度是多少吖？？
发布网友
发布时间：2022-04-22 13:33
共1个回答
热心网友
时间：2023-08-25 02:38
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)
