Când studiam performanța algoritmilor, am dat peste asta . Nu numai că oferă o idee despre modul în care sunt desfășurate interviurile la marile corporații tehnologice, dar vă permite și să înțelegeți cum problemele algoritmice sunt rezolvate cât mai eficient posibil.
Acest articol este un fel de acompaniament al videoclipului. În el ofer comentarii despre toate soluțiile afișate, plus propria mea versiune a soluției în JavaScript. Sunt discutate și nuanțele fiecărui algoritm.
Amintim: pentru toți cititorii „Habr” - o reducere de 10 de ruble la înscrierea la orice curs Skillbox folosind codul promoțional „Habr”.
Skillbox recomandă: Curs practic .
Declarație de problemă
Ni se oferă o matrice ordonată și o valoare specifică. Apoi i se cere să creeze o funcție care returnează adevărat sau fals, în funcție de faptul dacă suma oricăror două numere din matrice poate fi egală cu o valoare dată.
Cu alte cuvinte, există două numere întregi în matrice, x și y, care, atunci când sunt adăugate împreună, sunt egale cu valoarea specificată?
Exemplul A
Dacă ni se dă o matrice [1, 2, 4, 9] și valoarea este 8, funcția va returna fals deoarece nu există două numere din matrice care pot adăuga până la 8.
Exemplul B
Dar dacă este o matrice [1, 2, 4, 4] și valoarea este 8, funcția ar trebui să returneze adevărat deoarece 4 + 4 = 8.
Soluția 1: Forța brută
Complexitatea timpului: O(N²).
Complexitatea spațiului: O(1).
Cel mai evident sens este folosirea unei perechi de bucle imbricate.
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;
};Această soluție nu este eficientă deoarece verifică fiecare sumă posibilă a două elemente din matrice și, de asemenea, compară fiecare pereche de indici de două ori. (De exemplu, când i = 1 și j = 2 este de fapt același cu compararea cu i = 2 și j = 1, dar în această soluție încercăm ambele opțiuni).
Deoarece soluția noastră folosește o pereche de bucle for imbricate, este pătratică cu complexitate de timp O(N²).
Soluția 2: Căutare binară
Complexitatea timpului: O(Nlog(N)).
Complexitatea spațiului: O(1).
Deoarece tablourile sunt ordonate, putem căuta o soluție folosind căutarea binară. Acesta este cel mai eficient algoritm pentru matrice ordonate. Căutarea binară în sine are un timp de rulare de O(log(N)). Cu toate acestea, mai trebuie să utilizați o buclă for pentru a verifica fiecare element față de toate celelalte valori.
Iată cum ar putea arăta o soluție. Pentru a clarifica lucrurile, folosim o funcție separată pentru a controla căutarea binară. Și, de asemenea, funcția removeIndex(), care returnează versiunea matricei minus indexul dat.
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;
};Algoritmul pornește de la indexul [0]. Apoi creează o versiune a matricei, excluzând primul index și utilizează căutarea binară pentru a vedea dacă oricare dintre valorile rămase poate fi adăugată la matrice pentru a produce suma dorită. Această acțiune este efectuată o dată pentru fiecare element din matrice.
Bucla for în sine va avea o complexitate liniară de timp de O(N), dar în interiorul buclei for efectuăm o căutare binară, care oferă o complexitate de timp globală de O(Nlog(N)). Această soluție este mai bună decât cea anterioară, dar mai este loc de îmbunătățire.
Soluția 3: Timpul liniar
Complexitatea timpului: O(N).
Complexitatea spațiului: O(1).
Acum vom rezolva problema, amintindu-ne că matricea este sortată. Soluția este să luăm două numere: unul la început și unul la sfârșit. Dacă rezultatul diferă de cel necesar, atunci schimbați punctele de început și de sfârșit.
În cele din urmă, fie vom întâlni valoarea dorită și vom returna adevărat, fie punctele de început și de sfârșit vor converge și vor returna false.
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;
};
Acum totul este bine, soluția pare a fi optimă. Dar cine poate garanta că matricea a fost comandată?
Ce atunci?
La prima vedere, am fi putut pur și simplu să comandăm mai întâi matricea și apoi să folosim soluția de mai sus. Dar cum va afecta acest lucru timpul de execuție?
Cel mai bun algoritm este sortarea rapidă cu complexitatea de timp O (Nlog (N)). Dacă îl folosim în soluția noastră optimă, își va schimba performanța de la O(N) la O(Nlog(N)). Este posibil să găsim o soluție liniară cu o matrice neordonată?
Soluție 4
Complexitatea timpului: O(N).
Complexitatea spațiului: O(N).
Da, există o soluție liniară; pentru a face acest lucru, trebuie să creăm o nouă matrice care să conțină lista de potriviri pe care le căutăm. Schimbul aici este utilizarea mai multă memorie: este singura soluție din hârtie cu complexitate spațială mai mare decât O(1).
Dacă prima valoare a unui tablou dat este 1 și valoarea de căutare este 8, putem adăuga valoarea 7 la matricea „valori de căutare”.
Apoi, pe măsură ce procesăm fiecare element al matricei, putem verifica matricea de „valori de căutare” și să vedem dacă una dintre ele este egală cu valoarea noastră. Dacă da, returnați adevărat.
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;
};Baza soluției este o buclă for, care, așa cum am văzut mai sus, are o complexitate de timp liniară de O(N).
A doua parte iterativă a funcției noastre este Array.prototype.include(), o metodă JavaScript care va returna adevărat sau fals, în funcție de faptul dacă tabloul conține valoarea dată.
Pentru a ne da seama de complexitatea temporală a lui Array.prototype.includes(), ne putem uita la polyfill-ul oferit de MDN (și scris în JavaScript) sau putem folosi o metodă în codul sursă al unui motor JavaScript, cum ar fi 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;
}
});
}Aici partea iterativă a Array.prototype.include() este bucla while din pasul 7 care (aproape) traversează întreaga lungime a matricei date. Aceasta înseamnă că complexitatea sa de timp este, de asemenea, liniară. Ei bine, deoarece este întotdeauna cu un pas în spatele matricei noastre principale, complexitatea timpului este O (N + (N - 1)). Folosind Big O Notation, o simplificăm la O(N) - deoarece N este cel care are cel mai mare impact atunci când crește dimensiunea intrării.
În ceea ce privește complexitatea spațială, este nevoie de o matrice suplimentară a cărei lungime oglindește tabloul original (minus unu, da, dar care poate fi ignorat), rezultând complexitatea spațială O(N). Ei bine, utilizarea crescută a memoriei asigură eficiența maximă a algoritmului.
Sper că veți găsi articolul util ca supliment la interviul dvs. video. Acesta arată că o problemă simplă poate fi rezolvată în mai multe moduri diferite cu cantități diferite de resurse utilizate (timp, memorie).
Skillbox recomandă:
- Curs aplicat online .
- Curs online .
- Curs practic anual .
Sursa: www.habr.com