Может кто-нибудь сказать мне время Big O моего вида алгоритма? - PullRequest
Новая
       12

Может кто-нибудь сказать мне время Big O моего вида алгоритма?

0 голосов
/ 18 февраля 2019

Я не очень хорошо запоминаю все разные алгоритмы, поэтому я реализовал один, но я не уверен, как рассчитать время Big O для него, потому что есть движущийся указатель.

Это не очень эффективно, или, по крайней мере, есть лучшие виды.

Он сортирует массив на месте, перемещая указатель назад и вперед, начиная с позиции 0 и двигаясь вправо, и один раз назад каждый раз, когда происходит свопинг, чтобы увидеть, находится ли элемент слеватоже нужно изменить.

Вот код: 

function countInversions(arr) {
  var count = 0;
  var i=0;

  while(i < arr.length) {
    // look behind
    if (i-1 >= 0 && arr[i-1] > arr[i]) {
      swap(arr, i, i-1);
      count++;
      i--;
      continue;
    }    
    // look ahead
    else if (arr[i] > arr[i+1]) { 
      swap(arr, i, i+1);
      count++;
      continue;
    }

    i++;
  }

  return count;
}

function swap(arr, i1, i2) {
  const temp = arr[i2];
  arr[i2] = arr[i1];
  arr[i1] = temp;
}

edit: похоже на «Bubble Sort».Я до сих пор не уверен, что такое биг-о.

1 Ответ

0 голосов
/ 19 февраля 2019

Ваша сортировка действительно пузырьковая, но вы просто переместили маленький элемент на первый, а не на большой.

Для алгоритмов сортировки сложность обычно принимается за худшее, лучшее и среднееслучаев.Лучший вариант в вашей реализации (пузырьковая сортировка) - это когда массив уже отсортирован, а сложность будет O (n).Но худшее и среднее значение O (n ^ 2)

Кстати, я заметил, что вы подсчитали количество операций свопинга, просто хотел упомянуть, что вы должны учитывать количествоциклы в терминах больших О. вычислений.Однако это полностью зависит от вашей платформы и требований, и если, например, сканирование массива почти не требует времени, а замена элементов стоит больше времени на вашей платформе, тогда подсчет свопов имеет смысл.

Я также хотел бы порекомендовать некоторыеУлучшения в вашем алгоритме:

Перед перемещением элемента влево вы можете сохранить текущую позицию и, как только она уляжется, просто вернитесь назад и продолжите с того места, где он был раньше.См. Модифицированный код ниже.

В любом случае сложность времени не изменится, и все равно она будет равна O (n ^ 2), но даст вам небольшое улучшение. 

function countInversions(arr) {
  var count = 0;
  var i=0;
  var old_i=-1;

  while(i < arr.length) {
    count++;
    // look behind
    if (i-1 >= 0 && arr[i-1] > arr[i]) {
      swap(arr, i, i-1);
      if (old_i<0)
        old_i=i;
      i--;
      continue;
    }    
    // look ahead
    else if (arr[i] > arr[i+1]) { 
      swap(arr, i, i+1);
      continue;
    }

    if (old_i>0){
      i=old_i;
      old_i=-1;
    }
    i++;
  }
  return count;
}

function swap(arr, i1, i2) {
  const temp = arr[i2];
  arr[i2] = arr[i1];
  arr[i1] = temp;
}
...