「アルゴリズム」の記事
20件 RSS で購読
20件
Project Euler 5: 1から20までのすべてで割り切れる最小の数を最小公倍数から組み立てる
1から20までのすべての数で割り切れる最小の正の整数を、1つずつ試すのではなく、ユークリッドの互除法と lcm(a, b) = a / gcd(a, b) × b の繰り返しで組み立てます。この方法がちょうど最小公倍数を与える理由の証明、整数の範囲、C++17とPython 3の実装まで扱います。
Jump Consistent Hash：表を持たずにシャード番号を決めるコンシステントハッシュと、その前提条件
シャードを10個から12個に増やすとき、hash mod n はキーの5/6を動かしますが、本当に動かす必要があるのは1/6です。Lamping・Veach の論文のコード、仕組み、バケットを増減したときに起きることをまとめました。
Project Euler 4: 3桁の数2つの積で最大の回文数を大きい方から探す
3桁の数2つの積のうち最大の回文数を、大きい積から順に探して枝刈りしながら求めます。枝刈りで答えを見落とさない理由の証明、偶数桁の回文数と11の関係、整数の範囲、C++17とPython 3の実装まで扱います。
Union-Find の経路圧縮とサイズによる重み付け：α(n) はどの実装に付く計算量か
Union-Find でサイズによる重み付け、経路圧縮、経路半減が parent 配列をそれぞれどう変えるかを小さな例で追い、最悪 Θ(log n) と操作列全体の O(m α(n)) がどの実装に当てはまるかを Princeton の algs4 の資料に沿って整理しました。
Project Euler 3: 割れるだけ割って最大の素因数を求める
小さい数から割れるだけ割っていく試し割り法で、12桁の整数の最大の素因数を求めます。最後に残る値がなぜ素数なのかの証明、√n の反復回数の上限、64ビット整数の範囲、C++17とPython 3の実装まで扱います。
KMPの失敗関数：不一致のあと、パターンはどこへ戻るのか
KMP文字列探索で不一致のあとパターンのどの位置を次に比較するかを決めるf表とnext表の定義と作り方、探索全体が線形時間になる理由を、1977年の原論文とPrincetonの実装に沿って整理します。
Project Euler 2: 偶数のフィボナッチ数だけを足す
フィボナッチ数列では3項ごとに偶数が現れることを証明し、偶数項どうしの漸化式 E(k) = 4E(k−1) + E(k−2) を導いて、400万以下の偶数項だけを足します。C++17とPython 3の実装、正しさの証明、整数の範囲まで扱います。
Project Euler 1: 3または5の倍数の和をO(1)で求める
1000未満で3か5で割り切れる数の和を、ループを使わずに包除原理と等差数列の和で求めます。C++17とPython 3の実装、正しさの証明、整数の範囲まで扱います。
Linux カーネルの rbtree：比較関数を保持せず、ノードを構造体に埋め込む赤黒木
Linux の赤黒木は比較関数を保持しません。ノードの埋め込み、自分で書く探索・挿入ループと呼び出しごとに比較関数を受け取るヘルパー、色ビット、cached・augmented 木、ロックなし探索の限界を v6.17 のソースで整理します。
スキップリスト：コイン投げで決めたレベルが O(log n) の探索を生む仕組み
ソート済み連結リストにランダムなレベルのポインタを足すと、なぜ探索が期待 O(log n) になるのか。Pugh の報告書のアルゴリズム、「期待」時間の範囲、Java ConcurrentSkipListMap のドキュメントが約束することを整理します。
長さのわからないストリームから k 個を公平に選ぶ: リザーバーサンプリング(Algorithm R)
全体の件数がわからないデータを一度だけ読みながら k 個を無作為に選ぶリザーバーサンプリング。置き換え確率が k/i になる理由、どの要素も k/n で残る証明、k 個の組み合わせの均等性、よくある範囲の誤りをまとめました。
ハッシュテーブルが O(1) でなくなるとき：衝突、O(n²) の挿入、ハッシュフラッディング
dict や HashMap の O(1) は期待値です。全キーのハッシュ値が同じだと n 個の挿入に少なくとも n(n−1)/2 回の比較が要る理由と、Python のハッシュランダム化と PYTHONHASHSEED、Rust の SipHash、Java の Comparable による対策をまとめました。
ブルームフィルタが「ない」ときだけ断言できる理由
ブルームフィルタが「確実にない」か「あるかもしれない」でしか答えない理由、偽陰性が出ないという保証が成り立つ条件、偽陽性の確率の式、ビットを消すと保証が崩れる理由を整理します。
sort(() => Math.random() - 0.5) でシャッフルしてはいけない理由と Fisher–Yates
ランダムな比較関数で配列を並べ替えても均等に混ざらない理由を ECMAScript 仕様で確認し、すべての順列が同じ確率で出る Fisher–Yates シャッフルと、乱数の範囲・生成器の注意点をまとめました。
クイックソートはいつO(n²)になるのか：標準ソートが最悪ケースを防ぐ仕組み
ソート済み入力、median-of-3 killer、敵対的な比較関数でクイックソートは二次時間になります。introsortの深さ制限と、C++・Rust・Go・Javaの文書が保証する範囲を解説します。
ダイクストラ法が負の重みで正しく動かない理由
負の辺がダイクストラ法の貪欲な選択を壊す仕組みを、辺3本の小さな反例で確認し、Bellman–Ford法やDAG向けの手法との使い分けを整理します。
ヒープはソート済みリストではない：優先度付きキューの並び順とインデックスの式
heapq や PriorityQueue を出力すると、なぜ並んでいないのか。ヒープが守る条件、0始まりの親子インデックスの式、ソート済みリストとの計算量の違い、同じ優先度の扱いを公式ドキュメントで整理します。
二分探索の挿入位置：bisect・lower_bound・binarySearch は何を返すのか
値がないときや重複があるときに Python の bisect、C++ の lower_bound、Java の Arrays.binarySearch が返す位置と、それぞれの前提条件を公式ドキュメントと C++ 規格で比べました。
配列の末尾への追加はなぜ O(1) なのか：動的配列と償却計算量
満杯になると全要素をコピーすることがあるのに append が O(1) とされる理由を、容量と償却解析で説明し、Java・C++・Rust・Go のドキュメントが保証する範囲と実装が決める増加率、容量を先に確保する方法をまとめました。
安定ソート（stable sort）とは：同じ値の並び順が保たれるソート
安定ソートの意味、複数のキーで並べ替えるときに重要な理由、Python・JavaScript・Java・C++の標準ソートが何を保証しているかを仕様と公式ドキュメントをもとに整理しました。
該当する記事がありません。別の言葉で検索してみてください。