在循环内声明新int变量是否会改变方法的空间复杂度？

请问在循环内部声明新的int变量是否会改变方法的空间复杂度？例如以下两个Java方法，它们的空间复杂度是否均为O(1)？还是第一个方法因反复声明变量c，空间复杂度为O(n)？

方法一（循环内声明变量c） #

public static int what (int []a) {
    int temp = 0;
    for (int i = 0; i < a.length; i++) {
        for (int j = i; j < a.length; j++) {
            int c = f(a, i, j); // 循环内声明变量c
            if (c % 2 == 0) {
                if (j - i + 1 > temp)
                    temp = j - i + 1;
            }
        }
    }
    return temp;
}

方法二（循环外声明变量c） #

public static int what (int []a) {
    int temp = 0;
    int c; // 循环外声明变量c
    for (int i = 0; i < a.length; i++) {
        for (int j = i; j < a.length; j++) {
            c = f(a, i, j);
            if (c % 2 == 0) {
                if (j - i + 1 > temp)
                    temp = j - i + 1;
            }
        }
    }
    return temp;
}

辅助方法f的实现 #

private static int f (int[]a, int low, int high)
{
    int res = 0;
    for (int i=low; i<=high; i++)
        res += a[i];
    return res;
}

结论与解释 #

两个方法的空间复杂度均为O(1)，循环内部声明int变量不会改变空间复杂度，原因如下：

• Java的局部变量存储在栈帧的局部变量表中，循环内声明的变量c，其作用域仅限于当前循环迭代。每次循环结束后，该变量占用的栈空间会被释放，下一次迭代时会复用这块空间，不会重复分配新的内存。
• 无论c是在循环内还是循环外声明，本质上都只占用固定大小的内存（Java中int类型占4字节），临时变量的总数量不会随输入规模n（数组a的长度）的变化而增加。
• 辅助方法f内部的变量同样是固定大小的局部变量，每次调用f时创建的栈帧大小固定，不会随n变化，因此f的空间复杂度也是O(1)，不会影响整体复杂度。

空间复杂度衡量的是算法运行时临时存储空间随输入规模的变化趋势，这里两个方法的临时内存占用始终是固定值，和输入规模无关，因此均为O(1)。

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