为什么这段代码的时间复杂度是O(N)？

Question

我认为下面代码的时间复杂度是 O(n^2) 或 O(n*logn)。

int j = 0;

for(i = 0; i < n; ++i) {
    while(j < n && arr[i] < arr[j]) {
        j++;
    }
}

然而，答案页说它是 O(n)。
搞不懂为什么会变成这样
我的（愚蠢的）意见如下：

时间复杂度为O(n^2)，因为有两次循环运行ning n次。 arr[i] < arr[j] 可能会影响 while 循环，但没关系。
时间复杂度为 O(n*logn) 因为 while 循环可能运行少于 n 次因为 arr[j] 可以小于 arr[i] 期间环形。结果，while 循环将运行进行 log(n) 次。

你能解释一下为什么我的答案是错误的以及为什么正确的时间复杂度是 O(n) 吗？

Answer 1

一般来说，要理解这样的流程，尝试添加打印语句来理解流程，在每个点打印 'i' 和 'j'。

在这种特定情况下，您知道外层 for 循环被触发了多少次，但尝试查看总次数 j 可以递增多少次。即使它在 for 循环内，它的总迭代次数可能是独立的。

Answer 2

for(i = 0; i < n; ++i)

循环 n 次。

while(j < n && arr[i] < arr[j]) {
    j++;
}

总共循环 n 次。请注意，j 只会在 i 的整个循环中递增，因此它是一个内部循环并不能使它成为更高阶的，因为它仍然只能从 0 到n 用于整个循环集。

所以是 O(2n) = O(n)

Why is the time complexity of this code O(N)?