Большая O-временная эффективность для квадратичной функции в JavaScript - PullRequest
Новая
       42

Большая O-временная эффективность для квадратичной функции в JavaScript

0 голосов
/ 01 мая 2019

Я пытаюсь повысить эффективность функции.В настоящее время он квадратичный, и я хотел бы сделать его логарифмическим.

Третья-последняя строка текущей функции также несколько смущает меня, и я хотел бы получить некоторые пояснения. 

function solution(arr){
   let result = 0
    for ( let i = 0; i < arr.length; i++)
        for (let j = 0; j < arr.length; j++)
            if (arr[i] == arr[j])
                result = Math.max(result, Math.abs(i - j));
         return result;
 }

Как мне решить эту проблему?

Ответы [ 2 ]

2 голосов
/ 01 мая 2019

По крайней мере, вы можете изменить индексы для зацикливания и пропустить самопроверку и снова проверить те же пары. 

function solution(arr){
    let result = 0
    for (let i = 0; i < arr.length - 1; i++)
        for (let j = i; j < arr.length; j++)
            if (arr[i] === arr[j])
                result = Math.max(result, Math.abs(i - j));
    return result;
}

Кратчайшим подходом является O (n) с использованием хеш-таблицы для хранения первого найденного индекса для значения. 

function solution(array) {
    var hash = {};
    return array.reduce(
        (m, v, i) => Math.max(m, i - (hash[v] = v in hash ? hash[v] : i)),
        0
    );
}

var array = [1, 3, 4, 5, 1, 3, 4, 5, 6, 2, 3];

console.log(solution(array));
0 голосов
/ 01 мая 2019

В приведенной выше функции цель состоит в том, чтобы найти максимальное число из массива.Теперь значение от третьей до последней строки, которое result = Math.max(result, Math.abs(i - j));, я разбью на две части, чтобы объяснить здесь,

Прежде всего, Math.abs(i-j) будет выполнено и предоставит абсолютное значение из разницы междуi и j.

После этого будет вызван метод внешней функции Math.max(), который предоставит вам максимальное значение между result и absolute value, полученное на первом шаге.Теперь максимальное значение будет храниться в result.Вот как работает эта функция.

Теперь этот оператор является условным, что означает, что он будет выполняться только в том случае, если arr[i]==arr[j].

Я надеюсь, что он очистил рабочий процесс этой программы.

...