Что плохого в производительности моих решений Tape-Equilibrium для Codility? - PullRequest
Новая
       76

Что плохого в производительности моих решений Tape-Equilibrium для Codility?

1 голос
/ 05 февраля 2020

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

function solution(A) {
    let slice = A.slice(1,A.length);
    let firstSliceSum = A[0];
    let lastSliceSum = slice.reduce((a, b) => a + b);
    let smallestValue = Math.abs(firstSliceSum-lastSliceSum);
    for(let i=1;i<A.length-1;i++){
        let shift = slice.shift();
        firstSliceSum=firstSliceSum+shift;
        lastSliceSum=lastSliceSum-shift;
        let diff = Math.abs(firstSliceSum-lastSliceSum);
        if(diff<smallestValue)smallestValue=diff;
    }
    return smallestValue;
}

У него есть только одно для l oop, которое выполняет итерации элементов, не считая начальную функцию «уменьшить». Я видел похожие Java решения, которые должны пройти со 100%. Ссылка на вызов: https://app.codility.com/programmers/lessons/3-time_complexity/tape_equilibrium/

1 Ответ

1 голос
/ 05 февраля 2020

Несколько проблем здесь.

  • Как уже указывалось, вы используете shift() внутри al oop , который имеет временную сложность O (n) . в конечном итоге делая ваш код O (n 2 ).
  • Во-вторых, вы также рассматриваете первую сумму индекса 0, тогда как упомянутые ограничения говорят для любых 0 <<code>P

Цитирование из упомянутой там задачи:

Любое целое число P, такое, что 0

  • Так что вам придется рассчитывать от 1 до A.length-1.

Фрагмент: 

function solution(A) {
  let slice = A.slice(1, A.length);
  let firstSliceSum = A[0];
  let lastSliceSum = slice.reduce((a, b) => a + b);
  let smallestValue = -1;
  for (let i = 1; i < A.length; i++) {
    let diff = Math.abs(firstSliceSum - lastSliceSum);
    if (smallestValue == -1 || diff < smallestValue) smallestValue = diff;
    firstSliceSum += A[i];
    lastSliceSum -= A[i];
  }
  return smallestValue;
}

console.log(solution([3, 1, 2, 4, 3]));
  • В приведенном выше (правильный код) мы инициализируем smallestValue в -1, поскольку абсолютное значение не может go быть отрицательным.
  • В l oop мы избегаем .shift() и просто берем различия firstSliceSum и lastSliceSum.
  • Позже мы уменьшаем A[i] с lastSliceSum и добавьте его к firstSliceSum, поскольку нам нужно учитывать A[i] для следующего предстоящего разделения, и удалите его из правой части разделения.
...