时间戳

首页 > 解决方案 > 对数组的空间复杂度

c++ - 对数组的空间复杂度

问题描述

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

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

我在想，因为一对是常数并且数组是 n，所以空间复杂度是O(2) * O(n) = O(2n) = O(n). 或者是空间复杂度O(n^2)，因为对数组本质上仍然是一个二维数组？

标签： c++arraysspace-complexity

解决方案

正确的空间复杂度是 O(n)

它表面上类似于二维数组的事实并不重要：第二维的大小是已知的，因此它仍然是 O(n)。如果这些对是 100 个元素的数组，这也是正确的。因为元素的维度（每个 100 元素数组）是已知的，所以结构的空间复杂度为 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 2 )。因为现在两个维度都取决于未知数量。

相反，如果第二维未知但已知与第一维不相关，则可以将其表示为 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) 空间复杂度？”

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

空间复杂度（和运行时复杂度等）旨在用作算法或数据结构的抽象表示。我们使用这些概念在高级概念上计算它们如何扩展到越来越大的输入。两种不同的数据结构，一种需要 100 字节/元素，另一种需要 4 字节/元素平方，在从小环境扩展到大环境时，彼此之间不会有一致的空间等级；在较小的环境中，后一种数据结构会消耗较少的内存，而在较大的环境中，前一种数据结构会消耗较少的内存。空间/运行时顺序复杂性只是表达这种关系的简写，无需陷入细节或语义中。如果细节或语义是你关心的，那么你'

推荐阅读