グラフアルゴリズムの計算量
グラフに関するアルゴリズム
アルゴリズムの本を読んでいる。

- 作者: Jon Kleinberg,Eva Tardos,浅野孝夫,浅野泰仁,小野孝男,平田富夫
- 出版社/メーカー: 共立出版
- 発売日: 2008/07/10
- メディア: 単行本
- 購入: 10人 クリック: 421回
- この商品を含むブログ (51件) を見る

Algorithm Design: Pearson New International Edition
- 作者: Jon Kleinberg,Eva Tardos
- 出版社/メーカー: Pearson
- 発売日: 2013/08/29
- メディア: Kindle版
- この商品を含むブログを見る
いまいち良くわからない箇所があったので訳を載せておく。因みに、邦訳もあるのだが、わかりにくかった。原著でもよくわからない部分だったので、訳本の問題ではない。
該当箇所はグラフに関する探索アルゴリズムの実装に関する部分。幅優先探索とか深さ優先探索とかの箇所だ。
-
Many graph algorithms need to examine all edges incident to a given node v. In the adjacency matrix representation, doing this involves considering all other nodes w, and checking the matrix entry A[v, w] to see whether the edge (v, w) is present—and this takes O (n) time. In the worst case, v may have O(n) incident edges, in which case checking all these edges will take O(n) time regardless of the representation. But many graphs in practice have significantly fewer edges incident to most nodes, and so it would be good to be able to find all these incident edges more efficiently. *1
- ざっくり訳すとこんな感じである。
-
多くのアルゴリズムでは、与えられた点vから伸びる辺を調べる。隣接行列表現では、すべての点wについて、行列A[v, w]を使って辺(v, w)があるかどうか調べる。そして、これは (vという1つの点について) O(n)時間かかる。最悪のケースでは、vはO(n)の辺を持っていて、この辺すべてを調べるのに O(n) 時間かかるのは(隣接行列といった特定の)表現に関係ない。しかし、実用的には多くのグラフは(最悪のケースである点がn本の辺を持つ場合より) 少ない辺の数を持っている。つまり、( (vという1つの点について) O(n)時間かかるアルゴリズムより) 効率のよくすべての辺を見つけられれば、ためになる。
まず、最初の O(n)のところでつまずいた。全部を調べる最悪のケースのO()と勘違いしていたのだ。ここでは、ある1個の点vについての計算量なのでO(n)が正しい。
次に、
But many graphs in practice have significantly fewer edges incident to most nodes...
の所だが、何に対して significantly fewer edges なのかよくわからない。これは、*2最悪のケースである、点がn本の辺を持つ場合と比べてということである。
簡単なことを述べているだけなのだが、わかりづらかった。最後の、
it would be good to be able to find all these incident edges more efficiently
はどうもしっくりと訳せなかった。大体、効率よく辺を見つかられるアルゴリズムを見つけることは常に良いことだろうに。