初始化指針數據結構的空間複雜度

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)。

請注意，大O符號會影響常數乘數：雖然std::map<Ptr1,Ptr2>和std::vector<Ptr1>的大O空間複雜度是相同的，但映射的乘數較高，因爲樹構造強制其存儲樹的開銷節點和它們之間的連接。