0

無向グラフでエッジ分離パスのセットを見つけるアルゴリズムがあります。

  1. グラフ内のすべてのエッジのリストから始めます

  2. リストに使用可能なエッジがまだある間に、深さ/幅優先検索を実行してパスを見つけます。パスが見つかった場合は、それを保存し、リストとグラフの両方からエッジを削除して、パス カウンターをインクリメントします。

  3. リストから最初に使用可能なエッジを削除し、それを現在のパスに指定します

  4. 現在のパスを保存されたエッジのリストと照合してください

  5. 有効なエッジが一致しない場合、パスは終了します

  6. 使用可能なエッジが現在のパスを拡張できる場合は、それを現在のパスに追加し、エッジ リストから削除してから、現在のパスの拡張を試み続けます。

2 と 3 は O(E(V+E) + E) 時間で実行されると思います。

  • 幅/深さの最初の検索は O(V+E) 時間で実行されます
  • 検索はリスト内の E エッジで実行されます
  • リストとグラフからの E エッジの削除

アルゴリズムの後半部分は、エッジ リストの反復処理に 2 つのループが必要なため、O(E^2) 時間で実行されます。

したがって、最終的な最悪のケースは O(E(V+E)+ E^2+E)=O(EV+2E^2+E) です。

私は正しいですか？

4

1 に答える 1

1

いいえ、そうではありません。私があなたの問題を理解している限り、 O(E(V+E)+ E^2+E) は正しいです。しかし、Big O Notation では、複雑さのために「最大の」イベントを採用します。複雑さのクラスが 3 つあります。

  1. E(V+E)
  2. E^2
  3. え

どの場合でも 2 の方が大きいため、点 3 は点 2 によって削除されます。「最悪の場合」の E は V^2 です。これがわかれば、ポイント 1 が最も複雑な部分であると判断できます (V^3+V^4 > V^4)。あなたのアルゴリズムは正しく、パーツに関する仮定も同様であるため、この問題のアルゴリズムの複雑さは次のようになります: O(E(V+E))

これらのスライドをご覧ください。スライド 23 では、複雑さが書き留められており、計算に適合しています ;)

于 2013-04-21T11:40:22.220 に答える