【算法】二分法 ① ( 二分法基本原理简介 | 二分法与哈希表对比 | 常见算法对应的时间复杂度 )
2023-06-13 09:18:07 时间
文章目录
一、二分法基本原理简介
二分法算法 是 基于 数组 数据结构 的 ;
数组 中的元素 是 已经 排序好的 , 由于 元素 是有序的 , 因此在 查询目标值 的时候 , 可以更加高效 的查询 其所在数组的索引 ;
1、二分法与哈希表对比
哈希表时间复杂度 : 如果将所有元素 放在 哈希表 中 , 从 哈希表 中查询某个元素是否存在 , 其 时间复杂度为
, 使用哈希表的前提是 所有的数据 都要读取到内存中 ;
哈希表的缺陷 : 如果 数组集合 的元素数量很大 , 如几十万个元素 , 则无法将其完整的读取到内存中 , 此时就无法使用哈希表进行查询了 ;
二分法 与 哈希表法 对比 :
- 算法灵活性 : 使用二分法 查询数组中的数据 , 数组的数据不仅仅局限于内存中 , 可以 存放在硬盘 , 网络 等介质中 , 如 : 存放在硬盘中 , 甚至可以存放在 不同设备 的 多块硬盘 中 ;
- 时间复杂度 : 二分法 的 时间复杂度 是
, 其比 哈希表 HashSet 的 时间复杂度
要高 , 但是 二分法 实现非常灵活 ;
2、二分法具体步骤
二分法步骤 :
- 首先 , 确定 数组 的查找区间 , 一般是 从第 0 个元素 到 最后一个元素 , 开始元素索引设置为 start 变量 , 结束元素索引设置为 end 变量 ;
- 然后 , 找到 start 索引 和 end 索引 的中间值 索引 , 将 该中间值索引的元素 与 查找目标值 进行对比 ;
- 如果 中心元素 = 目标值 , 直接返回该索引值 ;
- 如果 中心元素 < 目标值 , 则需要去 该查找区间的 右侧继续查找 , 经过该操作查找区间被缩小了一半 ;
- 如果 中心元素 > 目标值 , 则需要去 该查找区间的 左侧继续查找 , 经过该操作查找区间被缩小了一半 ;
- 最后 , 如果上述遍历出现 start >= end , 则说明该数组中没有目标值 ;
二、常见算法对应的时间复杂度
常见算法对应的时间复杂度 : 时间复杂度从小到大进行排序 ;
: 位运算 , 哈希表查询
: 二分法 , 快速幂算法 , 辗转相除法 , 倍增法 ;
: 枚举法 , 单调栈算法 , 双指针算法 ;
: 快速排序 , 归并排序 , 堆排序 ;
: 枚举法 , 动态规划 ;
: 枚举法 , 动态规划 ;
: 组合相关的搜索问题 ;
: 排列相关的搜索问题 ;
算法示例 : 判定数组中是否存在某个 目标值 元素 , 如何进行优化 ;
- 最差算法 : 如果每次都 扫描一遍数组 , 查询目标值是否存在 , 该操作的 时间复杂度是
, 也就是数组如果有
个元素 , 则最坏情况需要遍历
次才能得到结果 ;
- 优化算法 : 对数组进行 排序 , 然后使用 二分法 进行查找 , 则每次查询的 时间复杂度是
;
- 最优算法 : 将数组元素存入 哈希表 , 每次查询的 时间复杂度是
相关文章
- 数据结构哈希表例题_数据结构哈希算法
- 检测模型改进—OHEM与Focal-Loss算法总结[通俗易懂]
- 算法时间复杂度的计算
- 关于hashlib哈希算法的一些个人笔记
- 一致性哈希算法的问题
- 一致性哈希算法及其实现
- BP算法详解_bp算法的基本思想
- pymemcached框架之一致性哈希算法实现
- 《异常检测——从经典算法到深度学习》6 基于重构概率的 VAE 异常检测
- 一致性哈希算法设计题,栽了
- Go 数据结构和算法篇(十四):哈希表、哈希函数、哈希冲突和哈希算法
- JS算法_知识点精讲
- 检索算法---顺序查找
- 用javascript分类刷leetcode-排序算法(图文视频讲解)
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-436 算法训练 正六边形
- 【Android UI】贝塞尔曲线 ⑥ ( 贝塞尔曲线递归算法原理 | 贝塞尔曲线递归算法实现 )
- Java数据结构和算法(十三)——哈希表详解编程语言
- 哈希算法生存状况报告
- 基于深度学习的人脸自动美妆与深度哈希算法
- Linux内核中的哈希算法详解(linux内核哈希)
- Linux哈希算法:安全、可靠的认证方式(linuxhash算法)
- 探索Oracle中的哈希算法使用技巧(oracle使用hash)
- 哈希结合Redis实现一致性哈希算法(基于redis一致性)
- 实现高可用的Redis集群哈希一致性算法(redis集群哈希算法)
- 算法Oracle11g中实现安全传输哈希算法(oracle11g哈希)
- Redis优化轻松挑战负载平衡算法(redis 负载算法)
- 谷歌推出有界负载的一致性哈希算法,解决服务器负载均衡问题
- 关于各种排列组合java算法实现方法
- python插入排序算法的实现代码
- c#哈希算法的实现方法及思路
- 堆排序算法(选择排序改进)