java - 恒定时间/空间复杂度概念的混淆

Question

我对恒定时间/空间复杂度的概念感到困惑。

例如:

public void recurse(int x) {
    if(x==0) return;
    else recurse(x/10);
}

其中，1

如果我们想用大O表示法来表达这个函数的空间复杂度，并计算递归的堆栈空间，空间复杂度是多少？

我很困惑:

1. O(1) - java 中 int 的最大值为 2147483647，因此最多会递归 10 次。
2. O(log x) - 递归次数实际上取决于 x 中的位数，因此最多我们将有 ~log₁₀x 递归。

如果我们说它是 O(1)，那么任何具有有限输入的算法是否可以将其时间/空间复杂度限制在某个数字范围内？因此，让我们以 java 中的数字数组中的插入排序为例。 Java 中可以拥有的最大数组的大小为 2147483647，那么这是否意味着 T(n) = O(2147483647²) = O(1)？

或者我应该把它看成 O(1) 是一个松边界，而 O(log x) 是一个更紧的边界？

这是我在维基百科上找到的定义:

如果 T(n) 的值受一个不依赖于输入大小的值的限制，则该算法被称为常数时间(也写为 O(1) 时间)。例如，访问数组中的任何单个元素都需要常数时间，因为只需执行一个操作即可定位它。同理，在升序排列的数组中寻找最小值；它是第一个元素。然而，在无序数组中找到最小值并不是一个恒定时间的操作，因为需要扫描数组中的每个元素才能确定最小值。因此它是一个线性时间操作，需要 O(n) 时间。但是，如果预先知道元素的数量并且不改变，那么这样的算法仍然可以说是在恒定时间内运行。

Answer 1

在分析算法的时间和空间复杂度时，我们不得不忽略物理计算机的一些局限性；复杂度是“输入大小”n 的函数，在大 O 表示法中，它是一个渐近上限，因为 n 趋于无穷大，但是物理计算机当然不能为任意大的 n 运行算法，因为它具有有限的内存和其他存储空间。

因此，为了以有意义的方式进行分析，我们在一种假想的计算机上分析算法，其中数组的长度没有限制，其中整数可以“足够大”以供算法运行，等等.您的 Java 代码是该算法的具体实现，但该算法作为抽象概念存在，超出了 Java 在实际计算机上可能实现的范围。所以在没有这种限制的假想计算机上运行这个抽象算法，空间复杂度是 O(log n)。

这种“想象中的计算机”听起来可能有点模糊，但它是可以进行数学形式化以进行严格分析的东西；它被称为model of computation .在实践中，除非你正在进行学术研究，否则你不需要那么严格地分析算法，因此适应更模糊的概念更有用，即你应该忽略任何会阻止算法在任意大输入上运行的限制.