二分查找时间复杂度分析
分析 二分 复杂度
2023-09-14 09:16:11 时间
主要还是从算法所占用的「时间」和「空间」两个维度去考量。
时间维度:是指执行当前算法所消耗的时间,我们通常用「时间复杂度」来描述。
空间维度:是指执行当前算法需要占用多少内存空间,我们通常用「空间复杂度」来描述。
二分查找分析:
二分查找每次排除掉一半的不适合值,所以对于N个元素的情况:
一次二分剩下:N/2
两次二分剩下:N/2/2 = n/4
三次二分查找剩下:N/2/2/2 = N/8
.....
M次二分剩下:n / (2^M)
在最坏情况下是在排除到只剩下最后一个值之后得到结果,即
N / (2^m) = 1
所以由上式可得:2^m = N
推出时间复杂度是以2为底的对数公式:
m = log2(N)
注意:m为查找次数, N为元素个数.
例如:求0-10000个元素中最多几次查找到73?
m = log2(10000)
m = 13次
相关文章
- 【说站】python二分查找的原理分析
- [答疑]如果把准备结婚作为一个项目,应该怎样开展需求分析
- 2023年机器学习趋势分析
- CTF-流量分析总结
- APP性能测评分析
- 【Linux 内核 内存管理】munmap 系统调用源码分析 ② ( do_munmap 函数执行流程 | do_munmap 函数源码 )
- 使用ELK采集和分析docker日志
- linux引导系统的方法分析
- 分析Linux系统:以工具为辅助(linux系统分析工具)
- 分析Redis持久化技术及其优势(redis持久化方式)
- Linux分析系统日志:从入门到精通(linux分析系统日志)
- 分析探究Redis妙不可言的设计原理(redis设计源码)
- Oracle FM FX 飞速数据库管理和分析利器(oracle fm fx)
- javascript显示隐藏层比较不错的方法分析
- JS继承实例分析
- JavaScript私有成员分析
- Android颜色编辑器的制作中遇到的问题分析
- C语言宏定义使用分析
- jqueryparent和parents的区别分析
- jQuery中DOM树操作之使用反向插入方法实例分析