数组的空间复杂度是什么？

Question

数组的空间复杂度是什么？

javaspace-complexity

10

我有一个大小为N的数组，其中N<=200。

在考虑到约束条件N的情况下，这里的空间复杂度将会是O(1)或(N)。

- Ritt

这只是N，不是吗？ - nafas

2

算法的空间复杂度不是很重要吗？你的算法是什么？给定N，创建一个大小为N的数组。它的时间复杂度是O(N)。如果它在另一个输入大小为n（与N无关）的算法中，并且你只需要创建一个大小为N的数组，那么它的时间复杂度是O(1)。 - Jeremy Grand

@nafas 是的，我也这么想。但是这里的N并没有增长，它是恒定的。 - Ritt

@JeremyGrand 是的，这很有道理。 - Ritt

1

@nafas 是的，我同意。我认为在这种情况下，如果数组大小是固定的，而且它不会增长到任何地方，那么时间复杂度应该是O(1)。 - Ritt

显示剩余5条评论

5个回答

7

空间复杂度通常只针对算法进行定义。

但是让我们聪明地从你的问题中形成一个算法。

Input: N values, N <= 200
Algorithm: Store all values
Output: None

空间复杂度是指执行算法所需的内存量，与N有关。

当你存储1个数字时，你需要一个存储区域。当你存储2个数字时，它会变为两倍。你的内存复杂度是O(n)，这意味着它呈线性增长；就像对于这个算法一样：

Input: N values, N <= 18,446,744,073,709,551,616 (unsigned int 64).
Algorithm: Store all values
Output: None

但是200真的很小，我们能不能说O(1)呢？

让我们再次巧妙地来解决这个问题，因为我们可以将其变成O(1):

Input: N values, N <= 200
Algorithm: Store all values in an array of size 200
Output: None

当您存储1个数字时，需要200个内存区域。当您存储2个数字时，需要200个内存区域。当您存储200个数字时，需要200个内存区域。这意味着内存是恒定的且与N无关。因此，复杂度为O（1）。

重要的是要注意，O（1）并不意味着您需要的内存量为1，而是意味着您需要的内存量与N无关。因此，当N增长时，它不会增加。

但是，如果我的对象是50GB的蓝光光盘怎么办？ O（1）应该非常小，但现在它将达到10TB！

此时，我们可能最终意识到，并不总是需要使用大O符号表示法。我们可以说我们需要存储10TB的数据并购买一些硬盘。如果您的老师对于您是否为非常小的N编写O（1）或O（n）感到烦恼，那么他是一个非常糟糕的老师。这个问题的答案既不会改变您的生活也不会改变您的职业生涯。大O符号只有在数字可以变得非常大的情况下才有意义。

- Eldar Kersebaum

3

这取决于您的问题情况。如果您只使用恒定的内存（或空间），则空间复杂度为O(1)。

然而，如果您有一些数据结构，比如一个1D数组，设计用于容纳N个元素，其中N可以从输入到输入变化，那么所需的内存量就取决于N。当N很小时，所需的空间也很小。当N很大时，所需的空间也很大。因此，所需空间与输入大小呈线性关系。这是O(N)空间。

同样地，如果您有一个大小为NxN的2D数组，则通常所需的空间为O(N^2)。

考虑以下示例，查找算法所需的最小空间：

 Scanner in = new Scanner(System.in);
 int n = in.nextInt();
 int[] array = new int[n];
 for(int i = 0; i < n; i++){
     array[i] = in.nextInt();
 }
 int minimum = array[0];
 for(int i = 0; i < n; i++){
     if (array[i] < minimum){
        minimum = array[i];
     }
 }
 System.out.println(minimum);

这里，我们有一个数组，其大小随n而变化。总空间需求= 2 + N，其中2是变量n和minimum的空间，N是array的空间。因此，这个算法的空间复杂度为O(N)。

希望这正是您所需要的。

- Oghli

2

我认为这将是O（1）的。如果空间大小随着n的增加而线性增加，则空间复杂度为O（n）。但在您的情况下，函数在200之后不依赖于n; f（n）=a*n+b。

- gati sahu

1

我有一个大小为N的数组，其中N <= 200。

好的，你有一个大小为N的数组。那又怎样呢？也就是说，仅仅存储一些数据并没有任何意义，因为没有上下文，比如使用这个数组的某些代码（算法）（空间）。因此，你不能测量空间复杂度（没有要运行的代码，只是数据坐在那里）。

现在，如果你在某种上下文中使用这个数组，比如一个函数，该函数创建N次输入数组，其中N <=这个数组的长度，则可以测量空间增长与运行时间（执行的语句/行数所花费的时间）之间的关系。

这里的空间复杂度将是多少？

考虑到约束条件N，这里的空间复杂度将是O(1)或(N)。

在你的情况下，空间复杂度将是O(1)，因为没有运行时间增长，因为没有要执行的代码。只有一个数据（你的数组）。

希望这能帮到你。

- Fouad Boukredine

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jeremy Grand · Accepted Answer

只有在尝试使用不同的输入来预测算法性能时，复杂性才具有相关性。我认为，如果没有任何上下文环境，仅谈论数组的空间复杂度是没有意义的。

如果您总是创建固定大小为N的数组（硬编码），则其复杂度为O(1)，因为无论您的算法处理什么输入，数组占用的空间都相同。

如果N随着输入大小而增长，则其复杂度为O(f(n))，其中f(n)是n（输入大小）和N（数组大小）之间的关系。

注意：O(...)公式是一种用数学符号表示数量级的方法，与乘数无关（抱歉表达不够精确，我已经超出了我的数学水平，从未学过英文术语），因此，如果N是一个常数，O(N)=O(1)（它们完全相同）。

如果我没记错的话，如果f < C * g，则O(f) = O(g)。因此，如果N小于200，则O(N) = O(200) = O(1)