공간 초기화 된 포인터 데이터 구조의 복잡성

Question

질문이 있습니다.

이론적 인 컴퓨터 과학의 관점에서 알고리즘을 분석 할 때 알고리즘이 새로운 데이터 구조를 초기화하면 공간 구조의 일부로 데이터 구조를 고려합니다.

이제이 부분에 대해 너무 확신하지 못합니다.

배열이 int인데 포인터를 int 포인터로 매핑하고 싶습니다. 이러한 알고리즘은 포인터를 사용하지 않은 경우

std::map<int*,int*> mymap; 
for (int i = 1; i < arraySize; i++) { 
    mymap[&arr[i-1]]=&arr[i]; 
} 

로서, 우리가 명확하게 N의 크기로지도를 초기화하는 것을 명시 할 수, 따라서 공간 복잡도 그러나 우리는이 경우에 대한, O (N) 인 포인터를 사용하면이 알고리즘의 공간 복잡도는 어떻게 될까요?

Answer 1

단일 포인터의 공간 복잡도는 다른 프리미티브의 공간 복잡성과 같습니다 (예 : O(1)).

std::map<K,V>은 N 노드의 트리로 구현됩니다. 그것의 공간 복잡성은 O(N*space-complexity-of-one-node)이므로, 귀하의 경우의 전체 공간 복잡도는 O(N)입니다.

big-O 표기법은 상수 승수를 배제합니다. std::map<Ptr1,Ptr2> 및 std::vector<Ptr1>의 big-O 공간 복잡성은 동일하지만 트리 구조가 트리 저장에 오버 헤드를 부과하기 때문에 맵에 대한 배율이 높습니다. 노드들과 그들 사이의 연결.