深さ優先グラフアルゴリズムの時間複雑度

私は時間の複雑さを学び始めています。単純な並べ替えでは時間の複雑さの例を見ました。深さ優先グラフアルゴリズムの時間複雑度

|V|=nと|E|=mのグラフで深さ優先探索の平均時間複雑度を計算するには、開始ノードを「u」、終了ノードを「v」としたいと考えました。

2012-04-12 Learner

私はこれが遅すぎることを知っています。しかし、探しているかもしれない他の人のために、ここに詳細な分析があります。 http://techieme.in/depth-first-traversal – dharam

DFSの時間複雑度はO（n + m）です。この複雑さは、各ノードを一度しか訪れていないという事実と、すべてのエッジを一度越えているツリー（サイクルなし）の場合を考慮して得られます。

例えば、開始ノードがuであり、終了ノードがvである場合、vが最後に訪問されたノードである最悪の場合を考えています。これで、接続されたコンポーネントの最初のネイバー、次に2番目のネイバーの接続コンポーネント、最後のネイバーの接続されたコンポーネント、vが見つかるまでの各コンポーネントを訪問し始めました。同じエッジを2回以上越えた。

出典

2012-04-12 06:45:39 gabitzish

敬意を表して、私は複雑さの分析には新しく、実際には私はOS上でプロジェクトをやっています、私はリソース割り当てグラフのサイクルを見つけようとしています...私は深さの最初の検索の変更を使用してサイクルを見つける...私はこのアルゴリズムの複雑さを銀行家のアルゴリズムと比較しようとしています..あなたは "avergaeケースのパフォーマンス"の数学的導出を与えることができます – Learner

"平均ケースパフォーマンス"は期待値です確率論からの項）を仮定している。 –

そのグラフは隣接行列の形態である場合、グラフは、隣接リストが、の形で与えられるならば、複雑度は我々のようにO（N×n個）、あるO（N + M）になり私たちがエッジを見つけるまで行全体を横切る必要があります。

出典

2013-05-17 17:28:03

深さ優先グラフアルゴリズムの時間複雑度

答えて

関連する問題