計算複雑性と実行時間 - その4

他の splib の結果もプロットしてみた。ここに benchmark 結果を載せたが、やはり fibonacci-heap の計算量と計算機上での実行時間の間には非常に大きな差がある。

DIKQ : Naitive-Dijkstra's algorithm
DIKH : 4-ary heap
DIKB : Dial's algorithm(1-level-buckets)
DIKD : double buckets
DIKF : Fibonacci-heap
mbp : multi-level bukcets