Является ли время выполнения BFS и DFS на двоичном дереве O (N)?

Я понимаю, что время выполнения BFS и DFS на универсальном графе составляет O (n + m), где n — количество узлов, а m — количество ребер, и это связано с тем, что для каждого узла необходимо учитывать его список смежности. Однако каково время выполнения BFS и DFS при выполнении на двоичном дереве? Я считаю, что это должно быть O (n), потому что возможное количество ребер, которые могут выйти из узла, постоянно (т. Е. 2). Пожалуйста, подтвердите, если это правильное понимание. Если нет, то объясните, пожалуйста, какова правильная временная сложность BFS и DFS на двоичном дереве?


algorithm time-complexity breadth-first-search binary-tree depth-first-search
person gmemon    schedule 11.11.2013    source источник
comment
возможный дубликат Какова временная и пространственная сложность обхода дерева сначала вдоха и сначала в глубину   -  person amit    schedule 11.11.2013

Ответы (2)


arrow_upward
23
arrow_downward

Временные сложности для BFS и DFS — это просто O(|E|) или, в вашем случае, O(m).

В двоичном дереве m равно n-1, поэтому временная сложность эквивалентна O(|V|). m относится к общему количеству ребер, а не к среднему количеству смежных ребер на вершину.

person kevmo314    schedule 11.11.2013

arrow_upward
19
arrow_downward

Да, O(n) верно.

Также заметим, что количество ребер более точно можно выразить как количество узлов - 1. Это довольно легко увидеть, если учесть, что каждый узел, кроме корня, имеет ребро от своего родителя к себе, и эти ребра покрывают все ребра, которые существуют в дереве.

person Bernhard Barker    schedule 11.11.2013