二分法的时间复杂度为O(log2n)是什么意思
发布网友
发布时间：2022-04-24 03:44
共2个回答
热心网友
时间：2023-10-25 18:56
网页链接
你可以看看我的上面这个博客
由于二分查找每次查询都是从数组中间切开查询，所以每次查询，剩余的查询数为上一次的一半，从下表可以清晰的看出查询次数与剩余元素数量对应关系
表-查询次数及剩余数
第几次查询 剩余待查询元素数量
1 N/2
2 N/(2^2)
3 N/(2^3)
… …
K N/(2^K)
从上表可以看出N/(2^K)肯定是大于等于1，也就是N/(2^K)>=1，我们计算时间复杂度是按照最坏的情况进行计算，也就是是查到剩余最后一个数才查到我们想要的数据，也就是
N/(2^K)=1
=>N=2^K
=>K=log2N
所以二分查找的时间复杂度为O(log2N)
热心网友
时间：2023-10-25 18:56
二分查找基本思路是先确定该区间的中间点,然后比较,再一半中再找中间点比较……直到找到.设中间点总数：n,平均查找长度为(n+1)∕ n×㏒2﹙n＋1﹚ －1 ≈㏒2﹙n＋1﹚－1
在应用极限化简就是log2(n)
热心网友
时间：2023-10-25 18:56
网页链接
你可以看看我的上面这个博客
由于二分查找每次查询都是从数组中间切开查询，所以每次查询，剩余的查询数为上一次的一半，从下表可以清晰的看出查询次数与剩余元素数量对应关系
表-查询次数及剩余数
第几次查询 剩余待查询元素数量
1 N/2
2 N/(2^2)
3 N/(2^3)
… …
K N/(2^K)
从上表可以看出N/(2^K)肯定是大于等于1，也就是N/(2^K)>=1，我们计算时间复杂度是按照最坏的情况进行计算，也就是是查到剩余最后一个数才查到我们想要的数据，也就是
N/(2^K)=1
=>N=2^K
=>K=log2N
所以二分查找的时间复杂度为O(log2N)
热心网友
时间：2023-10-25 18:56
网页链接
你可以看看我的上面这个博客
由于二分查找每次查询都是从数组中间切开查询，所以每次查询，剩余的查询数为上一次的一半，从下表可以清晰的看出查询次数与剩余元素数量对应关系
表-查询次数及剩余数
第几次查询 剩余待查询元素数量
1 N/2
2 N/(2^2)
3 N/(2^3)
… …
K N/(2^K)
从上表可以看出N/(2^K)肯定是大于等于1，也就是N/(2^K)>=1，我们计算时间复杂度是按照最坏的情况进行计算，也就是是查到剩余最后一个数才查到我们想要的数据，也就是
N/(2^K)=1
=>N=2^K
=>K=log2N
所以二分查找的时间复杂度为O(log2N)
热心网友
时间：2023-10-25 18:56
二分查找基本思路是先确定该区间的中间点,然后比较,再一半中再找中间点比较……直到找到.设中间点总数：n,平均查找长度为(n+1)∕ n×㏒2﹙n＋1﹚ －1 ≈㏒2﹙n＋1﹚－1
在应用极限化简就是log2(n)
热心网友
时间：2023-10-25 18:56
二分查找基本思路是先确定该区间的中间点,然后比较,再一半中再找中间点比较……直到找到.设中间点总数：n,平均查找长度为(n+1)∕ n×㏒2﹙n＋1﹚ －1 ≈㏒2﹙n＋1﹚－1
在应用极限化简就是log2(n)
热心网友
时间：2023-10-25 18:56
网页链接
你可以看看我的上面这个博客
由于二分查找每次查询都是从数组中间切开查询，所以每次查询，剩余的查询数为上一次的一半，从下表可以清晰的看出查询次数与剩余元素数量对应关系
表-查询次数及剩余数
第几次查询 剩余待查询元素数量
1 N/2
2 N/(2^2)
3 N/(2^3)
… …
K N/(2^K)
从上表可以看出N/(2^K)肯定是大于等于1，也就是N/(2^K)>=1，我们计算时间复杂度是按照最坏的情况进行计算，也就是是查到剩余最后一个数才查到我们想要的数据，也就是
N/(2^K)=1
=>N=2^K
=>K=log2N
所以二分查找的时间复杂度为O(log2N)
热心网友
时间：2023-10-25 18:56
网页链接
你可以看看我的上面这个博客
由于二分查找每次查询都是从数组中间切开查询，所以每次查询，剩余的查询数为上一次的一半，从下表可以清晰的看出查询次数与剩余元素数量对应关系
表-查询次数及剩余数
第几次查询 剩余待查询元素数量
1 N/2
2 N/(2^2)
3 N/(2^3)
… …
K N/(2^K)
从上表可以看出N/(2^K)肯定是大于等于1，也就是N/(2^K)>=1，我们计算时间复杂度是按照最坏的情况进行计算，也就是是查到剩余最后一个数才查到我们想要的数据，也就是
N/(2^K)=1
=>N=2^K
=>K=log2N
所以二分查找的时间复杂度为O(log2N)
热心网友
时间：2023-10-25 18:56
二分查找基本思路是先确定该区间的中间点,然后比较,再一半中再找中间点比较……直到找到.设中间点总数：n,平均查找长度为(n+1)∕ n×㏒2﹙n＋1﹚ －1 ≈㏒2﹙n＋1﹚－1
在应用极限化简就是log2(n)
热心网友
时间：2023-10-25 18:56
二分查找基本思路是先确定该区间的中间点,然后比较,再一半中再找中间点比较……直到找到.设中间点总数：n,平均查找长度为(n+1)∕ n×㏒2﹙n＋1﹚ －1 ≈㏒2﹙n＋1﹚－1
在应用极限化简就是log2(n)
