学生版 社会人版
JA EN
体系 › 計算アルゴリズム

計算量と評価

オーダー記法・時間と空間のトレードオフ・実測との乖離

01 ·計算量と評価·無料·8分で読めます 計算量を1から理解する — オーダー記法は何を測っているのか O(n)・O(n log n)・O(n²)が実行時間としてどんな体感になるのか。定数倍とオーダーの違い、時間と空間のトレードオフ、そして理論の計算量とプロファイラの実測が食い違う理由まで、前提知識ゼロで解説します。 02 ·計算量と評価·★ 会員·10分で読めます 計算量と実測が食い違うとき — キャッシュ・分岐・メモリ帯域 同じO(n)のコードが実測では桁で違う——O記法が意図的に捨てている「メモリの現実」を、キャッシュ階層・分岐予測・メモリ帯域の3つの側面から解き明かす。 03 ·計算量と評価·★ 会員·14分で読めます 乱択アルゴリズム — サイコロを振ると速くなる不思議 なぜ乱数を混ぜると速くなるのか。ランダムピボットのクイックソート、片側誤りのブルームフィルタ、モンテカルロとラスベガスの違いを前提知識ゼロから積み上げ、乱数の扱いを間違えたときに起きる事故まで見ます。 04 ·計算量と評価·無料·12分で読めます NP完全を1から — 「解けない」ではなく「検証は速い」 NPはNon-Polynomialの略ではありません。「答えを見せられたら速く確認できる」というクラスの話です。P vs NP・還元・NP完全を前提知識ゼロから積み上げ、シフト表や配送計画といった現場の問題にそれがどう現れるかまで見ます。 05 ·計算量と評価·★ 会員·16分で読めます 近似アルゴリズム — 厳密を諦めて保証を取る 最適解を諦める代わりに「最悪でも◯倍以内」という値札を付ける技術。近似比の定義から、貪欲アルゴリズムの保証を最後まで証明する手つき、巡回セールスマンで三角不等式の有無が結論をひっくり返す理由までを前提知識ゼロで積み上げます。