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

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>，但映射的乘数更高，因为树的构造会增加存储树节点和它们之间的连接的开销。