計算モデルと実行時間について

勉強している本↓
sites.google.com

▼本には計算量を分析するためには理想的な数学的モデル、WビットのワードRAMモデルを導入している。しかし、まだ自分のものにできてないので、ここではまとめない。本に書かれていることをまとめると以下のようになる。
・メモリの各セルにはWビットのワードを格納できる。
・ワードに対する基本的な操作（算術演算 $+, -, *, /, ％$ 、比較 $<, >, =, \geq, \leq$ 、ビット単位の論理演算（ビット単位の論理積ANDや論理和OR、排他的論理和XOR））には定数時間を要する。
・メモリのアクセスには定数時間で読み書きできる。サイズｋのメモリの割当には $O(k)$ の時間がかかる。またそのメモリの参照は1ワードで表せる。（つまり、ここでのワード数がメモリ使用量となる）
・データ構造に格納されうる要素数がnのとき $w>\log n$ と仮定する。こうすると要素数を1ワードで表せる。
・WビットのワードRAMモデルはW=32とすると、32ビットコンピュータに似ている。

▼つづいて実行時間の議論について
データ構造の性能には主に3つの指標がある
・正しさ
・時間計算量
・空間計算量
この内、「正しさ」が破られるのはどういうときか。データ構造の実装の中身にバグがあったり、あるいはハードウェアに不具合があってCPUの命令が正しく反映されずメモリの読み書きができなかったり、とかだろうか。もちろんハードウェアの不具合なら大抵はエラーが発生してくれるだろうが、ごく稀にそうでない場合もあるだろう。

▼実行時間について以下のことを議論することが多い。
・最悪実行時間
ある操作の最悪実行時間が $f(n)$ であるというとき、その操作の実行時間が $f(n)$ になることは決して無い。これはわかりやすい。

・償却実行時間
ある操作の償却実行時間が $f(n)$ であるというとき、典型的な実行時間が $f(n)$ を超えないことを意味する。
m回実行したときの合計時間が $mf(n)$ を超えない。
平均値とどう違うのかがわかりにくいと思う。これは個人的な理解だが、平均実行時間 $f(n)$ だとm回実行したときに実行時間が $mf(n)$ を超えないことを保証できない。その実行時間が確率などに左右されているときは実行してみないと超えないかどうかわからない。しかし、償却実行時間の場合、どのようなタイミングで実行時間が大きくなるかわかっている（データ構造の仕組みがわかっている）ので、そのことを織り込んで実行時間 $f(n)$ を見積もれる。よく例に上がるのがJavaのArrayListで、予め用意してあるメモリを超えて要素を追加しようとすると、メモリ確保に時間がかかりそのタイミングだけ実行時間が長くなる。m回その操作を実行するときに、そのタイミングを織り込んで $f(n)$ を見積もるのが償却実行時間ではなかろうか。