初始化指针数据结构的空间复杂性

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符号分解出的系数器:虽然一个大-O空间复杂度std::map<Ptr1,Ptr2>和std::vector<Ptr1>是一样的,在地图乘数较高,因为树建设规定的开销用于存储其中的树节点和连接.