Space 数组的复杂度？

Question

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

这里的 space 复杂度是多少。

O(1) 或 (N) - 考虑约束 N.

Answer 1

我认为它将是 O(1)。space 如果 space 大小随着 n.But 的增加而线性增加，则复杂度为 O(n) 在您的情况下，函数是200 后不依赖于 n； f(n)=a*n+b..

Answer 2

仅当您尝试预测算法在各种输入下的性能时，复杂性才有意义。我认为在没有任何上下文的情况下只谈论数组的 space 复杂性没有任何意义。

如果你总是创建一个大小为 N 的数组（硬编码），它是 O(1)，因为无论你的算法处理什么输入，space你的数组取的是一样的

如果您的 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)

Answer 3

Space复杂性通常只为算法定义。

但是让我们狡猾并根据您的问题形成一个算法。

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

Space 复杂度是执行算法所需的内存量，与 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) 应该很小，但现在是 10 TB！

此时我们可能终于意识到我们并不总是需要使用大 O 表示法。我们可以说我们需要存储 10 TB 的数据并购买一些硬盘。如果你的老师对你是为非常小的 N 写 O(1) 还是写 O(n) 而大惊小怪，那么他就是一个非常糟糕的老师。这个问题的答案既不会改变你的生活，也不会改变你的事业。 大 O 表示法只对可以变得非常大的数字有意义。

Answer 4

这取决于您的情况 problem.if 您只使用恒定数量的内存（或 space）。所以，space 复杂度是 O(1).

但是，如果您有一些数据结构，例如一维数组，旨在容纳 N 个元素，其中 N 可以因输入而异，那么所需的内存量取决于 N。当 N 是小，所需的space也小。当N很大时，需要的space也很大。因此，所需的 space 和输入大小存在线性相关性。即 O(N) space.

同样，如果你有一个大小为 NxN 的二维数组，那么通常，所需的 space 是 O(N^2).

考虑以下查找算法所需的最小值 space 的示例：

 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 而变化。总 space 要求 = 2 + N，其中 2 用于变量 n 和 minimum，N 用于 array。所以，这个算法的 space 复杂度是 O(N).

希望这就是您要找的。

Answer 5

I have an array of size N, and N is <= 200.

好的，你有一个大小为 N 的数组。怎么样？意思是，存储一些数据在 space 复杂性方面没有任何意义，因为没有像使用此数组 (space) 的某些代码（算法）那样的上下文。因此，您无法衡量 space 什么都没有的复杂性（没有代码运行，只有数据就在那里）。

现在，如果您在某些上下文中使用此数组，例如创建 N 倍此输入数组的函数，其中 N <= 此数组的长度，那么您可以衡量 space 相对于 [= 的增长情况26=] 这个函数的时间（statements/lines 执行所花费的时间）。

What would be the space complexity here.

O(1) or (N) - considering the constraint N?

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

希望对您有所帮助

Space 数组的复杂度？

Space Complexity of an array?

java

space-complexity