二维数组扁平化操作的空间复杂度分析

这个操作的空间复杂度既不是你说的O(n*m)，也不是O(n)，准确来说是O(k)——其中k是原二维数组中所有元素的总个数。

具体分析： #

• 空间复杂度衡量的是算法额外占用的存储空间（不包含输入本身）。这里我们创建的新数组flat，其长度完全等于原二维数组所有元素的总数，它占用的空间直接由总元素数决定。
• 你提到的O(nm)（n为外层数组长度，m为最大内层数组长度）是原二维数组的「最大潜在元素数」，但实际元素数往往小于这个值（比如你的示例里，n=3，m=4，nm=12，但实际总元素数是9），用这个表述会高估空间需求，不够准确。
• 而O(n)更不合理，因为新数组的长度和外层数组的长度没有直接关联——示例中外层数组长度是3，但新数组长度是9，显然远大于n。

结合你的示例代码来看： #

原二维数组的元素总数是3+2+4=9，最终生成的flat数组长度就是9，额外占用的空间和这9个元素的规模正相关，所以空间复杂度为O(9)，当数组规模扩大时，就是O(k)（k为总元素数）。

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