【算法】二分法 ① ( 二分法基本原理简介 | 二分法与哈希表对比 | 常见算法对应的时间复杂度 )

2023-03-30 18:56:25 浏览数 (1)

文章目录

  • 一、二分法基本原理简介
    • 1、二分法与哈希表对比
    • 2、二分法具体步骤
  • 二、常见算法对应的时间复杂度

一、二分法基本原理简介

二分法算法 是 基于 数组 数据结构 的 ;

数组 中的元素 是 已经 排序好的 , 由于 元素 是有序的 , 因此在 查询目标值 的时候 , 可以更加高效 的查询 其所在数组的索引 ;

1、二分法与哈希表对比

哈希表时间复杂度 : 如果将所有元素 放在 哈希表 中 , 从 哈希表 中查询某个元素是否存在 , 其 时间复杂度为

O(1)

, 使用哈希表的前提是 所有的数据 都要读取到内存中 ;

哈希表的缺陷 : 如果 数组集合 的元素数量很大 , 如几十万个元素 , 则无法将其完整的读取到内存中 , 此时就无法使用哈希表进行查询了 ;

二分法 与 哈希表法 对比 :

  • 算法灵活性 : 使用二分法 查询数组中的数据 , 数组的数据不仅仅局限于内存中 , 可以 存放在硬盘 , 网络 等介质中 , 如 : 存放在硬盘中 , 甚至可以存放在 不同设备 的 多块硬盘 中 ;
  • 时间复杂度 : 二分法 的 时间复杂度 是
O(log n)

, 其比 哈希表 HashSet 的 时间复杂度

O(1)

要高 , 但是 二分法 实现非常灵活 ;

2、二分法具体步骤

二分法步骤 :

  • 首先 , 确定 数组 的查找区间 , 一般是 从第 0 个元素 到 最后一个元素 , 开始元素索引设置为 start 变量 , 结束元素索引设置为 end 变量 ;
  • 然后 , 找到 start 索引 和 end 索引 的中间值 索引 , 将 该中间值索引的元素 与 查找目标值 进行对比 ;
    • 如果 中心元素 = 目标值 , 直接返回该索引值 ;
    • 如果 中心元素 < 目标值 , 则需要去 该查找区间的 右侧继续查找 , 经过该操作查找区间被缩小了一半 ;
    • 如果 中心元素 > 目标值 , 则需要去 该查找区间的 左侧继续查找 , 经过该操作查找区间被缩小了一半 ;
  • 最后 , 如果上述遍历出现 start >= end , 则说明该数组中没有目标值 ;

二、常见算法对应的时间复杂度

常见算法对应的时间复杂度 : 时间复杂度从小到大进行排序 ;

O(1)

: 位运算 , 哈希表查询

O(log n)

: 二分法 , 快速幂算法 , 辗转相除法 , 倍增法 ;

O(n)

: 枚举法 , 单调栈算法 , 双指针算法 ;

O(n log n)

: 快速排序 , 归并排序 , 堆排序 ;

O(n^2)

: 枚举法 , 动态规划 ;

O(n^3)

: 枚举法 , 动态规划 ;

O(2^n)

: 组合相关的搜索问题 ;

O(n!)

: 排列相关的搜索问题 ;

算法示例 : 判定数组中是否存在某个 目标值 元素 , 如何进行优化 ;

  • 最差算法 : 如果每次都 扫描一遍数组 , 查询目标值是否存在 , 该操作的 时间复杂度是
O(n)

, 也就是数组如果有

n

个元素 , 则最坏情况需要遍历

n

次才能得到结果 ;

  • 优化算法 : 对数组进行 排序 , 然后使用 二分法 进行查找 , 则每次查询的 时间复杂度是
O(log n)

;

  • 最优算法 : 将数组元素存入 哈希表 , 每次查询的 时间复杂度是
O(1)
排序 数据 数组 算法 索引

0 人点赞