引用单个数组的数组数组的内存使用情况？

Question

假设在 Python3 中我有一个大小为 N 的数组和一个包含 N 个数组的数组。

a = []
b = []

for i in range(N):
  a.append(i)

for i in range(N):
  b.append(a)

每个 b[i] 现在引用同一个数组 a。我认为这仍然是 O(N) 内存，因为当我访问数组时，我实际上是在访问对内存块的引用，因此每个 b[i] 都保持常量 space 内存（a 的地址）和array a 拥有 O(N) 内存，所以这应该是 O(N) 内存，而不是 O(N^2) 如果 b 中的每个 N^2 单元格都拥有一个独立值。这是正确的吗？

Answer 1

是的，这是正确的。 a 的大小是 O(n)，并且 b 持有 N 个引用 到 a 的相同实例。总的来说，内存复杂度是O(n)。

Answer 2

是的，对于所有实际用途来说都是 O(N)。 a 包含 N 对 int 对象的引用，b 包含 N 对 a 的引用。那是 2N 个参考文献。

从技术上讲，a 引用的每个 int 对象使用的内存量是 N 的函数，但因为它大约是 24 + O(log_{2**32} N) 字节每个 int 对象，隐藏常量是如此之小，以至于只有当 N 是天文数字时（大于您可能能够负担或寻址的任何内存量）才会有所不同。

另一方面，列表的长度也限制在 sys.maxlen 个元素，这意味着在某种意义上所有列表都使用 O(1) 内存（具有非常大的常量）。 :)

引用单个数组的数组数组的内存使用情况？

Memory usage of an array of arrays referencing a single array?

python

python-3.x

space-complexity