Что означает deg (deg (u))?

Question

Я никогда не слышал этого раньше, или, может быть, я слышал это в других терминах?
Контекст таков, что для списков смежности время перечисления всех вершин, смежных с u , равно Θ(deg(u)).
Аналогично, время, чтобы определить, является ли (u, v) ∈ E O(deg(u)).
Если реализация списка смежности является массивом, то я предполагаю, что он будет постояннымвремя нахождения u в массиве.
Если все смежные вершины связаны с u , то я считаю, что O(n) потребуется время, чтобы составить список или найти все вершины, гдеn - число смежных вершин.
По сути, это означает Θ(deg(u))?

Answer 1

Θ(deg(u)) = биг-тэта степени u = время сильно ограничено (ограничено сверху и снизу) степенью вершин. В случае представления графа списком смежности степень вершины u равна |adj[u]| размер списка для u.

Таким образом, итерация по смежным вершинам u по списку смежности тесно связана с количеством вершин, смежных с u (алгоритмические факты иногда кажутся избыточными, не так ли?).

Разница между Big-O и Big-Theta заключается в том, что Big-O является верхней границей, тогда как Big-Theta устанавливает жесткую границу сверху и снизу. То есть одно и то же выражение служит границей, но с другим коэффициентом m и x0. См. семейство обозначений Бахманна-Ландау в Википедии.

Answer 2

Я почти уверен, deg(u) означает "степень u", то есть количество ребер, которые содержат u.В представлении списка смежности это число также будет размером списка смежности для u, поэтому для его итерации требуется Θ(|list|), то есть Θ(deg(u)).