オーダー記法の伸び方：各計算量クラスが実際にいくらかかるか

あなたのデータ

二つのアルゴリズムを差し向かいで

定数とは、記法が捨ててしまうもの全部です。メモリ確保、キャッシュミス、一歩ごとの中身。片方に重い定数を与えて、それが効かなくなる地点を見てください。

このページはあなたのループを読みません。コードを読んで計算量を当てにいくのは、測定の衣をまとった当て推量です。ループは途中で抜けられますし、中のたった一つの呼び出しが本当の費用を隠すこともあり、再帰は見た目どおりに読めることのほうが少ない。クラスを選ぶのはあなたで、そこから先の計算は厳密です。

結果

このページの初期値では、逆転は 439 要素です。二百件のリストで「良いほうのクラス」に手を伸ばした人は、プログラムを遅くし、コードを難しくしただけです。記法は警告しません。記法が語るのは最終的にどうなるかであって、あなたに何が起きるかではないからです。

この大きさでの各クラス

最後の列こそ、じっと見る値打ちがあります。誰も頭の中に持っていない列だからです。線形の仕事は倍になる。二乗の仕事は四倍になる。指数の仕事は二乗される。すでに千要素あるところで入力を倍にすると、費用は二の千乗倍、つまり三百二桁の数になります。

階乗の悪さは、倍にすることとは別の筋の悪さです。一つ足すだけで費用は新しい個数倍になります。つまり二十一個目は、二十個の問題まるごとの二十一倍です。だから二十都市の巡回セールスマンを厳密に解くと 2.4 の百万×百万×百万歩、一秒十億回でも七十七年になります。同じ二十都市が、二の n 乗なら千分の一秒で終わるのにです。

同じ理由で、クラスどうしの差は小さい規模では退屈で、大きい規模では容赦がありません。十要素では n log n と n の二乗の差は三倍で、利用者は誰も気づきません。千要素では百倍、百万要素では五万倍です。同じ二つのアルゴリズム、同じコード、変わったのは入力だけです。

つまり、計算量クラスを正直に読むなら、それは曲線の形についての約束であって、速さについての約束ではありません。入力が増えたとき費用がどう反応するかを述べるだけで、今日あなたの機械で、実際の大きさで速いかどうかについては何一つ述べていません。