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

Question

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

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

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

Answer 1

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

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

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

---

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