阵列的空间复杂性？

Question

我有一个大小为N的数组,N <= 200.

这里的空间复杂性是多少？

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

Answer 1

只有当您尝试使用各种输入预测算法的性能时,复杂性才有意义.我认为在没有任何上下文的情况下谈论数组的空间复杂性没有任何意义.

如果你总是创建一个大小为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)

Answer 2

空间复杂度通常仅针对算法定义。

但是，让我们巧妙地根据您的问题形成一个算法。

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

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

当您存储 1 个数字时，您将需要 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！

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