Gallop search 用于在排序列表中搜索元素。你从索引0开始,然后是索引1、2、4、8、16等,直到你超过目标,然后在刚才找到的范围内再次搜索。
这个算法的时间复杂度是什么?它似乎是某种对数时间复杂度,但我无法确定具体是什么。
Gallop search 用于在排序列表中搜索元素。你从索引0开始,然后是索引1、2、4、8、16等,直到你超过目标,然后在刚才找到的范围内再次搜索。
这个算法的时间复杂度是什么?它似乎是某种对数时间复杂度,但我无法确定具体是什么。
T(n) = T(n/2) + O(logn)
= T(n/4) + c1log(n/2) + c2logn ((all logs are base 2.))
.
.
.
.
= O((logn)^2)
log(n)
次比较;随着时间的推移,你会做越来越少的比较...不过我不确定那是什么... - user541686log(n) + log(n) - log(2) + log(n) - log(3) ...
,是的,你的界限很好;谢谢! - user541686