搞定算法与数据结构 (01):二分查找法的时间复杂度与空间复杂度分析

作者: 王炳明 分类: 算法与数据结构 发布时间: 2021-10-02 14:38 热度:1,799

查看完整目录 –>《搞定算法与数据结构


给定问题

给定一个包含有 N 个元素的有序数组,如何快速确定某个值是否在该数组中。

注意题目中的数组,一定要是有序的,才能使用本文的二分法查找。

查找逻辑

现有一个目标值为 v 的数值,要判断 v 是否在长度为 n 的数组 L 之中。

可以把原数组切成两个大小相等的子区间,由于数组是有序的,因此若 v < L[n/2],则表示 v 不会在 L[n/2:n] 的区间里,接下来只要再把 L[0:n/2] 切成两个大小相等的子区间,然后拿 L[n/4] 比较大小,确实在哪个区间里,以此类推,直到子区间元素只有一个时,结束。

单调数组上的二分查找算法

时间复杂度

时间复杂度,有最好的时间复杂度,最坏的时间复杂度,平均时间复杂度。

对于二分查找法来说,我们假设我们最多需要 x 次的二分数组才能确定是否在数组中,用 F(n) 表示

第一次二分数组,公式可以表示为

F(n) = 1 + F(n/2)

根据递归,再往下推算第二次二分数组

F(n) = 1 + F(n/2)
       = 1 + (1 + F(n/4)
       = 2 + F(n/4)

经过 x 次后,每个子区间的元素个数为 1,由于公式可以推算成如下

F(n) = x + F(n/(2^x))

因此,F(n/(2^x)) = F(1),也即 n/(2^x) = 1

经过计算可得: x=log_2^n

也就是说,最多经过 log_2^n + 1 后,就可以知道 v 在不在指定的数组中。

由于时间复杂度表示的是 代码执行时间随数据规模增长的变化趋势 ,因此计算复杂度公式中的低阶、常量、系数三部分都不会左右增长趋势,都可以直接忽略,因此最终二分法的时间复杂度是

log_2^n + 1 = log_2^{10} * log_{10}^n+1 => O(log^n)

空间复杂度

二分法主要考察的点在于时间复杂度的计算,而对于空间复杂度,会根据代码实现方法的不同而有所不同。

一般来说,代码有两种实现方法:

  1. 递归:由于每一次递归调用,都要额外申请栈空间,子级的栈空间是父级栈空间的一半,计算方法与上面计算时间复杂度相同,因此空间复杂度为 O(log^n)
  2. 迭代:除了原数组本身会占用 n 个元素的内存空间外,其他不会再额外申请内存空间,因此空间复杂度为 O(n)

文章有帮助,请作者喝杯咖啡?

发表评论