Какова временная и пространственная сложность первого и глубинного пересечения деревьев по ширине?

Ответ 1

BFS:

Сложность времени O(|V|), где |V| - количество узлов, вам нужно пройти все узлы.
Пространство полноты также O(|V|) - так как в худшем случае вам нужно удерживать все вершины в очереди.

ДФС:

Сложность времени снова O(|V|), вам нужно пройти все узлы.
Сложность пространства - зависит от реализации, рекурсивная реализация может иметь сложность пространства O(h) [наихудший случай], где h - максимальная глубина вашего дерева. Использование итеративного решения с стеком на самом деле такое же, как BFS, просто используя стек вместо очереди - так что вы получаете как O(|V|) сложность времени и пространства.

(*) Обратите внимание, что сложность пространства и временная сложность немного отличаются для дерева, а затем для общих графиков, потому что вам не нужно поддерживать набор visited для дерева и |E| = O(|V|), поэтому |E| фактически является избыточным.

Ответ 2

Есть два основных фактора сложности

• Сложность времени
• Космическая сложность

Сложность по времени

Это время, необходимое для создания node.

В DFS количество необходимого времени пропорционально коэффициенту глубины и ветвления. Для DFS общее количество времени, которое требуется, -

1 + b + b2 + b3 +... + bd ~~ bd

Таким образом, временная сложность = O(bd)

Сложность пространства

Это объем пространства или памяти, необходимый для получения решения DFS сохраняет только текущий путь, который он преследует. Следовательно, пространственная сложность является линейной функцией глубины.

Таким образом, сложность пространства задается O(d)