Сайт http://web.eecs.utk.edu/~huangj/CS302S04/notes/graph-searching.html описывает, что, когда используется список смежности, DFS и BFS имеют сложность O (V + E) и если используется матрица смежности, сложность O (V 2). Почему это?
Почему временная сложность DFS и BFS зависит от того, как представлен график?
Ответ 1
В обоих случаях время выполнения зависит от того, сколько времени потребуется для итерации по исходящим ребрам данного node. С помощью списка смежности время выполнения прямо пропорционально количеству исходящих ребер. Поскольку каждый node посещается один раз, стоимость - это количество узлов плюс число ребер, которое равно O (m + n). С матрицей смежности время, необходимое для нахождения всех исходящих ребер, равно O (n), поскольку все n столбцов в строке для a node должны быть проверены. Суммируя по всем n узлам, это получается для O (n 2).
Надеюсь, это поможет!
Ответ 2
Вы должны заметить, что для изучения каждой вершины времени, необходимого для изучения, она равна только c * x, где x - это неопределенность вершины. Поскольку нас интересует общая сложность, общее время будет c1 * x1 + c2 * x2... cnxn для n узлов. Принимая max (ci) = d, мы видим, что общее время равно <= d (сумма значений всех вершин) = d * 2m = O (m). мы вычислили время не для одной вершины, а для всех вершин, взятых вместе. Но операция enqueuing занимает время O (n), поэтому totall O (n + m).
Ответ 3
Временная сложность для DFS и BFS может быть вычислена следующим образом:
Итерация каждой вершины один раз и соответствующих инцидентных ребер, поэтому общая сложность по времени будет ->
Сложность времени = v1 + (инцидент_еджи на v1) + v2 + (инцидент_границы на v2) +...... + vn + (инцидент_границы на vn)
Теперь это можно перегруппировать как → (v1 + v2 + v3 +..... vn) + (инцидент_еджи на v1 + инцидент_еджи на v2 +..... инцидент_еджи на vn)
Таким образом, общая сложность времени оказалась бы = (v1 + v2 + v3 +..... vn) + (инцидент_еджи на v1 + инцидент_еджи на v2 +..... инцидент_еджи на vn)
(v1 + v2 +... + vn) = V или n (общее количество вершин)
Для представления списка смежности:
(инцидент_еджи на v1 + инцидент_еджи на v2 +..... инцидент_еджи на vn) = E (общее количество ребер)
Таким образом, для времени представления списка смежности сложность времени будет O (V + E)
Для представления матрицы смежности:
Чтобы посетить соседей соответствующего узла (строки), нам нужно перебрать все столбцы для конкретной строки, которая составляет V
Итак, (инцидент_еджи на v1 + инцидент_еджи на v2 +..... инцидент_еджи на vn) = V + V +.... V-й раз V) = V * V
Таким образом, временная сложность будет O (V + V ^ 2) = O (V ^ 2)