素朴なアルゴリズム 講義の内容 • 素朴な（工夫の無い）アルゴリズム – 単純挿入法 – 単純選択法 – バブルソート O(n2) • やや工夫されたアルゴリズム – マージソート – ヒープソート – クイックソート O(nlogn) クイックソートの最悪計算量はO(n2) • O(n2) ⇒ O(nlogn) ⇒？ O(n) 単純挿入法 この部分までを、ソートされている状態にしたい この部分までは既にソートされている … ０ １ ２ ３ ４ ５ ６ 単純挿入法 現時点で５番目のデータを適切な位置に移動する 適切な位置に移動したいデータを配列０にコピーする （番兵と呼ばれる技法を使う） … ０ １ ２ ３ ４ ５ ６ 単純挿入法 適切な位置に移動したいデータとその左隣のデータを比べて もし左隣のデータの方が大きい場合はその２つを入れ替える … ０ １ ２ ３ ４ ５ ６ 単純挿入法 … ０ １ ２ ３ ４ ５ ６ 単純挿入法 … ０ １ ２ ３ ４ ５ ６ 単純挿入法（番兵の役割） 番兵を使わないと余計な比較が必要となる while (j > 0) and (x < a[j]) do … ０ １ ２ ３ ４ ５ ６ 単純選択法 小さい順で４番目までを、 ソートされている状態にしたい 小さい順で３番目までは 既にソートされている … １ ２ ３ ４ ５ ６ ７ 単純選択法 残りのデータの中で一番小さいデータを 見つけて４番目のデータを入れ替える １ ２ ３ ４ ５ ６ ７ バブルソート a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] 22 3 3 3 3 3 3 17 22 6 6 6 6 6 6 17 22 9 9 9 9 21 6 17 22 17 17 17 47 21 9 17 22 21 21 9 47 21 21 21 22 22 3 9 47 33 33 33 33 33 33 33 47 47 47 47 決定木とは • ソートの計算過程を木で表したもの • 計算過程 ⇒ データの比較の過程 • ソートアルゴリズム ⇔ 決定木 Yes a<b b<c Yes Yes a<b<c Yes No a<b a<c No Yes No a<c a<b No a<c<b c<a<b Yes No b<c No Yes No b<a<c b<c<a c<b<a ソートアルゴリズムと決定木 比較 c 勝者 b １位 a < b < cの場合 敗者 2位 比較 比較 敗者 a Yes 3位 a<b b<c Yes Yes a<b<c Yes No a<b a<c No Yes No a<c a<b No a<c<b c<a<b Yes No b<c No Yes No b<a<c b<c<a c<b<a ソートアルゴリズムと決定木 比較 c 勝者 b １位 a < c < bの場合 敗者 2位 比較 比較 敗者 a Yes 3位 a<b b<c Yes Yes a<b<c Yes No a<b a<c No Yes No a<c a<b No a<c<b c<a<b Yes No b<c No Yes No b<a<c b<c<a c<b<a ソートアルゴリズムと決定木 • • • • ソートアルゴリズム ソートの時間計算 決定木の葉 決定木の高さ Yes ⇔ ⇔ ⇔ ⇔ 決定木 比較回数 ソートの結果 比較回数 1回 a < b 2回 b < c Yes Yes a<b<c Yes No 3回 a < b a<c No Yes No a<c a<b No a<c<b c<a<b Yes No b<c No Yes No b<a<c b<c<a c<b<a ソートアルゴリズムの下界 定理 • ソートアルゴリズム ⇔ 決定木 n!個の葉を持つどんな決定木Tでも, • ソートの時間計算 ⇔n) 比較回数 決定木Tの高さはΩ(n log • 決定木の葉 ⇔ ソートの結果 • 決定木の高さ ⇔ 最悪比較回数 • 示したい事 n個のデータを持つどんなソートアルゴリズムでも, 最悪比較回数がΩ(n log n)かかる • 決定木の言葉に翻訳すると n!個の葉を持つどんな決定木Tでも, 決定木Tの高さはΩ(n log n) ソートアルゴリズムの下界 定理 n!個の葉を持つどんな決定木Tでも, 決定木Tの高さはΩ(n log n) 証明の概略 – n個のデータがなすソート結果の組合せ数 ⇒ n!個 – 決定木Tの高さをhで表す (このhを見積もりたい) – 高さhの木の葉の個数は高々2h (補題4.1) ⇒ 2h ≧ (葉の個数) = n! ⇒ 2h ≧ n! = (n) × (n-1)×･･･×(n/2) ×･･･×(2)×(1) ≧ (n/2)× (n/2)×･･･×(n/2) = (n/2)n/2 ⇒ h = log 2h ≧ log(n/2)n/2 ≒ n/2 log n/2 = Ω(n log n) ここからは部品 バブルソート １ ２ ３ ４ ５ ６ ７ バブルソート １ ２ ３ ４ ５ ６ ７ バブルソート １ ２ ３ ４ ５ ６ ７ ソートアルゴリズムと決定木 比較 c 勝者 b １位 b < a < cの場合 敗者 2位 比較 比較 敗者 a Yes 3位 a<b b<c Yes Yes a<b<c Yes No a<b a<c No Yes No a<c a<b No a<c<b c<a<b Yes No b<c No Yes No b<a<c b<c<a c<b<a 決定木 比較 c b 勝者 敗者 比較 2位 比較 敗者 a Yes Yes １位 b<c 3位 a<b No No Yes a<c No a < b < c Yes a < c No b < a < c Yes b < c No a<c<b c<a<b b<c<a c<b<a
© Copyright 2024 ExpyDoc
