Общая путаница по поводу сложности пространства

Question

У меня проблемы с пониманием сложности космоса.Мой общий вопрос: как пространственная сложность алгоритма на дереве может быть меньше, чем количество узлов в дереве?Вот конкретный пример:

Если b - это коэффициент ветвления, то d - это глубина самого мелкого целевого узла, а m - максимальная длина любого пути в пространстве состояний.

. Для DFS сложность пространства равнадолжен быть O (бм).Я думал, что это всегда будет размером с дерево?Где остальная часть дерева и как мы используем все дерево только с O (bm) пространственной сложностью?

Answer 1

Пространственная сложность алгоритма обычно отделена от пространства, занимаемого необработанными данными.

Например, при поиске дерева вы можете сохранить стек узлов в дереве, до которого спустилисьдобраться до какого-то конкретного листа.В этом случае тройка занимает O (N) место, но поиск занимает (при условии сбалансированного дерева) O (log N) пространство сверх того, что само дерево занимает.

Answer 2

Поскольку сложность пространства представляет собой дополнительное пространство, которое она занимает помимо ввода.

Сложность, как правило, определяется для машин Тьюринга.Пространство, которое занимает алгоритм, - это дополнительное количество ячеек, необходимое для его работы.Ячейки ввода не учитываются и могут быть повторно использованы алгоритмом для уменьшения дополнительной памяти.