javascript - 使用两个指针的算法的时间复杂度。是0(n)还是0(n^2)

Question

这就是给出的问题。

给定一个整数数组，返回一个新数组，其中新数组中的每个元素都是原始输入数组中该元素右侧较小元素的数量。

例如，给定数组 [3, 4, 9, 6, 1]，返回 [1, 1, 2, 1, 0]，因为:

There is 1 smaller element to the right of 3
There is 1 smaller element to the right of 4
There are 2 smaller elements to the right of 9
There is 1 smaller element to the right of 6
There are no smaller elements to the right of 1

我想出了这个二指针算法。

 function lessThan(arr) {
  let results = [];
  let i = 0;
  let j = arr.length - 1;
  let count = 0;
  while (i < arr.length) {
    if (arr[i] > arr[j]) {
      count++;
    }
    j--;
    if (j === 1) {
      results.push(count);
      count = 0;
      i++;
      j = arr.length - 1;
    }
  }
  return results;
}

指针“i”将从开头开始，“j”将从结尾开始。如果 'j' 等于 1。'i' 增加，'j' 重置到末尾。这一直持续到'i'到达数组的末尾。(当'i'等于或大于arr.length时，while循环中断)。根据我对时间复杂度的了解。我猜我们只遍历数组一次，它是 O(n) 。但我们不应该考虑这样一个事实:在我们经历的过程中，对“j”进行了“n”次比较吗？我是竞争性编程和 Big O 表示法的新手。请帮助我。

谢谢。

Answer 1

它是O(n²)，您递增i每len(arr)迭代，依此类推，直到 i到达len(arr) .

这给出了 len(arr) * len(arr) 的复杂性即 O(n²)。