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

请注意，big-O 表示法分解了常量乘数:尽管 std::map<Ptr1,Ptr2> 的 big-O 空间复杂度和 std::vector<Ptr1>是相同的， map 的乘数更高，因为树构造强加了存储树节点和它们之间的连接的开销。