英文:
Time complexity of while loop when bound is reset?
问题
我有一个使用索引“i”遍历数组的while循环，只执行O(1)的操作。如果可能将bound 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;
}
英文:
I have a while loop that iterates through an array using the index "i" and only performs O(1) operations. If perhaps the bound j is decremented to compare an element at j with the current element at i, I want to be able to continue iterating through the array if j < i, but i does not equal the length of the array - 1. If I reset j to its initial bound of length of array - 1, would the while loop still be O(n) complexity?
Example (in Java):
i = 0;
j = array.length - 1;
while(i < j) {
...
if (j < i) {
j = array.length - 1;
}
i = i + 1;
}
答案1
得分: 0
This is because the condition j < i is never true (at least not for an array length which is greater than zero).
Imagine you start with j = 1, then you have only one iteration, where i's value is only incremented one time, causing the expression i < j to evaluate to false in the next iteration (i's value is 1 here) and therefore breaking the loop.
This applies for any case higher than j = 1 as well (unless overflow).
And another hint for university stuff: Just try it out. Either by going through it by hand or by adding println calls to the source code. It's much easier to do by example than by overthinking abstract numbers.
英文:
This is because the condition j < i is never true (at least not for an array length which is greater than zero).
Imagine you start with j = 1, then you have only one iteration, where i's value is only incremented one time, causing the expression i < j to evaluate to false in the next iteration (i's value is 1 here) and therefore breaking the loop.
This applies for any case higher than j = 1 as well (unless overflow).
And another hint for university stuff: Just try it out. Either by going through it by hand or by adding println calls to the source code. It's much easier to do by example than by overthinking abstract numbers.
专注分享java语言的经验与见解，让所有开发者获益！
评论