プロット時に奇妙な結果が出る（Cormen）Red-black tree insert

Question

CormenのIntroduction to Algorithmsの擬似コードに従ってPythonのRed-Blackツリーに実装しました。

insertが実際にO(logn)であることを自分の目で見たいので、n=1, 10, 20, ..., 5000というノードをツリーに挿入するのにかかる時間をプロットしました。

x - 軸がnあるとy - 軸はそれがミリ秒にかかった時間です：

これが結果です。

私にとって、グラフは対数より線形に見えます。それを何が説明できますか？

Answer 1

いいえ、グラフには、n要素をツリーに挿入するためのコストの測定値が表示されます。ここで、x軸は挿入した要素の数であり、y軸は合計時間です。

n個の要素をツリーに挿入するのに必要な時間を合計する関数を呼び出してみましょう。f(n)

その後、我々はfがどのように見えるかの大まかなアイデアを得ることができます。

f(1) < k*log(1)     for some constant k. 

f(2) < k*log(1) + k*log(2)  for some constant k 

... 

f(n) < k * [log(1) + log(2) + ... + log(n)] for some constant k. 

によりログがどのように機能するかには、我々はlog(1) + ... + log(n)を折りたたむことができます。

f(n) < k * [log(1*2*3*...*n)]  for some constant k 

f(n) < k * log(n!)    for some constant k 

我々はウィキペディアを見てみることができますどのlog(n!)のように見えるのgraphを参照してください。記事のグラフを見てください。あなたにはよく知られているはずです。:)です

は

、私はあなたが事故でこれをやったと思う：

for n in (5000, 50000, 500000): 
    startTime = ... 
    ## .. make a fresh tree 
    ## insert n elements into the tree 
    stopTime = ... 
    ## record the tuple (n, stopTime - startTime) for plotting 

むしろ木に一つの要素を挿入する個々のコストよりも、サイズnのツリーを構築するための総時間をプロットしましたサイズのN：

for n in range(50000): 
    startTime = ... 
    ## insert an element into the tree 
    stopTime = ... 
    ## record the tuple (n, stopTime - startTime) for plotting 

---

クリス・テイラーは、あなたがf(n)/nをプロットすると、ログのグラフが表示されますことをコメントで指摘しています。 log(n!)とかなり近似しているのはn*log(n)です（Wikipediaのページを参照）。

f(n) < k * log(n!)    for some constant k 

をしてもらう：だから私たちは私たちのバウンドに戻ることができ

f(n) < k * n * log(n)    for some constant k 

をそして今、あなたがnでf(n)を分割する場合は、あなたのグラフはによって上記有界されることを確認するために簡単なはずです対数の形。

Answer 2

5000は、実際に対数を「見る」ためには十分ではないかもしれません - 試行は50000と500000で実行してください。 2秒20秒かかる場合は、線形の成長が理にかなっています。それより少ない場合は、対数が意味をなさない。ほとんどの「シンプルな」関数で十分にズームインすると、結果はかなり線形に見えます。

Answer 3

「なぜ」の質問には常にいくつかの推測があります。私はあなたが見ているジャンプがシステムメモリ管理に関係していると思われます。継続的な成長のためにシステムがより大きなメモリ空間を割り当てなければならない場合、プログラム全体の処理を完了するのに所定の時間が追加されます。ノードに「ペイロード」フィールドを追加して、必要な記憶領域の量を増やし、私が正しい場合、ジャンプが頻繁に行われます。

いいグラフです。