有一个长度为n的顺序存储的有序线性表,要在此线性表中利用对分查找算法查找某元素x,试分析在等概率的情况下该算法的时间复杂

有一个长度为n的顺序存储的有序线性表,要在此线性表中利用对分查找算法查找某元素x,试分析在等概率的情况下该算法的时间复杂度.(要有步骤)
srcbi 1年前 已收到1个回答 举报

玩笑开大了 春芽

共回答了15个问题采纳率:86.7% 举报

每次去掉一半,设最坏用k次
则2^k = n,于是k = log2n,就是时间复杂度的O(log2n)

1年前

8
可能相似的问题
Copyright © 2024 YULUCN.COM - 雨露学习互助 - 16 q. 2.865 s. - webmaster@yulucn.com