Java中log n次while循环内声明数组的空间复杂度判定
该循环场景的空间复杂度判定
该实现下的空间复杂度为O(1),具体判定逻辑如下:
空间复杂度的核心统计规则
空间复杂度计算的是算法运行全流程中同一时刻的最大内存占用峰值,而非整个运行周期累计消耗的内存总和;统计时会剔除已经失去所有有效引用、无法被访问的内存块,不管这些内存块是被GC及时回收,还是暂时驻留堆中等待后续回收。
结合场景的细节拆解
- 循环内创建的长度为2的数组属于块级局部变量,作用域仅覆盖当前这一次循环迭代:当本轮循环代码执行完毕,指向该数组的局部引用就会从栈上移除,数组本身成为无引用的可回收对象。
- 内存占用不会随循环次数叠加:哪怕循环总执行次数达到log n次,每一轮进入循环创建新数组时,都会覆盖上一轮迭代遗留的数组引用,旧数组和新数组不会同时驻留在内存中形成占用叠加。同一时刻最多只会存在1个长度为2的数组,对应的内存大小是和输入规模n无关的固定常数。
- 明确和O(log n)空间复杂度的边界:只有当循环中创建的数组被存入全局列表、全局栈结构等长期持有引用的容器,所有历史创建的数组都无法被回收,内存占用会随循环次数增长到log n * 单数组大小,这种场景才会达到O(log n)的空间复杂度。
参考代码逻辑:
while (high > low) { int[] arr = arrFunc(mid, 0); }
补充提示:不要把GC的回收能力作为影响判定的变量——哪怕Java GC完全不主动回收内存,等整个方法退出才统一清理堆内存,块级作用域的规则也保证了旧数组从被覆盖引用的时刻开始就成为不可达对象,不会造成log n个数组同时占满内存的情况。
内容的提问来源于stack exchange,提问作者Matan Amitai
相关产品推荐
相关产品推荐

