11

リスト内の要素を検索する場合、どちらが高速かを理解するためのコードを作成しました。それは二等分であることが判明しました。私が理解していないのは、バイセクトアルゴリズムの複雑さであり、Van Emde Boasツリーを使用していますか？

#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

4

2 に答える 2

23

二分探索を使用するため、O（log n）になります。

于 2012-08-18T21:08:44.390 に答える
1

右、二分探索があります。O（Ln（n））が答えです。

しかし、あなたのリストはすべてのケースをテストするのに十分ではありません。すべてのアルゴリズムは異なる実行時間を要した可能性がありますが、すべての場合でこれらをテストする必要があります。十分な数のリストでテストすると、正しい結果が得られます。

納得していただければ幸いです。

于 2012-08-18T22:09:58.240 に答える