Это частичный комментарий, частичный ответ.
В инженерном плане опубликованная исходная функция использует "грубую силу" для решения проблемы, повторяя каждую (или более чем необходимую) возможную комбинацию. Число итераций n велико - если бы вы сделали все возможное, это было бы
n * (n-1) = bazillio n
Меньше - больше
Итак, давайте рассмотрим вещи, которые можно оптимизировать, сначала некоторые мелочи, я немного запутался в первом цикле for
и nArray
:
// OP's code
for(let i = 1; i <= n; i++) {
nArray.push(n - (n - i));
sum += i;
}
??? Вы действительно не используете nArray
для чего-либо? Length
это просто п ... я так лишен сна, что-то упустил? И хотя вы можете суммировать последовательную последовательность целых чисел 1-n
с помощью цикла for
, существует прямой и простой способ избежать цикла:
sum = ( n + 1 ) * n * 0.5 ;
ПЕТЛИ
// OP's loops, not optimized
for(let i = Math.round(n/2); i < length; i++) {
for(let y = Math.round(n/2); y < length; y++) {
if(i != y) {
if(i*y === sum - i - y) {
Особенности оптимизации:
Я вижу, что вы на правильном пути в некотором смысле , сокращая начальные значения i, y
пополам с учетом факторов. Но вы перебираете их обоих в одном направлении: UP. Кроме того, нижние числа выглядят так, как будто они могут доходить чуть ниже половины от n (возможно, не потому, что последовательность начинается с 1, я не подтвердил это, но, похоже, это так).
Кроме того, мы хотим избегать деления каждый раз, когда начинаем создание экземпляра цикла (т.е. устанавливаем переменную один раз, а также собираемся ее изменить). И, наконец, с помощью операторов IF, i и y никогда не будут равны друг другу, как мы собираемся создавать циклы, так что это условие может исчезнуть.
Но более важным является направление прохождения петель . Меньший коэффициент low
, вероятно, будет близок к самому низкому значению цикла (около половины от n), а больший коэффициент hi
равен , вероятно , будет около значения n. Если у нас есть какая-то основательная математическая теория, которая говорит что-то вроде «привет, никогда не будет меньше 0,75n», то мы могли бы сделать пару модов, чтобы воспользоваться этими знаниями.
То, как показаны циклы ниже, они ломаются и повторяются до того, как встречаются циклы hi и low.
Более того, не имеет значения, какой цикл выбирает меньшее или большее число, поэтому мы можем использовать это для сокращения внутреннего цикла при проверке пар чисел, делая цикл каждый раз меньше. Мы не хотим тратить время на проверку одной и той же пары номеров более одного раза! Цикл с более низким коэффициентом начнется чуть ниже половины n и увеличится, а цикл с более высоким коэффициентом начнется с n и опустится.
// Code Fragment, more optimized:
let nHi = n;
let low = Math.trunc( n * 0.49 );
let sum = ( n + 1 ) * n * 0.5 ;
// While Loop for the outside (incrementing) loop
while( low < nHi ) {
// FOR loop for the inside decrementing loop
for(let hi = nHi; hi > low; hi--) {
// If we're higher than the sum, we exit, decrement.
if( hi * low + hi + low > sum ) {
continue;
}
// If we're equal, then we're DONE and we write to array.
else if( hi * low + hi + low === sum) {
answersArray.push([hi, low]);
low = nHi; // Note this is if we want to end once finding one pair
break; // If you want to find ALL pairs for large numbers then replace these low = nHi; with low++;
}
// And if not, we increment the low counter and restart the hi loop from the top.
else {
low++;
break;
}
} // close for
} // close while
Учебник
Итак, мы установили несколько переменных. Обратите внимание, что low установлено чуть меньше половины n, так как большие числа выглядят так, как будто они могут быть на несколько пунктов меньше. Кроме того, мы не округляем, мы усекаем, что, по сути, «всегда округляет вниз» и немного лучше для производительности (хотя в данном случае это имеет значение только с одним назначением).
Цикл while начинается с самого низкого значения и увеличивается, возможно, вплоть до n-1. Цикл hi FOR начинается в n (копируется в nHi), а затем уменьшается до тех пор, пока коэффициент не будет найден, ИЛИ не перехватывает при низком + 1.
Условия:
Первый IF: Если мы выше суммы, мы выходим, уменьшаем и продолжаем с более низким значением для фактора hi.
ИЛИ ЕСЛИ: Если мы РАВНЫ, то мы закончили и перерыв на обед. Мы устанавливаем low = nHi, чтобы при выходе из цикла FOR мы также выходили из цикла WHILE.
ELSE: Если мы попадаем сюда, это потому, что мы меньше суммы, поэтому нам нужно увеличить цикл while и сбросить цикл hi FOR, чтобы снова начать с n (nHi).