使用两个 pointers.Is 0(n) 或 0(n^2) 的算法的时间复杂度

Question

这就是给出的问题。

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

例如，给定数组 [3, 4, 9, 6, 1], return [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 循环中断）。根据我对时间的了解 complexity.I 猜测我们只遍历数组一次是 O(n)。但是我们不应该考虑这样一个事实，即在我们进行的过程中有 'n' 与 'j' 的比较吗？我是竞争性编程的新手，Big O notation.Please 帮助我。

谢谢。

Answer 1

它是 O(n²)，每 len(arr) 次迭代增加 i，直到 i 达到 len(arr).

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

Answer 2

您可以将代码重新排列为

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

是的，您巧妙地将嵌套循环合并为一个循环，但这并没有改变它的复杂性。请注意，在您的版本中，while 循环运行 arr.length ² 次，因为 i 不会在每次迭代时递增，而只会在 j == 1.

时递增

从我的更新版本来看，不仅可以清楚地看到代码是 O(n²)，而且它是错误的：j !== 1（或 j > 1）应该与 [=13= 进行比较] 而不是 1 - 你只想计算右边的元素。

使用两个 pointers.Is 0(n) 或 0(n^2) 的算法的时间复杂度

Time complexity of algorithms using two pointers.Is it 0(n) or 0(n^2)

javascript

algorithm

big-o

time-complexity