Lorsque j'étudiais les performances des algorithmes, je suis tombé sur
cette vidéo de la fausse interview de Google . Il donne non seulement une idée de la façon dont les entretiens sont organisés dans les grandes sociétés technologiques, mais vous permet également de comprendre comment les problèmes algorithmiques sont résolus, et plus efficacement.
Cet article est une sorte d'accompagnement de la vidéo. Dans ce document, je donne des commentaires sur toutes les solutions présentées, ainsi que ma propre version de la solution en JavaScript. Les nuances de chaque algorithme sont également discutées.
Nous vous rappelons: pour tous les lecteurs de «Habr» - une remise de 10 000 roubles lors de l'inscription à un cours Skillbox en utilisant le code promo «Habr».
Skillbox recommande: Cours pratique "Mobile Developer PRO" .
Énoncé du problème
On nous donne un tableau ordonné et une valeur spécifique. Ensuite, ils demandent de créer une fonction qui renvoie vrai ou faux, selon que la somme de deux nombres quelconques du tableau peut être égale à la valeur donnée.
En d'autres termes, y a-t-il deux entiers x et y dans le tableau qui, une fois ajoutés, sont égaux à la valeur spécifiée?
Exemple ASi on nous a donné un tableau [1, 2, 4, 9] et une valeur de 8, la fonction retournera false, car aucun nombre du tableau ne peut donner 8 au total.
Exemple BMais s'il s'agit d'un tableau [1, 2, 4, 4] et que la valeur est 8, la fonction doit retourner true, car 4 + 4 = 8.
Solution 1. BruteforceDifficulté temporelle: O (N²).
Complexité spatiale: O (1).La signification 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 qualifiée d’efficace, car elle vérifie chaque somme possible de deux éléments du tableau et compare également deux fois chaque paire d’indices. (Par exemple, lorsque i = 1 et j = 2 - c'est en fait la même chose que la comparaison avec i = 2 et j = 1, mais dans cette solution, nous essayons les deux options).
Puisque notre solution utilise une paire de boucles imbriquées, elle est quadratique avec une complexité temporelle de O (N²).
Solution 2. Recherche binaire (binaire)Difficulté temporelle: O (Nlog (N)).
Complexité spatiale: O (1) .
Puisque les tableaux sont ordonnés, nous pouvons rechercher une solution en utilisant la recherche binaire. Il s'agit de l'algorithme le plus efficace pour les tableaux ordonnés. La recherche binaire elle-même a un runtime O (log (N)). Cependant, vous devez toujours utiliser une boucle for pour comparer chaque élément à toutes les autres valeurs.
Voici à quoi pourrait ressembler la solution. Pour que tout soit clair, nous utilisons une fonction distincte pour contrôler la recherche binaire. Ainsi que la fonction removeIndex (), qui renvoie la version du tableau moins l'index spécifié.
const findSum = (arr, val) => { for (let i = 0; i < arr.length; i++){ if (binarySearch(removeIndex(arr, i), val - arr[i])) { return true; } }; return false; }; const removeIndex = (arr, 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]) { end = pivot - 1; } else 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, à l'exclusion du premier index, et utilise une recherche binaire pour vérifier si l'une des valeurs restantes peut être ajoutée au tableau pour obtenir la quantité souhaitée. Cette action est effectuée une fois pour chaque élément du tableau.
La boucle for elle-même aura une complexité temporelle linéaire de O (N), mais à l'intérieur de la boucle for, nous effectuons une recherche binaire, qui donne la complexité temporelle totale de O (Nlog (N)). Cette solution est meilleure que la précédente, mais il y a encore quelque chose à améliorer.
Solution 3. Temps linéaireDifficulté temporelle: O (N).
Complexité spatiale: O (1).Nous allons maintenant résoudre le problème en nous souvenant que le tableau est trié. La solution consiste à prendre deux nombres: un au début et un à la fin. Si le résultat diffère de celui requis, nous modifions les points de début et de fin.
En fin de compte, soit nous atteignons la valeur souhaitée et retournons vrai, soit les points de début et de fin convergent et retournent faux.
const findSum = (arr, val) => { let start = 0; let end = arr.length - 1; while (start < end) { let sum = arr[start] + arr[end]; if (sum > val) { end -= 1; } else if (sum < val) { start += 1; } else { return true; }; }; return false; };
Maintenant tout va bien, la solution semble être optimale. Mais qui garantira que la baie a été commandée?
Et alors?
À première vue, nous pourrions simplement trier le tableau en premier, puis utiliser la solution ci-dessus. Mais comment cela affectera-t-il l'exécution?
Le meilleur algorithme est un tri rapide avec une complexité temporelle O (Nlog (N)). Si nous l'utilisons dans notre solution optimale, il changera ses performances de O (N) à O (Nlog (N)). Est-il possible de trouver une solution linéaire avec un tableau non ordonné?
Décision 4Difficulté temporelle: O (N).
Complexité spatiale: O (N).Oui, une solution linéaire existe, pour cela vous devez créer un nouveau tableau contenant une liste de correspondances que nous recherchons. Le compromis ici est une utilisation plus active de la mémoire: c'est la seule solution de l'article dont la complexité spatiale dépasse O (1).
Si la première valeur de ce tableau est 1 et la valeur de recherche est 8, nous pouvons ajouter la valeur 7 au tableau de «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'un d'eux est égal à notre valeur. Si oui, retournez vrai.
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 d'itération de notre fonction est Array.prototype.include (), une méthode JavaScript qui retournera vrai ou faux selon que le tableau contient la valeur donnée.
Pour découvrir la complexité temporelle de Array.prototype.includes (), nous pouvons regarder le polyfill fourni par MDN (et écrit en JavaScript), ou utiliser une méthode dans le code source d'un moteur JavaScript tel que Google V8 (C ++).
Ici, la partie itérative de Array.prototype.include () est la boucle while à l'étape 7, qui traverse (presque) toute la longueur du tableau donné. Cela signifie que sa complexité temporelle est également linéaire. Eh bien, comme c'est toujours une étape derrière notre tableau principal, la complexité temporelle est O (N + (N - 1)). En utilisant la notation Big O, nous la simplifions en O (N) - car c'est N qui a la plus grande influence avec l'augmentation de la taille d'entrée.
Quant à 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 conduit à la complexité spatiale de O (N). Eh bien, une utilisation accrue de la mémoire garantit une efficacité maximale de l'algorithme.
J'espère que cet article vous sera utile en tant que pièce jointe à une interview vidéo. Il montre qu'un problème simple peut être résolu de plusieurs manières différentes avec différentes quantités de ressources utilisées (temps, mémoire).
Skillbox recommande: