以下代码的时间复杂度是多少? [英] What is time complexity for the following code?

问题描述

看起来下面代码的复杂度应该是 O(n^2) 但它是 O(n)，怎么办?

It seems the complexity of the following code should be O(n^2) but it's O(n), how?

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

推荐答案

j 不会随着外循环的每次迭代重置为 0.因此，它只运行到 n-1 一次，与 i 一样.因此，您有两个从 0 到(最多)n-1 的并行/混合迭代.

j is not reset to 0 with every iteration of the outer loop. As such, it runs to n-1 just once, same as i does. So you have two parallel/intermingled iterations from 0 to (at most) n-1.

在每一步，程序将i加一.当 i 到达 n 时程序终止.外循环"运行 n 次.

In every step, the program increases i by one. The program terminates when i reaches n. The "outer loop" is run n times.

还有一个关于 j 的内循环".但它所做的只是增加 j 直到它达到 i(最多，有时它做的更少).j 永远不会减少.因此，该部分最多总共运行 n 次(不是外循环"的每次迭代的 n 次).

There is also an "inner loop" about j. But all it does is increase j until it reaches i (at most, sometimes it does less). j is never decreased. So that part is also run at most n times in total (not n times for each iteration of the "outer loop").

这篇关于以下代码的时间复杂度是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！