Lorsque je m'intéressais à la performance des algorithmes, je suis tombé sur cette . Elle donne non seulement un aperçu de la façon dont se déroulent les entretiens dans les grandes entreprises technologiques, mais permet également de comprendre comment résoudre des problèmes algorithmiques de manière aussi efficace que possible.
Cet article sert d'accompagnement à la vidéo. J'y commente toutes les solutions présentées, ainsi que ma propre version de la solution en JavaScript. Les nuances de chaque algorithme sont également abordées.
Rappelons-le : pour tous les lecteurs de « Habr » — une réduction de 10 000 roubles lors de l'inscription à tout cours Skillbox avec le code promo « Habr ».
Skillbox recommande : Cours pratique .
Définition du problème
On nous donne un tableau trié et une valeur précise. On nous demande ensuite de créer une fonction qui renvoie true ou false, en fonction de la possibilité que la somme de n'importe quels deux nombres du tableau soit égale à la valeur donnée.
En d'autres termes, existe-t-il dans le tableau deux entiers x et y dont la somme est égale à la valeur spécifiée ?
Exemple A
Si nous avons le tableau [1, 2, 4, 9] et la valeur 8, la fonction renverra false, car aucun couple de nombres dans le tableau ne peut donner 8 en somme.
Exemple B
Mais si nous avons le tableau [1, 2, 4, 4] et la valeur 8, la fonction doit renvoyer true, car 4 + 4 = 8.
Solution 1. Brute force
Complexité temporelle : O(N²).
Complexité spatiale : O(1).
La solution la plus évidente consiste à utiliser une paire de boucles imbriquées.
const findSum = (arr, val) => {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length; j++) {
if (i !== j && arr[i] + arr[j] === val) {
return true;
};
};
};
return false;
};Cette solution ne peut pas être considérée comme efficace, car elle vérifie chaque somme possible de deux éléments dans le tableau et compare également chaque paire d'indices deux fois. (Par exemple, lorsque i = 1 et j = 2, cela équivaut en fait à comparer avec i = 2 et j = 1, mais dans cette solution, nous essayons les deux cas).
Comme notre solution utilise une paire de boucles for imbriquées, elle est quadratique avec une complexité temporelle de O(N²).
Solution 2. Recherche binaire
Complexité temporelle : O(Nlog(N)).
Complexité spatiale : O(1).
Étant donné que les tableaux sont triés, nous pouvons chercher une solution en utilisant la recherche binaire. C'est l'algorithme le plus efficace pour les tableaux triés. La recherche binaire en elle-même a un temps d'exécution de O(log(N)). Cependant, il est toujours nécessaire d'utiliser une boucle for pour vérifier chaque élément avec toutes les autres valeurs.
Voici à quoi pourrait ressembler la solution. Pour que tout soit clair, nous utilisons une fonction distincte pour gérer la recherche binaire. Ainsi qu'une fonction removeIndex (), qui renvoie la version du tableau sans l'index spécifié.
const findSum = (arr, val) => {
for (let i = 0; i {
return arr.slice(0, i).concat(arr.slice(i + 1, arr.length));
};
const binarySearch = (arr, val) => {
let start = 0;
let end = arr.length - 1;
let pivot = Math.floor(arr.length / 2);
while (start < end) {
if (val arr[pivot]) {
start = pivot + 1;
};
pivot = Math.floor((start + end) / 2);
if (arr[pivot] === val) {
return true;
}
};
return false;
};L'algorithme commence à l'index [0]. Ensuite, il crée une version du tableau, en excluant le premier index, et utilise la recherche binaire pour vérifier si l'on peut ajouter l'une des valeurs restantes dans le tableau pour obtenir la somme souhaitée. Cette action est effectuée une fois pour chaque élément du tableau.
En soi, la boucle for aura une complexité temporelle linéaire O (N), mais à l'intérieur de la boucle for, nous effectuons une recherche binaire, ce qui donne une complexité temporelle globale de O (Nlog (N)). Cette solution est meilleure que la précédente, mais il y a encore place à amélioration.
Solution 3. Temps linéaire
Complexité temporelle : O(N).
Complexité spatiale : O(1).
Maintenant, nous allons résoudre le problème en gardant à l'esprit que le tableau est trié. La solution consiste à prendre deux nombres : un au début et un à la fin. Si le résultat est différent de ce qui est requis, nous changeons le point de départ et le point d'arrivée.
En fin de compte, soit nous atteindrons la valeur recherchée et nous renverrons true, soit les points de départ et d'arrivée convergeront et nous retournerons false.
const findSum = (arr, val) => {
let start = 0;
let end = arr.length - 1;
while (start val) {
end -= 1;
} else if (sum < val) {
start += 1;
} else {
return true;
};
};
return false;
};Maintenant tout va bien, la solution semble optimale. Mais qui peut garantir que le tableau était ordonné ?
Et alors ?
À première vue, nous pourrions d'abord trier le tableau, puis utiliser la solution ci-dessus. Mais comment cela affectera-t-il le temps d'exécution ?
Le meilleur algorithme est le tri rapide avec une complexité temporelle de O (Nlog (N)). Si nous l'utilisons dans notre solution optimale, sa performance passera de O (N) à O (Nlog (N)). Pouvons-nous trouver une solution linéaire avec un tableau non trié ?
Solution 4
Complexité temporelle : O(N).
Complexité spatiale : O(N).
Oui, une solution linéaire existe, il faut créer un nouveau tableau contenant la liste des correspondances que nous cherchons. Le compromis ici est une utilisation de la mémoire plus active : c'est la seule solution dans l'article avec une complexité spatiale dépassant O (1).
Si la première valeur de ce tableau est 1 et que la valeur recherchée est 8, nous pouvons ajouter la valeur 7 au tableau des « valeurs de recherche ».
Ensuite, en traitant chaque élément du tableau, nous pouvons vérifier le tableau des « valeurs de recherche » et voir si l'une d'elles est égale à notre valeur. Si c'est le cas, nous retournons true.
const findSum = (arr, val) => {
let searchValues = [val - arr[0]];
for (let i = 1; i < arr.length; i++) {
let searchVal = val - arr[i];
if (searchValues.includes(arr[i])) {
return true;
} else {
searchValues.push(searchVal);
}
};
return false;
};La base de la solution est la boucle for, qui, comme nous l'avons vu ci-dessus, a une complexité temporelle linéaire O (N).
La deuxième partie itérative de notre fonction est Array.prototype.include (), une méthode JavaScript qui renverra true ou false selon que le tableau contient la valeur donnée.
Pour déterminer la complexité temporelle d'Array.prototype.includes (), nous pouvons examiner le polyfill fourni par MDN (et écrit en JavaScript), ou utiliser la méthode dans le code source d'un moteur JavaScript tel que Google V8 (C ++).
// https://tc39.github.io/ecma262/#sec-array.prototype.includes
if (!Array.prototype.includes) {
Object.defineProperty(Array.prototype, 'includes', {
value: function(valueToFind, fromIndex) {
if (this == null) {
throw new TypeError('"this" is null or not defined');
}
// 1. Let O be ? ToObject(this value).
var o = Object(this);
// 2. Let len be ? ToLength(? Get(O, "length")).
var len = o.length >>> 0;
// 3. If len is 0, return false.
if (len === 0) {
return false;
}
// 4. Let n be ? ToInteger(fromIndex).
// (If fromIndex is undefined, this step produces the value 0.)
var n = fromIndex | 0;
// 5. If n ≥ 0, then
// a. Let k be n.
// 6. Else n < 0,
// a. Let k be len + n.
// b. If k < 0, let k be 0.
var k = Math.max(n >= 0 ? n : len - Math.abs(n), 0);
function sameValueZero(x, y) {
return x === y || (typeof x === 'number' && typeof y === 'number' && isNaN(x) && isNaN(y));
}
// 7. Repeat, while k < len
while (k < len) {
// a. Let elementK be the result of ? Get(O, ! ToString(k)).
// b. If SameValueZero(valueToFind, elementK) is true, return true.
if (sameValueZero(o[k], valueToFind)) {
return true;
}
// c. Increase k by 1.
k++;
}
// 8. Return false
return false;
}
});
}Ici, la partie itérative d'Array.prototype.include () est une boucle while à l'étape 7, qui traverse (presque) toute la longueur du tableau donné. Cela signifie que sa complexité temporelle est également linéaire. Et comme elle est toujours en retard d'une étape par rapport à notre tableau principal, la complexité temporelle est O (N + (N - 1)). En utilisant la notation Big O, nous la simplifions à O (N) — car c'est N qui a le plus d'impact à mesure que la taille d'entrée augmente.
En ce qui concerne la complexité spatiale, un tableau supplémentaire est nécessaire, dont la longueur reflète le tableau d'origine (moins un, oui, mais cela peut être ignoré), ce qui entraîne une complexité spatiale O (N). L'augmentation de l'utilisation de la mémoire permet une efficacité maximale de l'algorithme.
J'espère que cet article vous sera utile en tant qu'annexe à l'entretien vidéo. Il montre qu'une tâche simple peut être réalisée de plusieurs manières différentes avec des ressources utilisées (temps, mémoire) variées.
Skillbox recommande :
- Cours en ligne appliqué .
- Cours en ligne .
- Cours pratique d'un an .
Source : habr.com
