这段代码的时间复杂度是多少？为什么？

Question

以下代码的时间复杂度为O(n)。但为什么呢？

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

Answer 1

控制通过外环n次。

控制最多通过内循环n次。那不是n次为每次通过外环，它是n次，最多总。