bisect算法的复杂度是多少?

问题描述

我编写了代码，以了解在搜索列表中的元素时哪个更快.事实证明是二等分的.我不明白什么是bisect算法的复杂性，它使用Van Emde Boas树吗?

I wrote code to understand which of them is faster when it comes to search an element in a list. It turns out to be bisect. What I do not understand is what is complexity of bisect algorithm and does it use Van Emde Boas tree?

#python inbuilt list search using 'in' took 0.0702499200317 secs

def mul3():
    a = [1, 2, 4, 5, 6, 7, 8, 10, 12, 42, 55, 65, 69, 95, 96, 101, 156, 199]
    for x in a:
        if x in a:
            print x, "True"
        else:
            print x, "False"

#using bisect took 0.0649611193601

def mul4():
    a = [1, 2, 4, 5, 6, 7, 8, 10, 12, 42, 55, 65, 69, 95, 96, 101, 156, 199]
    import bisect
    for x in a:
        locate = bisect.bisect_left(a, x)
        if locate == len(a) or a[locate] != x:
            print False
        print True

 #using binary search took 0.0651483638284


a = [1, 2, 4, 5, 6, 7, 8, 10, 12, 42, 55, 65, 69, 95, 96, 101, 156, 199]


for x in a:
    lo = 0
    hi = 18
    while lo < hi:
        mid = (lo+hi)//2
        midval = a[mid]
        if midval < x:
            lo = mid+1
        elif midval > x:
            hi = mid
        else:
            print True
            lo = hi

参考: http://docs.python.org/library/bisect.html

推荐答案

它使用二进制搜索，从而使其变为O(log n).

It uses binary search, which makes it O(log n).

这篇关于bisect算法的复杂度是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！