algorithm - プリムのアルゴリズムの複雑さの上限を証明する

Question

プリムのアルゴリズムの時間計算量の上限をどのように証明できるか知りたいです。プリムのアルゴリズムの時間計算量が O(|E| log |V|)であることは知っています。ここで、E はエッジ、V は頂点ですが、時間計算量の上限とはどういう意味ですか?

Answer 1

しかし、時間計算量の上限は何を意味するのでしょうか?

あなたの質問は、通常、アルゴリズムの上限に関するものです。上限は、f(x) がどれだけ「遠くまで」進むかなど、最悪のケースを制限します。

ビッグ O 表記法による関数の記述は、通常、関数の成長率の上限のみを提供します。アルゴリズムの上限は、上限または最高の成長率を示すために使用されます。

これは、与えられたアルゴリズムが、その入力セットを考えると、この複雑さより悪いパフォーマンスを発揮できないことを意味します。

したがって、グラフにバイナリ ヒープと隣接関係を使用し、エッジを重みで並べ替えると、合計時間の計算量は になりますO(|E| log |V|)。

したがって、f(x) = O(|E| log |V|).

Big-O 表記法で表現すると、この関数の下に制限されます。