7

PageRankアルゴリズムのBig-Oの複雑さを探しています。私はほとんど何も見つけることができませんでした、私はちょうど見つけましたO(n+m)（n-ノードのm数、-アーク/エッジの数）が、私は今のところこの複雑さを信じていませんでした。

収束基準が欠けていると思います。これが一定だとは思いませんでした。収束はグラフの直径に依存すると思います。1回の反復でBig-Oを使用するだけで十分な場合があります。その場合、収束は重要ではありません。

それにもかかわらず、PageRankはすべてのノードにアクセスし、すべての着信ランクを集約する必要があるため、実行時間は。と予想していましたO(n * m)。

私は何か見落としてますか？PageRankのBig-Oの複雑さの貴重な情報源を知っている人はいますか？

前もって感謝します。

4

1 に答える 1

2

いくつかの調査とさらなる考察の結果、私はO(n+m)本物であるという結論に達しました。

完全グラフであっても、各エッジに2回触れる必要があるためです。すべての端に触れることができなかった、それは私の考えの間違いでした。そのため、少なくともすべてのノードに触れる必要があります。これは、大きなOでmである各エッジのn回と2回です。したがって、正解は次のようになります。O(n+m)

于 2012-09-24T11:09:41.307 に答える