Изменение O (n ^ 3) на O (n ^ 2) в JavaScript [дубликат]

    

На этот вопрос уже есть ответ здесь:

    

Я пытаюсь сэкономить время в своем решении для кодирования.

У меня есть функция с именем tripletSum, которая принимает два параметра x и a где x - это число, а a - это массив.

Эта функция должна возвращать true, если список a содержит три элемента, которые складываются в число x, в противном случае должно возвращаться false

Я создал следующее рабочее решение:

function tripletSum(x, a) {
    for(var i = 0; i < a.length; i++) {
        for(var j = i + 1; j < a.length; j++) {
            for(var k = j + 1; k < a.length; k++) {
                if((a[i] + a[j] + a[k]) === x) {
                    return true;
                }
            }
        }
    }
    return false;
}

Но это не лучшая практика. В настоящее время для выполнения этой функции требуется время O(n^3), если я не ошибаюсь и думаю, что можно улучшить время сложность O(n^2).

В любом случае, я могу изменить этот код, чтобы сделать это?

Изменить . Это не дубликат другого вопроса, потому что я просил внести конкретное усовершенствование в мой текущий пример в JavaScript, который отличается от того, что было задано в отмеченном дублирующем вопросе.

7 голосов | спросил Barry Michael Doyle 13 J0000006Europe/Moscow 2017, 00:13:05

3 ответа


0

Вот идея: сначала нужно отсортировать массив a. После этого вы можете иметь один цикл, который перебирает все элементы от 0 до N - 2 (исключительно). Давайте назовем i индексом этого цикла. Здесь приходит полезность того факта, что массив отсортирован. Мы будем использовать знание о том, что массив отсортирован, чтобы «сжать» «необработанный» подмассив (диапазон от i + 1 до N-го элемента). Теперь у вас будет 2 значения: left и right. left будет указывать левый индекс необработанного подмассива, а right будет указывать правильный индекс этой необработанной части массива. В начале мы устанавливаем left = i + 1 и right = N - 1 , Мы вычисляем sum a[i] + a[left] + a[right]. Теперь у нас есть 3 случая:

  1. If sum = x и верните true
  2. Если sum > x, тогда нам нужно уменьшить сумму, поэтому нам нужно уменьшить right на 1 (нажать справа)
  3. Если sum < x, тогда нам нужно увеличить сумму, поэтому нам нужно увеличить left от 1 (нажмите слева)

Здесь следует решение Javascript.

function tripletSum(x, a) {
    a.sort(function(i, j) {
        return i - j;
    });

    var N = a.length;

    for(var i = 0; i < N - 2; i++) {
        var left = i + 1, right = N - 1;

        while(left < right) {
            var sum = a[i] + a[left] + a[right];
            if(sum === x) {
                return true;
            }
            else if(sum > x) {
                right--;
            }
            else {
                left++;
            }
        }

    }

    return false;
}

Сложность времени составляет O(N^2), и дополнительное пространство не используется.

ответил giliev 13 J0000006Europe/Moscow 2017, 01:12:50
0

Сохраняйте подобный словарю объект для всех ключей, содержащихся в массиве. Затем во втором цикле вычитаете два значения из x и ищите это значение в словаре.

function tripletSum(x, a) {
    var dictionary = {};
    for(var i = 0; i < a.length; i++) {
        dictionary[a[i]] = true;
    }

    for(var i = 0; i < a.length; i++) {
        for(var j = i + 1; j < a.length; j++) {
            var remainder = x - a[i] - a[j];
            if(dictionary[remainder])
                return true;
        }
    }
    return false;
}
ответил Frederik Hansen 13 J0000006Europe/Moscow 2017, 00:16:07
0

Вы можете в основном использовать бинарный поиск и сортировку, чтобы уменьшить сложность до O (n ^ 2 * logn) от O (n ^ 3).

 function tripletSum(x, a) {
    a.sort(function(a, b) {
            return a - b
        }) // O(n*logn)
    var n = a.length;
    for (var i = 0; i < n; i++) {
        for (var j = i + 1; j < n; j++) {
            if (a.indexOf(x - a[i] - a[j]) > j) {
                return true; //O(n^2*logn)
            }
        }
    }
    return false;
}

console.log(tripletSum(0, [
    1,
    5,
    6,
    -2, 
    -3
]))

Общая сложность = O (n * logn) + O (n ^ 2 * logn) ~ O (n ^ 2 * logn)

ответил Piyush 13 J0000006Europe/Moscow 2017, 00:53:50

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132