以下的时间复杂度是多少？

Question

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

谁能更直观地解释一下它的时间复杂度？

Answer 1

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

在给定的代码中，变量 j 的值在两个循环之外都被初始化为 0。在内部循环中，变量 j 的值总是递增。如果 arr[i] < arr[j] 则 j 的值增加 1 否则内部循环的内容将不会被执行。请注意，j 的值永远不会超过 n。因此，给定代码片段的复杂度总是 O(n)。