Если в каждой рекурсии создается новый объект, является ли сложность пространства O (1)?

Question

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

Я чувствую ту часть, в которой я не уверен, может ли пространство объекта быть перерабатывается, когда заканчивается уровень рекурсии. Если пространство можно использовать повторно, я бы сказал, что сложность пространства равна O (1), в противном случае я чувствую, что это O (M), где M - число рекурсий.

Answer 1

Возможность восстановить некоторые объекты (фиксированного размера), связанные с фреймом активации, не меняет асимптотику c сложности. Это только улучшает константы фактического использования ресурса.

Использование алгоритмом хранилища O (M) просто на основе количества кадров активации, которые он выделяет за раз, а не их точного размера.

Конечно, использование 100 байтов в кадре, безусловно, лучше, чем 1000 или 10000, но такие постоянные факторы не способствуют сложности , поэтому мы заставляем их исчезать в обозначении O.

Понижение этого до O (1) потребует реорганизации самого потока управления, такого как переход к хвостовым вызовам или итерации.