设序列长度为n,在最坏的情况下,时间复杂度为O(log2n)的算法是什么
来源:学生作业帮 编辑:作业帮 分类:数学作业 时间:2024/10/03 08:01:13
设序列长度为n,在最坏的情况下,时间复杂度为O(log2n)的算法是什么
二分法
二分法的基本思想如下:
假设数据是按升序排序的,对于给定值x,从序列的中间位置开始比较,如果当前位置值等于x,则查找成功;若x小于当前位置值,则在数列的前半段中查找;若x大于当前位置值则在数列的后半段中继续查找,直到找到为止.
由于是数组是预先排序好的,所以可以采用折半查询的方式,每次抛掉待查询部分的一半
这样,长度为N的数组,只需要log2N次查询即可,2是对数的底.
例如,长度为7的数组,最多只需要3次就可以找到
O(log2n)只是表示是log2N同一数量级,因为有个取整的问题,而且也有可能在查询过程中就已经找到(也就是某个折半查询点正好是待查询数据),这样O(log2n)就是一个上限
二分法的基本思想如下:
假设数据是按升序排序的,对于给定值x,从序列的中间位置开始比较,如果当前位置值等于x,则查找成功;若x小于当前位置值,则在数列的前半段中查找;若x大于当前位置值则在数列的后半段中继续查找,直到找到为止.
由于是数组是预先排序好的,所以可以采用折半查询的方式,每次抛掉待查询部分的一半
这样,长度为N的数组,只需要log2N次查询即可,2是对数的底.
例如,长度为7的数组,最多只需要3次就可以找到
O(log2n)只是表示是log2N同一数量级,因为有个取整的问题,而且也有可能在查询过程中就已经找到(也就是某个折半查询点正好是待查询数据),这样O(log2n)就是一个上限
串的模式匹配算法中的BRUTE FORCE算法在最好情况下的时间复杂度为什么是O(n+m)而不是O(m)?其中m是模式.
几道数据结构题1,将长度为n的单链表接在长度为m的单链表之后算法的空间复杂度为()A,O(1) B,O(n) C,O(m
已知长度为n的线性表A采用顺序存储结构,请写出一个时间复杂度为O(n)、空间复杂度为O(1)的算法,该算法可删除线性表中
若一个算法中的语句频度之和为T(n)=n+2nlogn,则算法的时间复杂度为?
有关时间复杂度的算法已知平面上N个点,使得在N个点组成的所有点对中,该店对间的距离最小.设计一个时间复杂度为0的算法.
若一个算法中的语句频度之和为T(n)=6n+3nlogn+n*n,则算法的时间复杂度为?
下面程序段的时间复杂度为_____.(n>1)
若一个算法中的语句频度之和为T(n)=1024n+4nlogn,则算法的时间复杂度为0(nlogn
对于长度为n 的线性表,在最坏情况下,下列各排序法所对应的比较次数中正确的是A)冒泡排序n/2
某算法的空间花费s(n)=100n*log2n+0.5*n1.1+2000*n+5000,其空间复杂度是多少?求解答及此
排序技术中 冒泡法和快速排序法的最坏情况下的比较次数是多少 其时间复杂度分别是多少
设计一个算法,计算数列2-4+6-8+10……±m的∑值并返回,要求时间复杂度为O(1).