|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 解析 ： [かいせき] 1. (n,vs) (1) analysis 2. (2) parsing
アルゴリズム解析とは、アルゴリズムの実行に必要とされるリソース（時間や記憶領域）量を見積もることである。多くのアルゴリズムは任意長の入力を受け付けるよう設計されている。アルゴリズムの「効率」や「複雑さ」は一般に、入力長からそのアルゴリズムを実行するのに必要なステップ数（時間複雑性）や記憶領域サイズ（空間複雑性）への関数として表される。 アルゴリズム解析は計算複雑性理論の重要な一分野である。計算複雑性理論では、与えられた計算問題を解くアルゴリズムが必要とするリソースを理論的に見積もる。この見積もりにより効率的なアルゴリズムを設計する指針が得られることがある。 アルゴリズム解析ではふつう、漸近的（asymptotic）な意味で複雑性を見積もる。すなわち、ある程度大きな入力長の際の複雑性関数を見積もる。このためにO記法、Ω記法、Θ記法が用いられる。例えば、二分探索のステップ数は入力サイズの対数に比例し、これを ''O''(log(''n'')) と表記したり、「対数時間」と称したりする。このような漸近的な見積もりを用いるのは、同じアルゴリズムでも実装の違いにより差が出るのを捨象するためである。異なる妥当な実装による効率の違いは定数倍に留まる。この定数を隠れた定数（hidden constant）と呼ぶ。 漸近的でない正確な効率がわかる場合もあるが、そのためには「計算モデル」と呼ばれるアルゴリズムの特定の実装を仮定する必要がある。計算モデルはチューリング機械のような抽象化された機械を使うか、個々の命令の実行時間が変化しないと仮定することが多い（例えば実際のコンピュータではキャッシュにヒットするかしないかでは大きく実行時間が異なるが、アルゴリズム解析では一般にそれを無視する）。例えば、二分探索で N 個のソートされた数から探索する場合、1回の参照を一定の単位時間でできるとした場合、回答を得るまでに最大で log2 N+1 単位時間を要する。 == コストモデル == 時間効率の見積もりはステップとして定義するものに依存する。意味のある解析をするには、各ステップの実行時間の上限が一定でなければならない。例えば、2つの数の加算を1ステップと仮定したとしよう。この仮定は場合によっては正しくない。例えば数が極めて大きくなれば、加算が一定時間で完了するとは限らないからである（紙と鉛筆で2桁の加算をする場合と1000桁の加算をする場合を比べていただきたい）。 一般に次の2つのコストモデルが使われる〔, section 1.3〕。 ; 一様コストモデル : マシンによる全ての演算について、一定のコストを割り当てる。数値の大きさは考慮しない。 ; 対数コストモデル : マシンによる全ての演算について、計算対象となる数値のビット数に比例したコストを割り当てる。 後者の方がより複雑になるので、任意精度演算アルゴリズムなどそれが必要となる場合でしか使用されない。任意精度演算は例えば暗号理論で必要とされる。 見過ごされがちな重要な観点として、公表されている問題の下限（最良実行時間）は実際のコンピュータよりも制限された計算モデルについてのものであることが多いという点が挙げられる。そのため、実際にアルゴリズムを実装し実行してみると、想定していたよりも実行時間が短くなる（成長が遅い）ことがある〔Examples of the price of abstraction? , cstheory.stackexchange.com〕。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「アルゴリズム解析」の詳細全文を読む スポンサード リンク
|