3

bisectライブラリを使用してリストにソート挿入するのにかかる時間を監視する簡単なテストを実行しています

import numpy as np
import bisect

def get_time(N):
    myl = []
    a = time.time()
    for i in np.arange(N):
        bisect.insort_left(myl, random.randint(0,1000000) )
    b = time.time()
    return (b-a)

だから私はこれを次のように呼び出します：

t_dict = {}
for N in [1000,5000,10000,50000,100000,200000,300000,400000,500000]:
    t_dict[N] = get_time(N)

結果をプロットします。

ここに画像の説明を入力

insort私はそれが最大になると推測/望んでいたでしょうO(nlog(n))。ドキュメントから、次のように書かれています。

「O(log n) 検索は、遅い O(n) 挿入ステップによって支配されることに注意してください。」

ここで何が欠けていますか？

編集：私は非常に明白なものを欠いていました。とにかく、SortedContainers パッケージの SortedList を使用して同じことで質問を更新したいと思います。

ここに画像の説明を入力

非常に速いもの！

4

1 に答える 1

7

bisectは O(logN) です。ただし、リストへの挿入は O(N) です。あなたはそれをN回行います。

bisect.insort_left()ドキュメントから：

O(log n) 検索は、遅い O(n) 挿入ステップによって支配されることに注意してください。

したがって、挿入は依然として O(N) であり、O(logN) の検索時間は (漸近的に言えば) それと比較して重要ではありません。したがって、全体として、時限テストには N 回 O(N) == O(N^2) の時間がかかります。

于 2016-05-02T09:15:59.477 に答える