big-o - Θ（deg（u））はどういう意味ですか？

Question

私はこれまで聞いたことがありませんか、それとも他の言葉で聞いたことがありますか？コンテキストは、隣接リストの場合、 u
に隣接するすべての頂点をリストする時間はです。 同様に、（u、v）∈Eであるかどうかを判断する時間。隣接リストの実装が配列である場合、配列内でu を見つけるのは一定の時間であると思います。隣接するすべての頂点がuに リンクされている場合、すべての頂点を一覧表示または検索するには時間がかかると思います。ここで、nは隣接する頂点の数です。 それは本質的にどういう意味ですか？Θ(deg(u))
O(deg(u))

O(n)
Θ(deg(u))

Answer 1

Θ(deg(u))=次数のビッグシータu=時間は、頂点の次数によって厳密に制限されます（上下から制限されます）。グラフの隣接リスト表現の場合、頂点の次数はuの|adj[u]|リストのサイズですu。

したがって、隣接リストによって隣接する頂点を反復処理することは、隣接する頂点のu数に密接に関係していuます（アルゴリズムの事実は冗長に聞こえることがありますね）。

Big-OとBig-Thetaの違いは、Big-Oが上限であるのに対し、Big-Thetaは上下からタイトな境界を示していることです。つまり、同じ式が境界として機能しますが、係数mとx0が異なります。ウィキペディアでBachmann-Landau表記のファミリーを参照してください。

Answer 2

私はかなり確かdeg(u)に「程度u」、つまりを含むエッジの数を意味しますu。隣接リスト表現では、その番号はの隣接リストのサイズにもなるためu、反復するにはΘ(|list|)、が必要です。これはΘ(deg(u))です。