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

Question

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

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

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

Answer 1

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

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

Answer 2

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

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