공간 복잡성에 대한 일반적인 혼동

Question

공간 복잡성을 이해하는 데 문제가 있습니다. 내 일반적인 질문은 : 트리에서 알고리즘의 공간 복잡도가 트리의 노드 수보다 작은 이유는 무엇입니까? 여기서 특정 예이다 :

B는 D는 얕은 목표 노드의 깊이, m은

DFS 들어

, 공간 복잡도로되어 상태 공간의 모든 경로의 최대 길이이다 분지 인자이면 O (bm)이되어야합니다. 나는 항상 나무의 크기 일 것이라고 생각했다. 나머지 나무는 어디에 있고 어떻게 O (bm) 공간 복잡도만으로 전체 트리를 사용합니까?

Answer 1

공간 복잡도가 엑스트라 공간을 나타 내기 때문에 입력과 함께 걸립니다.

복잡도는 일반적으로 튜링 기계와 관련하여 정의됩니다. 알고리즘이 수행하는 공간은 실행에 필요한 추가 셀 수입니다. 입력 셀은 고려되지 않으며 여분의 저장 공간을 줄이기 위해 알고리즘에 의해 재사용 될 수 있습니다.

Answer 2

알고리즘의 공간 복잡도는 일반적으로 원시 데이터가 차지하는 공간과 별개입니다.

예를 들어, 트리를 검색 할 때 트리에서 특정 리프를 얻기 위해 노드 스택을 유지할 수 있습니다. 이 경우, 3은 O (N) 공간을 취하지 만, 탐색은 트리 자체가 차지하는 것 이상의 균형 잡힌 트리 O (log N) 공간을 필요로합니다.