最大の複雑さを決定できない - ビッグオー、時間複雑性、グラフアルゴリズム

私はコードの1つの要素（Vは私のグラフの頂点であり、Eはエッジです）、私のコードの別の部分は複雑さO（n log n ）。 O（n | log | n |）はO（| V | *（| V | + | E |））よりも大きいのですか？

回答：

グラフアルゴリズムのコンテキストでは、通常、| V | nと| E | mによって。したがって、あなたのアルゴリズムは時間O（n（n + m））と時間O（n log n）の2つの部分を持っています。最初の部分はO（n² + nm）。したがって、ランタイム全体はO（n² + nm + n log n）。 n log n = 0（n²）、これはO（n² + nm）、全体的なランタイムを提供します。

グラフが接続されていると仮定しているならば、mが少なくともn-1であることを知っているので、これをさらに単純化することができます（nm）。

お役に立てれば！