2016 - 2024

感恩一路有你

顺序表查找的时间复杂度 数组排序的最少时间复杂度O(nlog2n)怎么计算的?

浏览量:2851 时间:2021-03-11 13:55:47 作者:admin

数组排序的最少时间复杂度O(nlog2n)怎么计算的?

二分法的基本思想如下:假设数据按升序排序。对于给定的值x,从序列的中间位置开始。如果当前位置值等于x,则搜索成功;如果x小于当前位置值,则搜索在序列的前半部分;如果x大于当前位置值,则搜索在序列的后半部分继续,直到找到为止。因为数组是预先排序的,所以我们可以使用半查询的方法,每次都丢弃一半要查询的部分。这样,长度为n的数组只需要log2n查询,2是对数的基。例如,长度为7的数组最多只能找到三次。O(log2n)只表示它与log2n的数量级相同,因为存在舍入问题,也有可能是在查询过程中发现的(即半个查询点正好是要查询的数据),所以O(log2n)是一个上限

顺序表查找的时间复杂度 数组元素的地址是连续的吗 linkblockqueue多线程消费

版权声明:本文内容由互联网用户自发贡献,本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。