heapを使ったダイクストラ法の計算量について考える

はじめに

タイトルにもある通り、heapを使用したダイクストラ法の計算量について考えてみます。
ダイクストラ法について知らない方はこちらなどが分かりやすいです。
heapについて知らない方はこちらなどが分かりやすいです。

結論

計算量は以下のようになります。

• 頂点の数V、辺の数Eとすると

O((V+E)log(V))

• V≒E(頂点と辺の数がほぼ同じ)の場合

O(Vlog(V))

• 各頂点から全ての頂点に辺があるような場合

O(V^2 log(V))

なぜ(V+E)log(V)になるのか

ダイクストラ法で、値を更新していくコードの主要部分は以下のようになります。

# 既にその頂点までの最低コストが確定している場合、頂点番号のindex要素をTrueとします。
seen = [False for _ in range(V)]

# その頂点までのコストを管理します。
C = float("Inf")
cost = [C for _ in range(V)]
cost[0] = 0

# (コスト, 頂点番号)
heap = [(0, 0)]

# Gは辞書型で、頂点0→頂点1のコストが10の場合、G[0][1] = 10としています。
while heap:
    s = heappop(heap)[1]
    seen[s] = True
    for i in G[s].keys():
        if cost[i] > cost[s] + G[s][i] and not seen[i]:
            cost[i] = cost[s] + G[s][i]
            heappush(heap, (cost[i], i))

ある時点で始点から最小のコストで行ける頂点の取得はheappopで行います。heappopの計算量は

O(log(V))

です。(後述)
この計算は外側のwhileのループ数の分だけ行いますが、頂点の取り出しは多くてもV回(頂点数)になります。
したがって、上記コードのheappop関連の計算量は

O(Vlog(V)) ・・・(1)

です。

ある時点での各頂点への最小コストが更新された場合、heappushを行います。heappushの計算量は

O(log(V))

です。(後述)
この計算は(whileのループ数)×(for i in G[s].keys())のループ分行いますが、どんなに多くてもE(辺の数)を超えることはありません。
ifの条件文が毎回trueだとしても、辺の数の回数しか更新は走らないはずだからです。したがってheappush関連の計算量は

O(Elog(V))・・・(2)

です。

(1)と(2)を合計すると、heapを使用したダイクストラ法の計算量は

(V+E)log(V)

になることが分かります。

heappopの計算量はなぜO(log(V))になるのか

heappopは実際には以下の操作をこの順番で行っています。

1. heapの先頭と末尾を交換(以後、先頭に来た要素を「追加した要素」と表現する)
2. heapの末尾を削除
3. 追加した要素が子要素より大きければ交換
4. (3)の操作を葉の要素まで繰り返す。

(3)の処理を繰り返すとき、最大でルート要素から葉要素まで行います。
heapを構成する完全二分木の高さをhとすると、最大でh回繰り返すことになります。
要素数がVの完全二分木の高さはlog(V)(後述)なので、heappopの計算量はO(log(V))で見積もることができます。

heappushの計算量はなぜO(log(V))になるのか

heappushは実際には以下の操作を行っています。

1. 末尾に要素を追加
2. 追加した要素が親要素より小さければ交換
3. (2)の操作をルートの要素まで繰り返す。

(2)の処理を繰り返すとき、最大で葉要素からルート要素まで行います。
heapを構成する完全二分木の高さをhとすると、最大でh回繰り返すことになります。
要素数がVの完全二分木の高さはlog(V)(後述)なので、heappopの計算量はO(log(V))で見積もることができます。

要素数Vの完全二分木の高さ

完全二分木は、高さがhのとき、要素数は最大で

2^{h+1} - 1

になります。

これは、等比数列の和を使うと、簡単に求めることができます。

高さがh-1のとき、要素数は最大で

2^{h} - 1

になります。

つまり高さがhのとき、要素数Vは以下の条件を満たします。

2^{h} - 1 < 2^{h} <= V <= 2^{h+1} - 1 < 2^{h+1}

2^{h} <= V < 2^{h+1}

両辺logを取ると

h <= log(V) < log(h+1)

となり、hは正の整数なので、高さhはlog(V)と分かります。(高さを0~で考えた場合)

まとめ

• heapを使ったダイクストラ法の計算量はO((V+E)log(V))
• heappopの計算量はO(log(V)) (Vは要素数)
• heappushの計算量はO(log(V)) (Vは要素数)
• 要素数Vの完全二分木の高さはlog(V)

参考

• ヒープをわかりやすく解説してみた
• 完全二分木の根の高さがO(logn)となる理由
• 等比数列の和
• ダイクストラ法とは?