Space 对数组的复杂度

Question

所以我想知道整数对数组的 space 复杂度是多少？

std::pair<int,int> arr[n];

我在想，因为一对是常量，数组是 n，所以 space 复杂度是 O(2) * O(n) = O(2n) = O(n)。还是 space 复杂性 O(n^2) 因为对数组本质上仍然是一个二维数组？

Answer 1

取的space是n * sizeof(std::pair<int, int>)个字节。 sizeof(std::pair<int, int>)是常数，O(n * (constant)) == O(n).

Answer 2

正确的 Space 复杂度是 O(n)

它表面上类似于二维数组这一事实并不重要：第二维的大小是已知的，因此，它仍然是 O(n)。如果这些对是 100 个元素的数组，这也是正确的。因为元素的维度（每个元素为 100 个元素的数组）是已知的，所以结构的 Space 复杂度为 O(100 * n)，即 O(n)。

然而，相反地，如果元素明确地始终与整个容器的大小相同，即是这样的：

int n = /*...*/;
std::vector<std::vector<int>> arr(n);
for(std::vector<int> & subarr : arr) {
    subarr.resize(n);
}

那么它确实是 O(n²) 而不是。因为现在两个维度都取决于一个未知的数量。

相反，如果第二个维度未知但已知与第一个维度不相关，则可以将其表示为 O(nm)，即这样构造的数组：

int n = /*...*/;
int m = /*...*/;
std::vector<std::vector<int>> arr(n);
for(std::vector<int> & subarr : arr) {
    subarr.resize(m);
}

现在这似乎是矛盾的：“但是 Xirema，你刚才说如果我们知道维度是 n X 100 个元素，它将是 O( n)，但是如果我们用 100 代替 m，我们会不会有 O(nm) 或 O(100n) space 的复杂度？"

但就像我说的：我们删除了已知数量。 O(2n) 等价于 O(5n)，因为我们只关心未知数。一旦未知数变为已知数，我们在评估 Space 复杂性时不再将其包括在内。

Space 复杂性（和运行时复杂性等）旨在用作算法或数据结构的抽象表示。我们使用这些概念在高层次概念上计算出它们如何扩展到越来越大的输入。两种不同的数据结构，一种需要每个元素 100 个字节，另一种需要每个元素平方 4 个字节，当从小型环境扩展到大型环境时，彼此之间的 space 等级将不一致；在较小的环境中，后一种数据结构会消耗较少的内存，而在较大的环境中，前一种数据结构会消耗较少的内存。 Space/Runtime 顺序复杂性只是表达这种关系的 shorthand，无需陷入细节或语义的泥潭。如果细节或语义是您关心的，那么您不会只使用 structure/algorithm 的顺序，您将实际测试和衡量这些不同的方法。

Answer 3

一个数组的space复杂度一般可以说是：

O(<size of array> * <size of each array element>)

这里有：

std::pair<int,int> arr[n];

所以arr是一个有n个元素的数组，每个元素是一个std::pair<int,int>。假设一个 int 占用 4 个字节，所以一对两个 int 应该占用 8 个字节（这个数字可能会根据实现略有不同，但这对于复杂度计算的目的无关紧要).所以复杂度将是 O(n * 8)，这与 O(n) 相同，因为常量不会影响复杂度。

你什么时候会有O(n^2)这样的东西？那么，您需要一个 multi-dimensional 数组。例如，像这样：

std::pair<int,int> arr[n][m];

现在 arr 是一个包含 m 个元素的数组，但每个元素又是 n std::pair<int,int> 个元素的数组。所以你有O(m * <size of array of n pairs>)，也就是O(m * n * 8)，也就是O(m * n)。如果 m 恰好与 n 相同，则得到 O(n * n) 或 O(n^2).

如您所想，同样的推理适用于任意数量的数组维度。

Space 对数组的复杂度

Space complexity of an array of pairs

c++

arrays

space-complexity

正确的 Space 复杂度是 O(n)