Почему временная сложность как DFS, так и BFS O (V + E)

132

Базовый алгоритм для BFS:

set start vertex to visited

load it into queue

while queue not empty

   for each edge incident to vertex

        if its not visited

            load into queue

            mark vertex

Поэтому я бы подумал, что временная сложность будет такой:

v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges) 

где vвершина 1кn

Во-первых, правильно ли я сказал? Во-вторых, как это O(N + E), и интуиция относительно того, почему это было бы действительно хорошо. Спасибо

обычный
источник

Ответы:

268

Ваша сумма

v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges)

может быть переписан как

(v1 + v2 + ... + vn) + [(incident_edges v1) + (incident_edges v2) + ... + (incident_edges vn)]

и первая группа, в O(N)то время как другая O(E).

Михай Марусак
источник
1
Но каждая вершина должна быть извлечена из очереди, а это журнал (| Q |) А что насчет этой части?
Yola
3
log (| Q |) <log (N) <N, поэтому вы можете спокойно игнорировать член в асимптотике
Михай Марусеак
2
Если в списке смежности каждая вершина соединена со всеми остальными вершинами, сложность будет эквивалентна O (V + E) = O (V + V ^ 2) = O (V ^ 2). E = V ^ 2, потому что наибольшее количество ребер = V ^ 2.
Макс
Согласно вашему ответу, сложность не станет O (V + 2E)? Поскольку каждое ребро может иметь общее ребро с другим ребром?
Каранский
2
От постоянных членов можно отказаться.
Михай Марусеак
41

ДФС (анализ):

  • Установка / получение метки вершины / ребра требует O(1)времени
  • Каждая вершина помечена дважды
    • один раз как НЕИЗВЕСТНО
    • один раз как ПОСЕТИТЕ
  • Каждое ребро помечено дважды
    • один раз как НЕИЗВЕСТНО
    • один раз как DISCOVERY или BACK
  • Метод IncidentEdges вызывается один раз для каждой вершины.
  • DFS запускается во O(n + m)времени, если граф представлен структурой списка смежности
  • Напомним, что Σv deg(v) = 2m

BFS (анализ):

  • Установка / получение метки вершины / ребра занимает O (1) раз
  • Каждая вершина помечена дважды
    • один раз как НЕИЗВЕСТНО
    • один раз как ПОСЕТИТЕ
  • Каждое ребро помечено дважды
    • один раз как НЕИЗВЕСТНО
    • один раз как DISCOVERY или CROSS
  • Каждая вершина вставляется один раз в последовательность Li
  • Метод IncidentEdges вызывается один раз для каждой вершины.
  • BFS работает во O(n + m)времени, если граф представлен структурой списка смежности.
  • Напомним, что Σv deg(v) = 2m
Новый
источник
tnx для редактирования, я здесь новичок, поэтому я все еще пытаюсь справиться с экраном редактирования :)
TheNewOne
1
спасибо за конкретность, упомянув, что графы должны быть представлены структурой списка смежности, меня беспокоило, почему DFS - это O (n + m), я бы подумал, что это O (n + 2m), потому что каждое ребро проходит дважды путем возврата.
mib1413456 02
22

Очень упрощено без особых формальностей: каждое ребро рассматривается ровно дважды, и каждый узел обрабатывается ровно один раз, поэтому сложность должна быть постоянной, кратной количеству ребер, а также количеству вершин.

Нитеш Дадвария
источник
Намного легче понять, чем математические обозначения без дополнительных объяснений, хотя Google для этого и предназначен.
mLstudent33
11

Сложность времени O(E+V)вместо этого, O(2E+V)потому что, если сложность времени равна n ^ 2 + 2n + 7, то она записывается как O (n ^ 2).

Следовательно, O (2E + V) записывается как O (E + V)

потому что разница между n ^ 2 и n имеет значение, но не между n и 2n.

Дхрувам Гупта
источник
@Am_I_Helpful, кто-то спрашивает выше о 2E в нотации big-oh .... вот почему 2 не рассматривается во временной сложности.
Дхрувам Гупта
@Am_I_Helpful, просто посмотрите сообщение над моим ответом .... там пользователь по имени Kehe CAI написал: «Я думаю, что каждое ребро было учтено дважды, и каждый узел был посещен один раз, поэтому общая временная сложность должна быть O (2E + V ) «. Я ответил соответственно .... Понятно !!!
Дхрувам Гупта
Я удалил свой голос против только потому, что вы отредактировали свой ответ,
Am_I_Helpful,
3

Я думаю, что каждое ребро было рассмотрено дважды и каждый узел был посещен один раз, поэтому общая временная сложность должна быть O (2E + V).

Кехе ЦАИ
источник
Даже я чувствую то же самое. Кто-нибудь может дать дополнительные объяснения по этому поводу?
Чайтанья
12
Анализ Big O игнорирует константу. O (2E + V) - это O (E + V).
Hemm
3

Интуитивно понятное объяснение этому заключается в простом анализе одного цикла:

  1. посетить вершину -> O (1)
  2. цикл for на всех инцидентных ребрах -> O (e), где e - количество ребер, инцидентных данной вершине v.

Таким образом, общее время для одного цикла составляет O (1) + O (e). Теперь просуммируйте его для каждой вершины, поскольку каждая вершина посещается один раз. Это дает

For every V
=> 

    O(1)
    +

    O(e)

=> O(V) + O(E)
Ultrablendz
источник
2

Краткое, но простое объяснение:

В худшем случае вам нужно будет посетить все вершины и ребра, поэтому временная сложность в худшем случае составляет O (V + E)

CodeYogi
источник