算法空间复杂度与内存分配的关联，能否据此估算物理内存？

先看这段数组遍历的代码：

for (int i = 0; i < array.length; i++) {
    for (int j = 0; j < array.length; j++) {
        //print (i,j)
    }
}

你对空间复杂度的理解是对的：int i和int j属于常数级空间开销（O(1)），数组array的空间开销和长度成正比（O(n)，n为array.length）。但要估算实际物理内存大小，光靠空间复杂度不够，得结合具体细节：

• 局部变量的实际大小：i和j都是int类型，在绝大多数系统和JVM里，每个int固定占4字节，不管数组多大，这俩变量的内存都是固定的，对应O(1)的复杂度。
• 数组的实际内存：
  • 如果是基本类型数组（比如int[]），总内存是「数组对象头大小 + 元素大小×长度」。数组对象头在64位JVM里一般是16字节（开启压缩指针的话），每个int元素4字节，所以总大小大概是16 + 4*n字节。
  • 如果是引用类型数组（比如Object[]），每个引用在64位JVM里占8字节（开启压缩指针则4字节），再加上每个元素指向的对象本身的内存——这时候数组的内存只是一部分，还要算所有元素对象的总大小。
• 额外开销：比如JVM栈帧的固定开销（每个方法调用的栈帧里还有程序计数器、局部变量表等结构），这些也是固定的常数级开销，属于O(1)的部分。

总结下来：空间复杂度告诉你内存增长的趋势（比如数组越长，内存占用线性增加），但要算出精确的物理内存，你得明确：

• 运行环境的参数（JVM位数、是否开启指针压缩）
• 数组元素的具体类型和每个元素的大小
• 加上局部变量、对象头、栈帧这些固定开销

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