两个 for 循环的 O(f(n))

Question

第一个循环会给出 O(n)，但第二个循环会永远运行，不是吗？这是否意味着整体 O(n) 只是 O(n) 还是内部 for 循环算作不仅仅是一个常数？

for (int i=0; i<n; i++) {
  for (int j=0; j<=42; j--) {
    System.out.println(i+j);
  }
}

Answer 1

System.out.println表示这是Java。

在Java中，int类型为32位有符号整数类型，取值范围为-2,147,483,648到2,147,483,647。减少已经处于最小值的变量会将其环绕到最大值。

这意味着在变量 j 回绕、变得大于 42 并终止内循环之前，内循环将运行迭代 2,147,483,648 次。因此，内部循环不是无限的，如问题中所示，而是有限且恒定的。

由于内循环总是执行这么多步骤，所以它是恒定的，因此 big-o 符号完全由外循环决定。

所以这段代码的 big-o 表示法是 O(n).

如果可以将 compiler/runtime 配置为在您尝试对 int 进行下溢时崩溃，而不是将其回绕，程序将始终崩溃，并且它将设法仅运行在内循环结束时崩溃之前外循环的 1 次迭代。因此它将是 O(1)。但是，我了解的不够Java，所以我不知道这是否可行。

如果不是 Java，这应该是在另一种理论编程语言的上下文中，或者被视为纯算法描述，其中 int 实际上没有下限, 然后程序不会终止，实际上 根本没有 大 O 符号。

关于最后一段的更多信息：O-notation, O(∞) = O(1)?。

O(f(n)) for two for loops