アルゴリズム(3章)
-
チューリングマシン:アルゴリズム用に定式化された数学的なモデル。以下の4つから成り立つ。(ⅰ) 入力データと出力データを含む二重の無限に長い記号のテープ。(ⅱ)読み/書きするヘッド。(ⅲ)可能な状態の一覧。(ⅳ)データを与えられたとき、実際にアルゴリズムのステップを指定するプログラム。チューリングマシンはアルゴリズムを開発するための実用的なツールではない。数学的定理の証明、問題の算法的複雑さの評価、異なるアルゴリズム間の比較などに役に立つ。
- 作者: A.ポランスキ,後藤修
- 出版社/メーカー: 丸善出版
- 発売日: 2012/07/17
- メディア: 単行本
- 購入: 1人 クリック: 1回
- この商品を含むブログを見る
- アルゴリズムは一般的に様々なデータセットに適用でき、実行時間は入力データの長さ(大きさ)に依存する。アルゴリズムの実行時間と入力データ長とを関連付ける規則はアルゴリズムの複雑さ、またはアルゴリズムの計算時間と呼ばれる。
- 実行中にアルゴリズムは中間データを算出する。中間データはコンピュータのメモリに格納されなければならない。アルゴリズムが必要とするメモリ格納容量(占有量)は、アルゴリズムの効率を特徴付ける第2のパラメータ。中間データの量もまた入力データの大きさに関連づけられ、メモリ占有効率はこれらの2つの量の関係によって記述される。
- 単純ソートとクイックソート:逐次並び替え K(K-1)/2回の比較が必要。O(K^2)。一方、クイックソートでは、X→[X1 xs X2]→[X11 x1 X12 x2 X21 x2 X22]→…のようにスプリッターxの大小で分割を繰り返す。分割にはKのオーダー、分割の回数はlog2Kのオーダーなので、速さはO(Klog2K)のオーダー。
- 単純検索と高速検索: