カンパニーの計算量

カンパニーを実装しようとして、カンパニーの解体のアルゴリズムを考えてみた。一番シンプルでオーソドックスなアルゴリズムは、すべてのパスの積の和をとるというそのままの方法だが、この場合の計算量を見積もってみた。

まずは計算量の上限を見積もるのがこの手の問題の常套手段なので、Np人の人とNcの数のカンパニーが互いに1/(Np+Nc)の評価をしているような偏りのないケースを考えてみた。（実は対称性から答えは計算しなくても自明なのだが、このケースから少しずれたら計算するしかなくなる）

結論からいうと、

貢献度計算の計算量=C₁N_p²+C₂N_p²(N_c^{logε/logα_c}-1)/(N_c-1)

となる。ここで、εはそれ以下は計算しないという誤差の精度、α_c=N_c/(N_c+N_p)である。

ちなみに第１項がべき乗法で貢献度ベクトルを求める計算量で、第２項はその前にカンパニーを解体する計算量だ。

-1なんて大した数じゃないので、割愛して整理すると、

貢献度計算の計算量=C₁N_p²+C₂N_p²N_c^{logε/logα_c-1}

となる。このことから、N_c^{logε/logα_c-1}

が計算量を決めることが分かるだろう。実はこの数、N_c=N_p=1000、ε=10^-9とすると、N_c³⁰になる。鬼だ。

この瞬間、カンパニーを実装するのをやめようと思ったが、これは計算量の上限の話だ。カンパニーの取引に極端な偏りがあると、急に楽になる。たとえば、ひとつの会社が10社としか取引していないと、N_c^3.5になる（これでもカンパニーはすべての人と取引していい場合だ）。

このことを数式で表現するには、αの定義をかえてあげればよい。すなわち、カンパニー同士の平均取引関係数をN_c2cとして、

α_c2c=N_c2c/(N_c2c+N_p)

として、

貢献度計算の計算量=C₁N_p²+C₂N_p²N_c^{logε/logα_c2c-1}

これでも結構な数だが、なんとかならなくもない。でも、世界経済を記述するとなったら、大変なことになるかも。

上記の式だが、可能なパスのパターンを等比級数で求めれば誰でも計算できるだろう。暇つぶしにどうぞ。