二分法的时间复杂度（时间复杂度和排序方法）
本文目录
- 时间复杂度和排序方法
- 二分法的时间复杂度为O（log2n）是什么意思
- 给定a,用二分法设计出求a^n的算法该算法的时间复杂度是每次分解的子问题是几个，子问题的规模是
- 二分法思路总结
- 二分查找的平均查找长度是多少
时间复杂度和排序方法
一个算法流程中 ， 常熟操作数量的指标， 这个指标叫做 O， 如果常熟的操作数量表达式中只要高阶项，不要低阶项， 也不要高阶项的系数，剩下的部分记为(fn), 那么时间复杂度就是O（fn）
一种最简单的方法是循环：
另一种方法是采用的二分法：
注意因为这是一个有序的数组， 所以我们可以先分一半, 然后比较我们要寻找的数字是是在左边的数组还是右边的数组，如果在左边将左边的数组一分为二， 然后继续划分。
第一种方法的时间复杂度是O(n), 第二种方法的时间复杂度是 O(logN)可以看出对于一个有序数组数量比较多的时候，二分法确实比较优秀一点。
第一种方法是直接两个数组分别循环找到其中的相同部分。 时间复杂度是 O(n*m)
第二种方法是：
对arr1数组进行循环， 然后在arr2中用二分去查找， 时间复杂度是O(n*logm)
第三种方法是 ， 如果左边数组比右边的数组小的话 就将左边的数组进行移动 ， 如果左边比右边大的话 ， 就将右边的数组进行移动 ， 如果两个相等的话就共同移动。其中的时间复杂度是O(n+m); 加上continue之后速度快了很多。
介绍完时间复杂度之后我们来看看几种排序方法。
所谓的冒泡排序就是先将最后一位固定最大的或者是最小的，然后取固定到倒数第二位中去固定， 我们如果对他进行使用冒泡从小到大开始排序的话应该怎么做呢？
首先排从第一个数字开始排序， 如果当前数字比下一个数字小或者相等的话，那么指针后移，在继续比较下一位，如果是当前数字大于下一位的话就会发生交换，然后指针向后移动。直到最大数字成为最后一位。
整个的时间复杂度是n-1+ n-2+...1
下面介绍一下对数器，所谓的对数器就用你所知道的简单的算法去验证下当前缩写算法的正确性。
我们平时写的算法可以用对数器来验证下
插入算法的精髓是，外部循环保证从1 的时候， 左边的数组是有序的， 如果是左边的数组没有顺序的，就内部循环发生交换， 比如说我们现在有一个数组是let arr = ，我们要保证他从小到大进行排序
外部循环从1开始， 左边的数组是 , 然后还是内部循环进行调序， 以此类推，最后的时间复杂度是2+3+4+...n-1
二分法的时间复杂度为O（log2n）是什么意思
二分法的基本思想如下：
假设数据是按升序排序的，对于给定值x，从序列的中间位置开始比较，如果当前位置值等于x，则查找成功；若x小于当前位置值，则在数列的前半段中查找；若x大于当前位置值则在数列的后半段中继续查找，直到找到为止。
由于是数组是预先排序好的，所以可以采用折半查询的方式，每次抛掉待查询部分的一半
这样，长度为N的数组，只需要log2N次查询即可，2是对数的底。
例如，长度为7的数组，最多只需要3次就可以找到
O(log2n)只是表示是log2N同一数量级，因为有个取整的问题，而且也有可能在查询过程中就已经找到（也就是某个折半查询点正好是待查询数据），这样O(log2n)就是一个上限
给定a,用二分法设计出求a^n的算法该算法的时间复杂度是每次分解的子问题是几个，子问题的规模是
int pow（int a， int n）
{
if (a == 0 || a == 1 || n == 1)
return a;
//n为了规整奇数时的余数
return a * pow(a, n / 2) * pow(a, （n - 1）/ 2);
}
时间复杂度为O(n)。每次将问题分解为2个，子问题的规模为n/2
二分法思路总结
二分的思想的挺简单的，一开始觉得要考虑很多边界情况。但其实不然，考虑这些边界情况并不会改善算法的时间复杂度。
深刻体会，对于计算机来说，少计算一次两次有什么区别呢。真正影响到执行时间的是内部if，else语句的出口。以及时间复杂度，是一种数量级的增长，而不是一次两次。
如果一定要用if else，那么看是否能用？：表达式代替。
首先二分法的思想
它是一种分治的思想。适用于相对有序的数组。初始化指针在数组的开头和结尾，然后得到中间数，进行比较，移动头尾指针，进行一半的取舍。
普通版的二分查找
给出 arr= ，找到数组中是否存在7，找到则并返回下标，找不到则返回-1
进阶版二分查找
例题：给出非递减排序数组的部分翻转数组，找出其最小元素
为什么使用二分
给出的条件是一个相对有序的数组并且因为当数据量大的时候，遍历整个数组，极不友好。也不够高级。
当找到的mid》left，则最小数一定在mid的右侧，当mid《left，最小数一定在mid的左侧（或者是mid）。最后我们会遍历到一个单调增的区域，这个时候直接拿left的值即可，不需要在进行二分了。
事件复杂度：O(lgn)
空间复杂度：O(1)
这个算法很巧妙的避开了类似这种找到mid（1）和left（1）相同的局面。算法中直接left++，再进行一次计算。
算法好难啊啊
继续加油吧！
二分查找的平均查找长度是多少
以二分查找方法从长度为10的有序表中查找一个元素时，平均查找长度为4。
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
二分查找的时间复杂度是O（2为底的log(n)），也就是说它的平均查找长度只和该有序表的长度有关，当长度为10时，平均查找长度为log10（2为底），其》3，《4，所以平均查找长度为4次。
扩展资料：
二分查找的查找过程：
首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。
重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
更多文章：
学后端开发的十大忠告（初学Java并且有志于后端开发的同学需要关注什么）
2025年11月28日 05:45
应届毕业生简历模板word版本免费（简历模板word个人简历范本五篇）
2025年9月17日 08:00
2025年5月30日 17:45
2026年5月24日 03:45
background 属性（CSS--background系列属性）
2026年2月27日 22:30
this is me对不对（她是我，用英语She is me!对吗）
2025年6月6日 18:15
2026年5月3日 04:45
2025年6月8日 12:30
2026年1月11日 05:15
2025年11月17日 15:00
2026年7月12日 19:45
queue up怎么读音发音英语（queue up是什么意思及用法）
2026年2月2日 03:00
css留言框右边滚动滑条（CSS样式如何设置滚动条的内边距）
2026年7月10日 12:45
2025年10月1日 02:15
alert属于js吗（关闭js的alert对话框后执行的是什么操作页面有没有被刷新）
2026年3月28日 10:30
2026年7月1日 05:30
2025年9月13日 23:15
2025年10月8日 08:15
2025年7月22日 16:45
marginnote3免费版（marginnote3试用到期后还能看文档吗）
2025年11月2日 05:30
