■

DeleteMinで取ってきたノードに隣接するノードはk個。これらをさらに展開してOPENリストに入れるわけだから、理論上Member,InsertはDeleteMinのk倍の回数呼ばれることになる。ただ実際にInsertが呼ばれる頻度はｋ倍まではいかないだろうけど。

• 線形リスト、、　Insert O(1),　Member O(n),DeleteMin O(n)
• バイナリヒープ Insert O(logn),Member O(n),DeleteMin O(logN)

ただMemberは別のデータ構造、配列かハッシュを併用することによって、オーダーO(1)で実行可能なので以下の計算には入れない。(たぶん。アルゴリズムの本でこのMemberのオーダーが計算に入ってないのはこの理由だと思う。)

全体のオーダーはn*DeleteMin + kn*(Insert)。
それぞれ代入すると、以前書いた線形リスト、バイナリヒープを用いたオーダーに一致する。
k倍呼ばれる関係で、最適化の優先度は確かにInsert＞DeleteMinだけど線形リストの場合、DeleteMinのオーダーがO(n)のため、DeleteMin、Insert共にO(logn)のバイナリヒープよりも遅くなる。