while循环为什么不为总时间复杂度贡献O（n）？

Question

我从采访位上得到了这个问题

问题

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

题

while循环执行的比较总数约为n（取决于，可能小于或等于n arr）。循环运行n次。时间复杂度不应该是O（n ^ 2）吗？

Answer 1

while循环中的条件之一是while j < n。这意味着最坏的情况，无论外部循环执行多少次循环，代码都只会在while循环n时间内for循环（j从零开始，仅增加，从不重置为零或减少）。由于for循环也会循环n计时，因此您big-O的O(n+n) => O(n)

注意：您可以放心地忽略其他条件arr[i] < arr[j]，因为我们只是在考虑最坏情况下的运行时。