c++ - 初始化指针数据结构的空间复杂度

我有一个问题。

从理论计算机科学的 Angular 来看，当我们分析算法时，如果算法初始化了一个新的数据结构，则我们认为该数据结构是空间复杂性的一部分。

现在我对这部分不太确定。

假设我有一个int数组，我想通过使用int指针映射来映射它们。如

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

如果此算法未使用指针，则我们可以清楚地声明它正在初始化大小为n的映射，因此空间复杂度为O(n)，但是在这种情况下，如果我们使用指针，空间复杂度是多少这个算法？

最佳答案

单个指针的空间复杂度与任何其他原语(即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空间复杂度相同，但映射的乘数较高，因为树的构造增加了其存储树节点和连接之间的开销。他们。

关于c++ - 初始化指针数据结构的空间复杂度，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20099528/