二分法时间复杂度计算
计算 时间 复杂度 二分法
2023-09-14 09:11:22 时间
https://blog.csdn.net/heihu_malice7/article/details/90042912
1.例如二分查找
总共有n个元素,每次查找的区间大小就是n,n/2,n/4,…,n/2^k(接下来操作元素的剩余个数),其中k就是循环的次数。
//k在递归的时候也可以说是递归的深度
由于n/2^k取整后>=1,即令n/2^k=1,
可得k=log2n,(是以2为底,n的对数),所以时间复杂度可以表示O()=O(logn)。
总结一下就是:
二分法的关键思想是 假设该数组的长度是N那么二分后是N/2,再二分后是N/4……直到二分到1结束(当然这是属于最坏的情况了,即每次找到的那个中点数都不是我们要找的),那么二分的次数就是基本语句执行的次数,于是我们可以设次数为x,N*(1/2)^x=1;则x=logn,底数是2。
相关文章
- imba97的工具箱 - 时间计算
- 算法时间复杂度的计算
- 【面试高频题】难度 3/5,近期面试原题(简单计算几何运用)
- Python应用之计算阶乘
- 1行Python代码,计算程序的运行时间,也可以用在算法和接口的调优上
- 隐私计算在医疗行业的应用
- MySQL时间戳计算:快速捷径实现效率升级(mysql时间戳计算)
- MySQL中处理时间的技巧:以秒为单位计算(mysql时间秒数)
- 计算Oracle中时间差值的技巧(oracle时间差值)
- MySQL时间计算技巧(mysql的时间运算)
- 利用Oracle时间计算函数提升效率(oracle时间计算函数)
- C语言编程实现Linux下的时间间隔计算(linuxc时间间隔)
- 如何使用count函数在MySQL中计算数据(count在mysql中)
- 云计算时代,Oracle云服务平台开启新纪元(oracle云服务平台)
- PHP中使用微秒计算脚本执行时间例子