1

N = 頂点の数 M = 有向グラフ G の辺の数とします。辺を隣接リストの形式で保存します。わかりやすくするために、Oi が頂点 i の出次数であり、Ii が頂点 i の入次数であると仮定します。

アルゴリズムは次のとおりです。

for each vertex i
  for each vertex j in i's adj.list
    //do some work
    for each vertex k in j's adj.list
      //do some work

「何らかの作業を行う」ことは、基本的に一定時間 (O(1)) で行われます。N、M で実行時間の一般的な表現を導き出すことができませんでした。誰かがこれを行う方法を説明できますか?

余談ですが、「私はあなたの宿題をしません」というコメントを防ぐために、CLRS からテキスト内の質問 (これは 22.1-5) を練習しています。グラフ アルゴリズムの時間の複雑さを見積もる方法を学ぶためにこれを行っています。 .

4

1 に答える 1

1

アルゴリズムで言及されている各隣接リストは、発信エッジ リストであると想定しています。代わりに、着信エッジと発信エッジの両方が参照される場合、合計作業は定数の 4 倍になり、O() レベルには影響しません。

forステートメントを F1、F2、F3 として参照すると、 F1 は N 回ループします。F2 は合計O1+O2+... = M回数ループします。ここOiで、質問に記載されている発信エッジの度数を示します。F3 は、F2 パスごとに最大で N 回ループし、最悪の場合でもそれよりも小さい下限はありません。これにより、アルゴリズムの O(M・N) 時間 (つまり、F1 と F2 から O(M)、F3 ごとに O(N)) になります。

于 2013-06-21T06:37:39.520 に答える