Временная сложность алгоритмов с использованием двух указателей: 0 (n) или 0 (n ^ 2)

Question

Итак, это проблема.

Учитывая массив целых чисел, вернуть новый массив, где каждый элемент в новом массиве - это количество меньших элементов справа от этого элемента в исходном входном массиве .

Например, для массива [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

I придумал этот алгоритм с двумя указателями.

 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, время l oop прерывается). В соответствии с тем, что я знаю о временной сложности. Я предполагаю, что мы go через массив только один раз, когда это O (n). Но не должны ли мы учитывать тот факт, что существует n сравнений, сделанных по отношению к j, когда мы go проходим через? Я новичок в соревновательном программировании и нотации Big O. Пожалуйста, помогите мне.

Спасибо.

Answer 1

Вы можете изменить свой код на

 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 l oop выполняется arr.length ² раз, поскольку i увеличивается не на каждой итерации, а только когда j == 1.

Из моей обновленной версии это не только ясно видно, что код O(n²), но также и то, что он неправильный: j !== 1 (или j > 1) следует сравнивать с i вместо 1 - вы хотите посчитать только элементы справа.

Answer 2

Это O (n²) , вы увеличиваете i каждые len(arr) итераций, и так до тех пор, пока i не достигнет len(arr).

Это дает сложность в len(arr) * len(arr) т.е. O (n²).