2

内容

  1. 问题陈述
  2. 详细说明和示例
  3. 访问的资源
  4. 答案（发布时）
  5. 后续问题（按照他们的设想）

问题

在计算“空间（内存）复杂度”的大 O 样式符号时，如何考虑原始类型的大小？

详细说明和示例

如果我分配一个长度为 N 个元素的数组，并且每个元素都是一个 32 位整数，那么我大概分配了大约 N*32 位。据我了解，这种分配的内存复杂度被认为是 O(N)。

使用上面的示例，如果我将数组中的每个元素视为指向唯一链表的指针，其中链表的长度为 1（包含 1 个节点和一个空指针），并且该节点的数据段也是 32 -bit 整数，我现在显然正在分配：

  1. 32 位数组元素
  2. 32位链表数据
  3. 32位链表空指针

我的数组变成 O(3*32*N) 了吗？我知道这仍将被视为 O(N)，但正如您所看到的，在时间/内存权衡变得相关的情况下，知道差异是相关的（例如，我可以使用各种长度的链表和存储在元素中的头指针数组以延迟我必须动态调整数组大小的点，因为我只能延长链表 - 这会将插入操作摊销到 O(1)，但会大大增加内存复杂性，直到实际发生调整大小，其中链表将恢复为数组中的元素，因此消耗的内存大大减少）

已访问的资源：

Stack Overflow 上的相关问题：

内存使用对算法复杂性的影响

为什么 A* 的复杂性在内存中是指数级的？

维基书有以下说法：

http://en.wikibooks.org/wiki/Data_Structures/Asymptotic_Notation

此外，维基百科详细阐述了这个主题：

http://en.wikipedia.org/wiki/Big_O_notation

答案

后续问题

4

2 回答 2

0

大 O 表示法的目的是我们从来没有像O(32*N). 如果差异真的很重要，那么公认的约定是不使用大 O 表示法或说类似32*O(N).

于 2013-11-21T05:27:29.817 回答
0

我认为您的困惑源于对大 O 表示法的误解。如果你有一个 32 位整数数组，它肯定比一个指向包含 32 位整数的单例链表的指针数组占用更少的空间（可能是 3 或 4 倍，具体取决于你拥有的链表类型） ）。然而，渐近地说，这两种设置都需要 Θ(n) 内存，因为 Θ 表示法讨论了内存消耗的渐近增长率，并且这两种方法都需要与所使用的元素数量成线性比例的内存。

通常，当空间使用不同时，渐近空间复杂度用于对不同的方法进行排名。例如，从长远来看，空间复杂度为 Θ(n log n) 的数据结构总是比空间复杂度为 Θ(n) 的数据结构使用更多的空间。然而，空间复杂度为 Θ(n) 的两种不同数据结构可能具有截然不同的内存占用。例如，考虑标准动态数组和斐波那契堆之间的空间复杂度差异。两者都需要 Θ(n) 内存，但所需的实际内存有很大不同（斐波那契堆可能需要 8 - 12 倍以上的内存）。

希望这可以帮助！

于 2013-11-21T07:17:40.577 回答