java - 重置绑定(bind)时 while 循环的时间复杂度？

Question

我有一个 while 循环，它使用索引“i”迭代数组，并且仅执行 O(1) 操作。如果边界 j 可能会递减以将 j 处的元素与 i 处的当前元素进行比较，那么我希望能够在 j < i 时继续迭代数组，但 i 不等于数组的长度 - 1。如果我将 j 重置为数组长度的初始界限 - 1，while 循环的复杂度仍然是 O(n) 吗？

示例(Java 语言):

i = 0;
j = array.length - 1;

while(i < j) {

  ...

  if (j < i) {

    j = array.length - 1;

  }

  i = i + 1;

}

Answer 1

这是因为条件j < i永远不会为真(至少对于大于零的数组长度而言)。

想象一下您从 j = 1, 开始那么你只有一次迭代，其中 i 的值仅增加一次，导致表达式 i < j在下一次迭代中求值为 false(此处 i 的值为 1)，从而中断循环。

这适用于任何高于 j = 1 的情况也是如此(除非溢出)。

还有关于大学内容的另一个提示:尝试一下。要么手动检查，要么将 println 调用添加到源代码中。通过示例比过度思考抽象数字要容易得多。