アルゴリズムとデータ構造2のテスト用ノート

B木

各ノードは最大m本の枝を持つ, 恨と葉以外のすべてのノードはm/2以上の枝を持つ, 挿入時ノードの要素数がm-1を超える場合は真ん中の要素を親として2分割して部分木を作り,親のノードの枝の位置に挿入する,それを繰り返す, ノードの中間の要素を消す時は,子の最大の要素をそこに挿入する,葉がなくなってしまう場合は隣から貰ってくる,隣にも存在しない場合,子の要素2つを合体して新たな子とし,枝の数を減らす, 高さは0オリジン,全てのノードに要素を詰めた場合,要素数は\(高さ*次数^0 + 高さ*次数^1 + … + 高さ*次数^{高さ}\)となる

ホーナー法

\(a_0 + a_{1}x + a_{2}x^2 + … + a_{n}x^n = a_0 + x(a_1 + x(a_2 + … x(a_{n - 1} + a_{n}x)))\)

RSA暗号

e = 正の整数, P, Q = 素数, N = P * Q, m = 暗号文, M = 平文, \(ed = k*(P‐1)*(Q‐1)+1\), \(m = M^e mod N\), \(M = m^d mod N\)

ソート

ヒープソート: O(n log n), ヒープの要素の子要素は配列の添字で2n, 2n + 1に存在する, ヒープへの挿入はまず最下層に要素を追加し,追加した要素と親を比較し,順序が正しくなければ交換する, ヒープからの削除はルートの削除は末尾と交換し,子要素と正しく入れ替えていく, ヒープソートはまず全てをヒープにして,末尾からルートの要素を入れ替えていく, マージソート: O(n log n), クイックソート: O(n^2)

    auto l = begin;
    auto r = end - 1;
    auto pivot = std::max({*l, *(l + 1), *(l + 2)});
    while (true) {
        while (*l < pivot) {
            ++l;
        }
        while (pivot < *r) {
            --r;
        }
        if (l < r) {
            std::iter_swap(l, r);
            ++l;
            --r;
        } else {
            break;
        }
    }
    quick_sort(begin, l);
    quick_sort(l, end);

シェルソート: \(O(n \log^2 n)\)間隔を分けて値をグループ化し,それぞれでソートする, ビンソート: 値を配列の添字に使って配列に格納する, 分布数え上げソート: 重複データを処理できるように出現回数を記録, 基数ソート: 桁をキーにしてソートする

文字列探索

BF法: 1文字づつずらして検索する, KMP法: ずらして良い幅をパターン用に構築して使う,前の重複する文字までずらして良い?, BM法: パターンの比較を後ろからやり,パターン用にずらして良い値を作っておきそれを使う,パターンに固有の値で比較失敗したら完全にずらして問題ない,不一致サフィックスは知らない

ダイクストラ法

未確定ノードのうち最短のノードを確定させ,確定しているノードと連結しているノードの仮距離を更新する.というのを繰り返せば良い.

このエントリーをはてなブックマークに追加 fb-like g-plusone pocket