軽重分類と償却解析で総仕事量を抑える

概要

一回の操作で多数の要素を処理しても、その重い処理を何度も繰り返せるとは限らない。操作列全体で要素が何回動くか、何回消えるかを数えると、一操作の最悪時間を単純に掛けるより小さい上界を得られる。

考え方

重い一操作を、何回実行できるか

空の容器に要素を追加する操作と、中身を一個ずつ取り出して空にする操作を考える。取り出した要素は戻さず、一個の追加・取り出しは定数時間とする。

「aを追加、bを追加、cを追加、空にする、もう一度空にする、dを追加、空にする」という7操作では、空にする各操作の取り出し回数は順に3、0、1回で、合計4回である。最初の一括処理は重いが、次も同じだけ処理するには要素を補充しなければならない。

全体で QQ 操作あるとき、一操作の取り出し回数は最大で QQ 程度なので、これを毎回に掛ければ O(Q2)O(Q^2) という上界になる。しかし、一つの追加で生まれた要素は高々一度しか取り出されない。各取り出しの費用を、その要素を追加した操作へ割り当てれば、総取り出し回数は追加回数以下となる。このような割り当てを課金と呼ぶ。空かどうかの確認を含む各操作の固定費用も合わせ、全体は O(Q)O(Q) 時間である。

このように操作列全体の費用を抑えるのが償却解析である。どの有効な操作列に対しても上界を示すので、入力がランダムだと仮定する平均時間とは区別する。

課金先を選んで下位単元へ進む

毎回の全走査が重そうなら、「その一反復を発生させたものは何か」「同じものが再び費用を負担するまでに何が必要か」を調べる。次の三つでは、その答えが異なる。

  • 一度限りの移動・消滅では、追加された要素や辺の各実体へ課金する。一実体がその移動・削除を経験するのは高々一度なので、生成された実体数から総量を抑える。単調進行で操作列を追う。
  • 所属サイズの増大・半減では、移動・走査された要素へ課金する。移動のたびに所属サイズが倍以上になるなら、最大サイズを NN として一要素に O(log⁡(N+1))O(\log(N+1)) 回まで課金できる。分割で半分以下になる場合も同様。small-to-largeで条件を確認する。
  • 閾値による軽重の分割では、軽い対象の走査と、重い対象ごとの前処理へ費用を分ける。軽い側は一回の走査量、重い側は対象数を制限する。閾値による軽重分類で両側の費用を釣り合わせる。

所属サイズを使う場合は、併合と分割の反復でサイズが戻らないか、重複の消滅で倍増の前提が崩れないかも確認する。閾値分割では、総出現数を MM、正の閾値を BB とすれば、出現数が BB を超える重い対象は高々 M/BM/B 個になる。この個数の上界は、要素が一度だけ消えるという議論とは別に得られる。

成立条件と計算量

まず要素の移動・辺の削除などの一回を費用単位に選び、総回数を証明する。次に一回あたりのデータ構造の費用を掛け、初期化・全操作の固定費用・出力を加える。例えば総移動回数が O(Q)O(Q) でも、一回にheap挿入が必要なら全体は O(Qlog⁡(Q+1))O(Q\log(Q+1)) 時間となる。

削除済みの要素を復元したり、同じ位置に要素を再生成したりできる場合は、そのたびに新しい処理の予算を数える。空間は累積処理回数だけでは決まらないので、同時に保持する要素数と補助配列の大きさから別に評価する。

下位単元

問題一覧

この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

導入対象の目安: 水色(1200–1599)。一操作の最悪時間から離れ、総仕事量と軽重分類で計算量を設計する入口。

対象色の読み方は本書の読み方を参照してください。

概念上の親: モデル変換とアルゴリズム設計。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-decomposition-amortization

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: なし。

このUnitでは扱わないもの

  • 探索空間を分けて候補を列挙・照合するmeet-in-the-middleや分割統治。

根拠