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

1対1最短路問題に対しても同様のプロットした。



全米(2400万点、5800万枝)だけでの計算量曲線なのに、思ったよりも実験結果とマッチしている。やはり実験的な性能が必要な場合でも計算量によるものが非常に重要である事を示している。それと同時にあるところまで行き着いたアルゴリズムは計算機の特性を考慮して改善するべきであると思う。log(n) を loglog(n) にするなどの改悪に近いものは理論的にも美しくないと感じるし、実装するとしてもうれしくない。