刷题刷出新高度，偷偷领先！偷偷领先！偷偷领先！ 关注我们，悄悄成为最优秀的自己！
面试题
Java版常用查找算法复杂度
使用微信搜索喵呜刷题，轻松应对面试！
答案：
分析&回答
| 平均时间复杂度 | 最差查找时间 | 查找前提 | 前提时间复杂度 | 插入新值时间 | |
|---|---|---|---|---|---|
| 顺序查找 | O(n) | O(n) | 无序或有序队列 | 无 | O(1) |
| 二分查找 | O(㏒n) | O(㏒n) | 排序（有序数组） | O(n㏒n) | O(n) |
| 插值查找 | O(㏒(㏒n)) | O(㏒(㏒n)) | 排序 | O(n㏒n) | O(n) |
| 斐波那契查找 | O(㏒n) | O(㏒n) | 排序+斐波那契数列 | O(n㏒n) | O(n) |
| 二叉树查找 | O(㏒n) | O(n) | 创建二叉树 | O(n㏒n) | O(㏒n) |
| 2-3树(k在2-3之间） | O(logk n) | O(logk n) | 创建2-3树 | O(nlogk n) | O(logk n) |
| 红黑树 | O(㏒n) | O(2㏒n) | 创建红黑树 | O(n㏒n) | O(㏒n) |
| B树和B+树（m为阶数） | O(log m/2 n/2) | O(log m/2 n/2) | 创建B树和B+树 | O(nlog m n) | O(log m n) |
| 区块查找(b为块数） | O(㏒b +n/b) | O(㏒b +n/b) | 创建区块 | O(n㏒b) | O(㏒b) |
| 哈希查找(k为一格的链表长度） | O(1) | O(k) | 创建哈希表 | O(n) | O(1) |
反思&扩展
特别关注二分查找、二叉树查找、红黑树
通常把查找过程中对关键字的平均比较次数，也叫平均查找长度（ASL）作为衡量一个查找算法效率优劣的标准：
ASL=求和(p[i]*c[i])，(i=1~n)。P[i]找到第i个记录的概率，c[i]找到第i个记录进行比较的次数
顺序查找的思想：从表的一端开始，顺序扫描线性表，依次将扫描到的关键字和给定值k比较，若当前扫描的关键字与k相等，则查找成功，
若扫描结束后，任未发现关键字等于k的记录，则查找失败。
ASL1查找成功（求和）i/n,i=1~n.
ASL2查找失败n
创作类型：
原创
本文链接：Java版常用查找算法复杂度
版权声明：本站点所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。让学习像火箭一样快速，微信扫码，获取考试解析、体验刷题服务，开启你的学习加速器！
分享考题 
