21/12/05 15:04:30.36 RsIoD/ak.net
>>803
>オーダーの話と実時間の話をシレっと往ったり還ったりするところなんかは、私には変だと思いましたね、
>アルゴリズムの評価はオーダーで行うのが普通で他はほとんどみない…
書くのが長くなるからオーダーで書いているだけで、オーダーだけでは正しい特徴を捉えられない
場合がある。
例えば、同じオーダーでも乗算や条件分岐の両方が使われているアルゴリズムとマシン語の
1クロックの命令1個にコンパイルされるものでは全然違う。
また、N個のデータを持っているハッシュ構造は、1回の検索は、数学的に厳密にはO(N)
だが、実験的(実際的)にはO(1)のように振舞うと言われており、厳密に扱うには、
オーダーの記号だけでは表現しきれない。
もし、オーダーだけで評価すればいいのなら、チューリング完全なあらゆる言語は、
同じアルゴリズムを使うことは可能で、同じオーダーの時間で計算できてしまうから、
速度比較には役立たない。