Transformer O(n^3) en O(n^2) en JavaScript

Question

J'essaie de comprendre comment gagner du temps dans ma solution de codage.

J'ai une fonction appelée tripletSum qui prend deux paramètres x y a donde x est un nombre et a est un tableau.

Cette fonction est censée renvoyer true si la liste a contient trois éléments dont la somme est égale au nombre x sinon il doit renvoyer false .

J'ai créé la solution suivante :

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;
}

Mais cela ne semble pas être la meilleure pratique. Actuellement, le temps nécessaire pour exécuter cette fonction est de O(n^3) si je ne me trompe pas et je pense qu'il peut être amélioré pour avoir une complexité temporelle de O(n^2) .

Comment puis-je modifier ce code pour qu'il fasse cela ?

Edita: Il ne s'agit pas d'un doublon de l'autre question car je demandais une amélioration spécifique de mon exemple actuel en JavaScript, ce qui n'est pas ce qui était demandé dans la question marquée comme doublon.

Answer 1

Conserve un objet de type dictionnaire pour toutes les clés contenues dans le tableau. Ensuite, dans votre deuxième boucle, vous soustrayez les deux valeurs de x et recherchez cette valeur dans votre dictionnaire.

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;
}

Answer 2

Voici l'idée : il faut d'abord trier le tableau a . Ensuite, vous pouvez avoir une boucle qui parcourt tous les éléments de 0 à N - 2 (exclusivement). Appelons cette boucle i l'index de cette boucle. C'est ici qu'intervient l'utilité du fait que le tableau est trié. Nous allons utiliser le fait que le tableau est trié pour "presser" le sous-réseau "non traité" (de i + 1 au N-ième élément). Vous aurez maintenant 2 valeurs left y right . left indiquera l'indice gauche du sous-réseau non traité, tandis que right indiquera l'indice de droite de la partie non traitée du tableau. Au début, nous définissons left = i + 1 y right = N - 1 . Nous calculons la sum a[i] + a[left] + a[right] . Nous avons maintenant trois cas :

1. If sum = x alors retourner vrai
2. Si sum > x il faut alors diminuer la somme, et donc décrémenter right par 1 (en partant de la droite)
3. Si sum < x alors nous devons augmenter la somme, donc nous devons incrémenter left por 1 (de gauche à droite)

Voici la solution en 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;
}

La complexité temporelle est la suivante O(N^2) et aucun espace supplémentaire n'est utilisé.

Answer 3

Vous pouvez essentiellement utiliser la recherche binaire et un tri pour réduire la complexité à O(n^2*logn) au lieu de 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
]))

Complexité totale = O(n*logn) + O(n^2*logn) ~ O(n^2*logn)