データ構造とアルゴリズム第二回知能情報学部新田直也前回の復習  アルゴリズムとは: 「チューリングマシンで表現される計算手続き」 (チャーチの提唱)   本講義では，適当なプログラミング言語によって表現する．アルゴリズムの性能:   一般に，1つの問題を解くアルゴリズムは複数存在．アルゴリズムの中に早いものと遅いものがある．最大公約数を求めるアルゴリズム  問題: 与えられた2自然数ａ, b の最大公約数を求めよ．  解法1: 総当り計算 1) 2) 3)  c := min{a, b} とおく． c が a, b を共に割り切る場合, c を出力して停止． c := c – 1 とおき，2) へ．解法2: ユークリッドの互除法 1) 2) 3) 4) c := max{a, b}, d := min{a, b} とおく． c を d で割った余りを r とおく． r が 0 ならば，d を出力して停止． c := d, d := r とおき，2) へ．計算の例  12と9の最大公約数を求めよ. [総当り計算] 1) 2) 3) 2) 3) 2) 3) 2) 3) 2) 3) 2) 3) 2) c := 9 割り切らない c := 8 割り切らない c:=7 割り切らない c:=6 割り切らない c:=5 割り切らない c:=4 割り切らない c:=3 割り切るので 3 を出力 [ユークリッドの互除法] 1) 2) 3) 4) 2) 3) c := 12, d:= 9 r := 3 r は 0 でない c := 9, d := 3 r := 0 r が 0 なので 3 を出力 →速い!! 計算の例(2)  12と6の最大公約数を求めよ. [総当り計算] 1) c := 6 2) 割り切るので 6 を出力 →速い!!  [ユークリッドの互除法] 1) c := 12, d:= 6 2) r := 0 3) r が 0 なので 6 を出力この例のように，総当り計算の方が速い場合もある． →どのようにしてアルゴリズムの速さを比較するか? 入力データのサイズ  最大公約数を求める計算では，入力データは2つの自然数 a, b ．  データサイズをビット長で表す．   すなわち，log2 a + log2 b 一般に，入力のデータサイズが大きくなると計算に費やす時間も長くなる．  ただし，入力のデータサイズを固定しても計算時間は一意に定まらない．サイズ = 8 総当りユークリッド互除法 a = 12, b = 9 14 6 a = 6, b = 18 2 3 入力サイズと計算時間の関係計算時間(steps) 時間計算量 16 14 12 10 8 6 4 2 0 最良の場合 0 2 4 6 入力サイズ(bit) 総当りユークリッド 8 入力サイズと計算時間の関係計算時間(steps) 時間計算量 16 14 12 10 8 6 4 2 0 最悪の場合 0 2 4 6 入力サイズ(bit) 総当りユークリッド 8 時間計算量の種類  最良の計算時間を比較しても無意味．   入力サイズによって変化しない．全体から見ると例外的な状況．     たまたま a と b が一致する場合．たまたま a, b のいずれかが他方の倍数になっている場合．アルゴリズムの性能を表しているとは言いがたい．一般に最悪または平均の計算時間を比較する．   最悪(最大)時間計算量: 解析的に求めやすい．平均時間計算量: より実態を表しているが，解析が困難．時間計算量の評価  最悪の時間計算量を比較したとしても，全入力サイズで一方が他方より速いとは限らない．（どこで比較するか?）  大きい入力サイズで比較したほうがよい．  全体の中では小さいサイズの方が例外的だと考えられる．オーダー表記  どのような関数に従って時間計算量が増大していくか?  オーダー O: 入力 n に対して，ある関数 f(n) が O(g(n))であるとは? 適当な定数 c, n0 が存在し，任意の n >= n0 について， f(n) <= c・g(n) が成り立つことを言う．関数 f(n) が O(g(n))であるとき， f(n) ∈ O(g(n)) または， f(n) = O(g(n)) と書く．計算量のオーダー  (最悪/平均)計算量は，通常オーダーで比較する．  オーダーの例：     n2 + 10 = O(n2) 2n2 + 4n + 10000 = O(n2) 2n + n2 = O(2n) n + log n = O(n) オーダーの効果  オーダーでは係数部分やオーバーヘッドが無視される．   コンピュータが速くなっても影響されない．プログラミング言語が変わっても影響されない。 →アルゴリズムの実質的な評価．  実行時間の実測値：     コンピュータによって影響される．同一コンピュータ上でもメモリ状況によって影響される．もちろんプログラミング言語にも影響される．コーディングテクニックにも影響される．時間計算量と領域計算量(1)  メモリをふんだんに使えば超高速に計算できる．  たとえば答えを予め求めておいて，表として保持しておく． a b GCD(a.b) 1 1 1 2 1 1 1 2 1 2 2 2 3 1 1 1 3 1 1 4 1 2 3 1 → 最悪時間計算量はO(1) 時間計算量と領域計算量(2)  前スライドの例   使用するメモリの量は? →O(2n) --- 領域計算量時間計算量と領域計算量は一般にトレードオフの関係にある．  目的に応じてアルゴリズムを選ぶ必要がある．計算量のまとめ  アルゴリズムの性能は計算量のオーダーで比較．  計算量の種類:  時間計算量    最悪時間計算量 → 単に計算量と言う場合がある．平均時間計算量領域計算量   最悪領域計算量平均領域計算量問題の難しさ(1)  ある問題を解くアルゴリズムは一般に複数存在する．  各問題で一番速い(最悪時間計算量のオーダーが最小である)アルゴリズムは?    最速のアルゴリズムを見つける方法は今のところない．（天才のひらめき）これ以上速く解けないということを証明できる場合がある．問題の難しさを知られている最速のアルゴリズムのオーダーで評価できる．問題の難しさ(2)  多項式時間アルゴリズムが存在する問題クラス P   指数時間アルゴリズムが存在する問題クラス EXP   最悪時間計算量のオーダーが，n の指数関数であるようなアルゴリズムが知られている問題の集合．非決定性多項式時間アルゴリズムのクラス NP   最悪時間計算量のオーダーが，n の多項式であるようなアルゴリズムが知られている問題の集合．最悪時間計算量のオーダー，n の多項式であるような非決定性アルゴリズムが知られている問題の集合． P = NP? 問題  数学上の未解決問題の1つ．