YouTube

Got a YouTube account?

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

Japanese subtitles

← 05-21 Using Heaps

Get Embed Code
3 Languages

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

  1. 各ノードに対して最短距離を見つける処理をします
  2. ヒープで行いますのでここはlog n処理です
  3. これが各ノードに対して行われるので
    この部分のアルゴリズムは
  4. n log nに時間がかかります
  5. エッジについては距離短縮の処理を行うので
  6. ここでもlog nの時間がかかります
    log nまたはm log nです
  7. さてこのn log nと m log nも加算して
  8. 連結グラフという前提で
    mは最低でもn以上なはずです
  9. トータルの実行時間はΘ(m log n)です
  10. このデータ構造設計に携わった2名について
    言及しておきます
  11. フレッドマンとタージャンがこの構造に貢献しました
  12. 特別なヒープを使い実行時間が
    n log n+mとなるようにしたのです
  13. 最低でもmだけがすべてのエッジに
    行けばいいようになりました
  14. 以前私がこのような仕組みを実装した時は
  15. 複雑なヒープ構造の維持にオーバーヘッドがかかり
  16. 漸近的結果しか得られませんでした
  17. しかしこのヒープのオーバーヘッドは小さいので
  18. かなり効率的なはずです