数组与字符串的大 O 内存

Question

这听起来可能很愚蠢，但我想了一下想知道，你不能玩弄算法并使 O(n) 内存看起来像 O(1) 吗？(Java) 假设您有一个包含 N 个真或假元素的数组。然后该数组将导致 O(n) 内存。但是，如果我们有一个“FFFFFFTFTFFT”数组，其中每个 charAt(i) 都回答数组的第 i 个索引的结果，那么我们是不是只使用了 O(1) 内存，或者它被认为是 O(n ) 内存，因为 String 是 O(n) 本身的大小？让我们更进一步。如果我们有一个包含真假的 N 数组并将其转换为字节，我们使用的内存甚至更少。那么字节也被认为是 O(1) 内存还是 O(n) 内存？例如，假设 n = 6。那么数组大小为 6 = O(n)。但是字节大小只有 1 个字节，因为 1 个字节可以存储 8 个不同的值（8 位）。那么这是 O(1) 还是 O(n) 因为对于大 N 我们得到以下情况...：N 等于 10000。数组是 O(n) 内存，但字节是什么内存？因为我们的字节是 O(n/8) = O(n)？

Answer 1

您描述的所有情况都是O(n)，它描述了n趋于无穷大时的限制行为，从数学上说：

f(n) = O(n), as n -> INF等于f(n)/n -> const, as n -> INF，其中const <> 0

所以10*n + 100 = O(n)和0.1*n = O(n)。

正如你写的，下一条语句也是正确的： O(n/8) = O(n) = O(n/const)

Answer 2

这里还有另一个误解：为了真正制作一个具有 O(1) 属性的“字符容器”（分别为：O(log n)，因为所需的内存仍然随着数据的增长而增长），这只适用于: 包含n个一种字符和1个另一种字符的字符串。

在这种情况下，是的，您只需要记住具有不同字符的索引。这类似于定义一个超级稀疏矩阵：如果在一个巨大的矩阵中只有一个值是 != 0，则您可以只存储相应的索引而不是整个矩阵，其中包含无数个 0 值。

当然：有些库可以为稀疏矩阵执行此类操作，以降低将已知 0 值保留在内存中的成本。当您可以（轻松）计算某些东西时，为什么还要记住它？！

Answer 3

我不确定您是否完全理解 Big O 的概念，但是在列出的每个案例中您仍然有 N 个元素。

该符号O(N)是 N 个元素的函数的上限，而不是由底层数据类型的大小定义，因为如上所述O(N/8) = O(N)。

所以，例如，

如果我们有一个包含真假的 N 数组并将其转换为字节

您正在将 N 个元素转换为 N 个字节。这是O(N)时间复杂度。您存储了2 * O(N)全部数组，从而导致O(N)空间复杂性。

charAt(i)

仅此操作就是O(1)时间复杂度，因为您正在访问一个元素。但是你有N数组或字符串中的元素，所以它是O(N)空间复杂度

我不太确定是否有一个通用的O(1)空间复杂度算法（除了简单的数学运算）