ダイクストラ線形

Question

まず：Dijkstras最短パスアルゴリズムの一般的な実行時間は、mは、辺の数およびn頂点

の数である

あります

第二：予想decreasekey操作の数は、次の

です

第：ダイクストラの予想走行時間ログにすべての操作を可能にするバイナリヒープと（n）の時間が

しかし、なぜ緻密グラフ上の実行時間が線形である場合でありますグラフが密集していると見なします。

ここでO記法とログ計算をお手伝いできますか？

Answer 1

私の解決策は、mがn log(n) log(log(n))の大きなオメガであるならば、log(n)はlog(m)の大きなオメガであることを示すために、難しいことではありません、今、次の

Answer 2

ファーストです。したがって、mはn log(m) log(log(m))の大きなオメガであることを示すことができます。

nは、大きなオメガがm/(log(m) log(log(m)))であることがわかります。

代替あなたは第三のポイントを持っていると我々は予想実行時間であることを取得式に代入し、このバック：あなたは、ログの合計に製品のすべてのログを拡張することができますここから

O(m + n log(m/n) log(n)) 

        m             m 
    = O(m + (------------------) log(log(m) log(log(m))) log(------------------) 
      log(m) log(log(m))        log(m) log(log(m)) 

。あなたは多くの言葉を得るでしょう。そして、それはすべてがO(m)またはo(m)であることを実証するだけの問題です。面倒ですが、簡単です。