Java中List<List<Integer>>嵌套结构的空间复杂度是多少？

• 首先明确：仅靠方法返回值的类型声明，根本无法确定固定的空间复杂度。空间复杂度计算的是数据结构实际持有数据的内存规模随数据量增长的量级，和你声明的类型没有绝对绑定关系：如果方法最终返回的是空嵌套列表，整体空间复杂度就是O(1)，和N*M没有任何关系。
• 大家常说的嵌套列表O(NM)空间复杂度，是有明确前提的：外层List共持有N个独立的内层List实例，且所有内层List存储的Integer元素总规模稳定在NM量级（最典型的场景就是用嵌套列表存储N行M列的二维矩阵）。
  这种场景下，不管你用嵌套ArrayList、还是原生int[][]二维数组，渐进空间复杂度都是O(NM)。ArrayList本身的对象头、内部数组引用、size计数这些固定属性，还有扩容时预留的冗余数组空间，都属于常数级的系数开销，在大O复杂度分析中会被直接忽略，不会改变最终的复杂度阶数——哪怕每个内层ArrayList因为扩容多留了50%的空余容量，总内存规模依然是NM的常数倍，不会升阶也不会降阶。
• 以下场景的空间复杂度就不是O(N*M)，不要硬套公式：
  • 如果外层List的N个位置存的都是同一个内层List的引用（没有创建N个独立的内层列表），实际只存储了M个整数，总空间规模是O(N + M)，远小于N*M量级。
  • 如果内层List长度不一致，比如外层第i个内层列表的长度为i，总元素量是N*(N+1)/2，此时渐进复杂度是O(N²)，不存在固定的M值。
  • 如果是稀疏存储场景，绝大多数内层List是空列表，总共只存了K个整数，总空间复杂度就是O(K)，和N、M的名义大小无关，比如用嵌套列表存图的邻接表时，空间复杂度就是O(节点数+边数)，和节点数平方的邻接矩阵规模完全无关。
• 额外提一句：如果是做精确到字节的实际内存测算，嵌套ArrayList确实会比原生二维数组占更多内存：每个ArrayList实例有固定的对象开销、每个内层列表的扩容冗余空间、Integer装箱对象的对象头开销，这些都会让实际内存数值变大，但这些都是常数系数差异，不会影响大O表示的渐进复杂度结论。

内容的提问来源于stack exchange，提问作者kxnyshk