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