提问人：kxnyshk 提问时间：7/9/2022 最后编辑：kxnyshk 更新时间：7/9/2022 访问量：448
Java 中 ArrayList 的 ArrayList 的空间复杂度是多少？
What would be the space complexity of an ArrayList of ArrayLists in Java?
问：
我有一个在 Java 中返回 List<List<Integer>> 的方法。这种数据结构的空间复杂性是什么？由于 ArrayList 中嵌套了 ArrayList，它会是 O（N*M） 吗？还是别的什么？
答：
2赞
Mureinik
7/9/2022
#1
你的想法是正确的，但可能需要稍微完善一下。
对于“外层”，空间复杂度为O（n），n是其中的元素数。
按照你的直觉，你应该把它乘以内部 s 的空间复杂度，这也是它们各自的大小。
但是，在没有任何附加信息或约束的情况下，您不应该假设内部和外部 s 具有相同的大小，因此在更一般的意义上，您想说如果内部列表中的元素数为 m，则总大小复杂度为 O（m * n）。如果 m=n（例如，每个索引表示一个位置，嵌套数组的“单元格”表示外部和内部映射的索引之间的距离），则 O（m * n） 确实将简化为 O（n2）。ArrayListArrayListArrayList
评论
0赞
Scott Hunter
7/9/2022
你不能把它简化为“如果总共有 N 个元素，那就是 O（N）”吗？
1赞
Mureinik
7/9/2022
@ScottHunter所有“内部”列表的总数放在一起？我想是的。但考虑到结构，我怀疑你永远不会这样计算它们。尽管这一切都归结为用例，以及您在此结构中实际存储的内容。
0赞
Scott Hunter
7/9/2022
但是，无论m&n有多“接近”，你的O（m*n）=我的O（N）不是吗？
0赞
Mureinik
7/9/2022
@ScottHunter是的，我们最终描述的是相同的大小 - 但最终 m 和 n 应该是在问题上下文中有意义的大小。如果元素总数“n”意味着什么，这就是你描述空间复杂度的方式，但如果内部和外部列表的实际大小意味着什么，你就会使用它们。
1赞
John
7/9/2022
#2
ArrayList 是动态数据结构，它比实际大小（元素数）增加了 50% 以上。所以实际上我们可以说它占用了 N+N/2 空间。 从复杂度原理来看，N 是最高度，所以 O（N）。 您有嵌套列表，内部列表决定了空间复杂度。 内部列表中的 n 个元素和 m 个内部列表中的元素都存在，因此总复杂度 O（n*米）
评论