YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

Japanese subtitles

← 03-12 Running Time of Connected Component

Get Embed Code
3 Languages

Showing Revision 1 created 03/11/2014 by Fran Ontanaya.

  1. 実行時間の解析は重要です
  2. それによって効率が分かるからです
  3. ここでもまた問題解決にかかる
  4. アルゴリズムの最短経路や実行時間をカウントします
  5. 前と同様にnはグラフ内のノード数と仮定し
  6. mはエッジ数と仮定します
  7. このアルゴリズムで使用する基本戦略は
  8. 一種のグラフ検索です
  9. グラフ検索には深さ優先探索と幅優先探索の
    2つの基本的な探索法があります
  10. ここでは深さ優先探索の形式についてお話しします
  11. 幅優先探索については
  12. 最短経路と合わせてあとでお話しします
  13. このアルゴリズムではパス長は関係なく
  14. パスを使って到達するすべてのノードを探索します
  15. このアルゴリズムを見てください
  16. すぐに気づくのは
  17. このmarked[node]=Trueのような文です
  18. これはグラフの各ノードに一度だけ実行されます
  19. いつ実行されるかは見極めづらいですが
  20. すべてのノードが一度だけ
    マークされるということは分かっています
  21. つまり各ノードにつき一度だけ
    実行されるということです
  22. ではこの2つの文とループを実行します
  23. ループは簡単に言うと
  24. この特定のノード[node]につながっている
    すべてのエッジを訪れて
  25. マークされているかどうかをチェックします
  26. これを表すif文がループの単位時間を
    操作する文となります
  27. これは一種のハッシュテーブルです
  28. ここが再帰呼び出しで
    内容を明らかにする必要がありますが
  29. とりあえず今は置いておきましょう
  30. ここで主要な計算が行われ
    ここに合計の値が加えられて
  31. また返します
  32. これらの文は各ノードに1度ずつ実行され
  33. これも各ノードに1度実行され
  34. これはグラフ内の各エッジに実行されます
  35. なぜならエッジは訪れる各ノードから出ているからです
  36. 何がいつ実行されるかを把握するのは困難ですが
  37. 実行時間の合計は把握できます
  38. ノード数+グラフ内のエッジ数のビッグ・シータです
  39. それがここで行われていることです
  40. 次のコードではmarkedは一度だけ実行されます
  41. mark_componentを呼び出す
    for node in Gは実行されるかは分かりません
  42. これをすべてに繰り返しますが
  43. 各ノードに対する処理にすぎないので
  44. 別のnを加えても実行時間は大してかかりません
  45. いつどのコンポーネントが実行されるかは
    分かりづらいですが
  46. 実行時間はΘ(n+m)です
  47. ちなみにこのグラフのサイズは線形です
  48. グラフはノード数とエッジ数で
    構成されているということです
  49. そのためグラフのサイズは線形になります