コストモデル
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/09/13 15:58 UTC 版)
時間効率の見積もりはステップとして定義するものに依存する。意味のある解析をするには、各ステップの実行時間の上限が一定でなければならない。例えば、2つの数の加算を1ステップと仮定したとしよう。この仮定は場合によっては正しくない。例えば数が極めて大きくなれば、加算が一定時間で完了するとは限らないからである（紙と鉛筆で2桁の加算をする場合と1000桁の加算をする場合を比べていただきたい）。 一般に次の2つのコストモデルが使われる。 一様コストモデル マシンによる全ての演算について、一定のコストを割り当てる。数値の大きさは考慮しない。 対数コストモデル マシンによる全ての演算について、計算対象となる数値のビット数に比例したコストを割り当てる。 後者の方がより複雑になるので、任意精度演算アルゴリズムなどそれが必要となる場合でしか使用されない。任意精度演算は例えば暗号理論で必要とされる。 見過ごされがちな重要な観点として、公表されている問題の下限（最良実行時間）は実際のコンピュータよりも制限された計算モデルについてのものであることが多いという点が挙げられる。そのため、実際にアルゴリズムを実装し実行してみると、想定していたよりも実行時間が短くなる（成長が遅い）ことがある。
※この「コストモデル」の解説は、「アルゴリズム解析」の解説の一部です。
「コストモデル」を含む「アルゴリズム解析」の記事については、「アルゴリズム解析」の概要を参照ください。
ウィキペディア小見出し辞書の「コストモデル」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- コストモデルのページへのリンク
