Сложность примитивов с использованием массива

Question

сложности алгоритма с использованием примитивов массива и смежности Список является:

V^2 + V + 2E + E = O(V^2)

Но я не могу вспомнить, почему E.

Answer 1

Сложность с использованием списка структуры смежности для представления графа, и массив для очереди по приоритету, является Θ (| V | + | E |). Для графиков без параллельных кромок это Θ (| V |).

Алгоритм Прима работает в | V | итерации, растущие на дереве, начиная с размера 1 и заканчивая размером | V |. Скажем, при некоторой итерации к дереву добавляется вершина v, а lete E (v) - это края, исходящие от v. Для каждого такого ребра мы можем найти соседа в массиве и обновить самое легкое расстояние от некоторой вершины в текущем дереве до него. Поиск вершины v требует времени Θ (| V |), так как мы должны сканировать массив, чтобы найти минимальное (это неэффективная реализация очереди приоритетов).

В целом, каждое ребро доступен один раз в каждом направлении (отсюда Θ (| Е |), и каждый из | V | итерации делает Θ (| V |) сканирования на массиве.

---

Обратите внимание, что для выражения в вопросе, V^2 + V + 2E + E, это важно помнить, что контекст является рассмотрение порядков роста. Следовательно, существует не так много смысла 2E (что означает 2? повторяя дважды по краям? Число инструкций CPU на каждый край?) Или действительно до 2E + E. Это просто неопределенные сокращенные обозначения, используемые иногда для обозначения различных этапов алгоритма.