Time and Space Complexity
Урок 7 из 9 курса Алгоритм Прима — Алгоритмы на графах на Coddy.
Временная сложность:
- Версия со сканированием ребер здесь имеет сложность O(V * E): V-1 раундов, каждый из которых сканирует все E ребер. С использованием бинарной кучи и списков смежности алгоритм Прима работает за O((V + E) log V).
Пространственная сложность:
- O(V) для массива
inTree(плюс входные ребра).
Резюме:
- Алгоритм Прима выращивает одно дерево, всегда добавляя самое дешевое ребро, выходящее из него, пока не будут включены все вершины.
- Он дает тот же минимальный общий вес, что и алгоритм Краскала, используя другую стратегию.
Попробуйте сами
В этом уроке нет задания по программированию.
Проверьте себяВ этом уроке есть небольшой тест. Начните урок, чтобы ответить на вопросы и сохранить прогресс.
Все уроки раздела Алгоритм Прима — Алгоритмы на графах
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity