← 研修トップ
データ構造とアルゴリズムの土台
なぜこのデータ構造を選ぶのか、なぜ遅いのか、見積もりをどう立てるのか。計算理論としてではなく、実務の判断として扱います。配列と連結リストの違いがキャッシュで決まること、ハッシュの平均O(1)が置いている仮定、木を低くすると読む回数が減る算数、そしてimportの依存解決がグラフの巡回であること。公式文書の計算量保証と実測から積み上げます。
- 1約 9 分なぜ「増え方」で測るのか — O記法が言っていないこと秒数は機械や状況で変わりますが、n を増やしたときの増え方は変わりません。だから計算量は、機械をまたいで持ち運べる比較の道具になります。
- 2約 9 分配列と連結リスト — 番地が続いているかどうか同じ「並び」に見えても、要素の番地が連続しているか飛んでいるかで別物になります。連続していれば、第7週で見た「64バイトまとめ読み」がそのまま効きます。
- 3約 9 分平均O(1)が置いている仮定 — ハッシュ表は魔法ではない「ハッシュ表は O(1)」は規格の書き方と食い違っています。C++ 標準ドラフトは `The worst-case complexity for most operations is linear, but the average case is much faster.`。最悪は線形です。
- 4約 9 分半分にすると、なぜ20回で済むのか100万件を1件ずつ見れば100万回ですが、毎回半分を捨てられるなら20回で1件まで絞れます。log₂(1,000,000) = 19.93… で、切り上げて20回です。
- 5約 9 分木は放っておくと偏る — 平衡が要る理由木を辿る回数が log で済むのは、形が保たれているときだけです。素の二分探索木は挿入された順序がそのまま形になり、ソート済みの列を入れると一直線に伸びます。
- 6約 9 分木を低くすると、読む回数が減る1回の読み取りでまとめて取れる量が大きいほど、1段あたりの分岐数は増えます。分岐が増えれば木は低くなり、根から葉まで辿るのに**読む段数が減ります**。
- 7約 9 分比較で並べ替える限界 — 下限があるということ要素どうしを比べることだけで並べ替えるなら、必要な比較回数には下限があります。CPython の listsort.txt は lg(n!) を「全順列にわたる平均で、比較に基づく方法が到達できる限界」と書いています。
- 8約 9 分取り出す順序が、解ける問題を決めるキューとスタックは「入れ物」が違うのではなく、**取り出す規則**が違うだけです。cppreference は両方を container adaptor と説明し、Python の `queue` 公式は3種類の差を "which differ only in the order in which the entries are retrieved" と書いています。
- 9約 9 分依存はグラフ — import が解決される形import を書くと、コードが1行も走る前にモジュールの依存がグラフとして深さ優先で辿られます。ECMAScript 仕様は自分の言葉で depth-first search (DFS) traversal と書き、循環部分を strongly connected components (SCCs) と呼んでいます。
- 10約 9 分同じ計算を2回しない — 覚えておくという交換同じ部分問題を何度も解き直しているなら、答えを覚えておけば済みます。払うのは、覚えておく場所です。
- 11約 9 分ならし計算量は、平均ではない配列の末尾への追加は、1回1回を見ると最悪 O(n) かかります。それでも n 回の合計を回数で割ると O(1) に収まります。これが「ならし (amortized)」です。
- 12約 9 分桁で見積もってから測る計算量の値打ちは、走らせる前に「n がいくつなら何が問題になるか」を桁で言えることにあります。n=100万で二重ループを書いたら待てない、は測らずに分かります。
- 13約 9 分選ぶとは、捨てること全部が速いデータ構造はありません。何かが速い構造は、別の何かが遅いか、別の何かを余分に使います。