Что означает именно такой big O: O(|E|)

Question

Проходил тест по BIG O и попался такой вопрос:

Incidence Matrix -> Матрица инцидентности

Graph Operations: Incidence Matrix
Query

O(|V| + |E|)
O(1)
O(|E|) -> правильный ответ
O(|V|)
O(|V|²)
O(|V| ⋅ |E|)

Вопрос что означает такой big O: O(|E|)?

Тут же, например, нету такой сложности.

Answer 1

Такие Big O типичны для алгоритмов на графах.

Классические обозначения:

|V| - количество вершин в графе (V—от английского "vertices"— это множество вершин)
|E| - количество ребер в графе (E—от английского "edges"—это множество парных вершин, также называемых ребрами)

Таким образом, O(|E|) будет означать что алгоритм имеет линейную сложность в зависимости от количества ребер графа.

По приведенной ссылке находятся примеры алгоритмов, которые не относятся к алгоритмам на графах, и большинство из них использует n в качестве размера "исходных данных". Типичный пример — количество элементов в списке\дереве\любой другой структуре данных.

Для алгоритмов на графах, типичны два очень разных параметра "исходных данных": количество вершин и количество ребер, и вычислительную сложность (Big O) очень полезно раскладывать на эти составляющие.

NB:

По определению, граф — это упорядоченная пара G(V,E). Таким образом, |V| - есть мощность множества вершин, а |E| - есть мощность множества ребер, где мощность нужно понимать как абстрактное обобщение над "количеством элементов множества".

Answer 2

Есть алгоритм. Он принимает на вход ряд параметров: a, b, c...

Алгоритм работает за время t(a, b, c, ...).

Говорят, что алгоритм работает за O(f(a, b, c, ...)), если существует такая константа C, что для любых a, b, c, ... имеем неравенство:

t(a, b, c, ...)<C*f(a, b, c, ...)

В твоем случае a=E, b=V, f=|E|

БЛОГ НА HUSL

Что означает именно такой big O: O(|E|)

Ответы (2 шт):