以二分查找方法从长度为n的线性有序表中查找一个元素时,时间复杂度

题目

以二分查找方法从长度为n的线性有序表中查找一个元素时,时间复杂度为()。

如果没有搜索结果或未解决您的问题,请直接 联系老师 获取答案。
相似问题和答案

第1题:

在长度为n的有序线性表中进行二分查找,所需要的比较次数为______。


正确答案:log2n
log2n 解析: 对于长度为n的有序线性表,在最坏情况下,二分查找只需要比较log2n次,而顺序查找需要比较n次。

第2题:

若对大小为N的有序顺序表进行顺序查找,当查找不成功时,平均查找长度为(59);当查找成功且表中仅有一个关键字等于欲查找的元素时,平均查找长度为(60)。

A.N

B.N+1

C.N/2

D.(N+1)/2


正确答案:A
解析:当查找不成功时,会查找至最后一个元素,故平均查找长度为N。

第3题:

采用二分查找方法查找长度为n的线性表时,每个元素的平均查找长度为()。

A、O(n2)

B、O(nlog2n)

C、O(n)

D、O(log2n)


参考答案:D

第4题:

顺序查找一个具有n个元素的线性表,二分查找一个具有n个元素的有序表,其时间复杂性为______。

A.O(n)

B.O(log2n)

C.O(n2)

D.O(nlog2n)


正确答案:B

第5题:

● 对 n 个元素的有序表 A[1..n]进行二分(折半)查找,则成功查找到表中的任意一个元素时,最多与A 中的 (39) 个元素进行比较。

(39)


正确答案:D

第6题:

利用折半查找方法在长度为n的有序表中查找一个元素的平均查找长度是()。

A.O(n2)

B.O(nlogn)

C.O(n)

D.O(logn)


参考答案:D

第7题:

对长度为n的有序线性表中进行二分查找,需要的比较次数为( )。


正确答案:log2n
log2n

第8题:

使用二分查找算法在一个有序序列中查找一个元素的时间复杂度为()

A.O(N)

B.O(logN)

C.O(N*N)

D.O(N*logN)


正确答案:B

第9题:

采用二分查找方法查找长度为n的线性表时,每个元素的平均查找长度为______。

A.O(log2n)

B.O(n)

C.O(nlog2n)

D.O(n2)


正确答案:A

第10题:

二分查找一个具有n个元素的有序表,其时间复杂度为______。

A.O(n)

B.O(n2)

C.O(log2n)

D.(nlog2n)


正确答案:C
解析:二分法中查找时间t与查找次数m呈比例关系,2m=n(n为极限查找个数),m=log2n,所以查找时间复杂度与log2n相关。