• 作成: 2018-01-19T13:38:16+09:00

アルゴリズムとデータ構造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法: パターンの比較を後ろからやり, パターン用にずらして良い値を作っておきそれを使う, パターンに固有の値で比較失敗したら完全にずらして問題ない, 不一致サフィックスは知らない

ダイクストラ法

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