Când studiam performanța algoritmilor, am dat peste acest . Acesta nu doar că oferă o imagine de ansamblu asupra modului în care decurg interviurile la marile companii tehnologice, dar ajută și la înțelegerea modului în care se rezolvă problemele algoritmice, într-un mod cât mai eficient.
Acest articol este un fel de acompaniament pentru video. Aici ofer comentarii pentru toate soluțiile prezentate, plus versiunea mea a soluției în JavaScript. De asemenea, discutăm detaliile fiecărui algoritm.
Vă reamintim: pentru toți cititorii „Habr” — reducere de 10.000 de ruble la înscrierea la orice curs Skillbox cu codul de promovare „Habr”.
Skillbox recomandă: Curs practic .
Formularea problemei
Ni se oferă un array ordonat și o valoare specifică. Apoi ni se cere să creăm o funcție care returnează true sau false, în funcție de faptul dacă suma oricăror două numere din array poate fi egală cu valoarea dată.
Cu alte cuvinte, există în array două numere întregi x și y, care prin adunare sunt egale cu valoarea specificată?
Exemplu A
Dacă am primit array-ul [1, 2, 4, 9] și valoarea 8, funcția va returna false, deoarece nicio două numere din array nu pot da 8 prin adunare.
Exemplu B
Dar dacă avem array-ul [1, 2, 4, 4] și valoarea 8, funcția ar trebui să returneze true, deoarece 4 + 4 = 8.
Soluția 1. Bruteforce
Complexitate temporală: O(N²).
Complexitate spațială: O(1).
Cea mai evidentă abordare este utilizarea a două cicluri 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 poate fi considerată eficientă, deoarece verifică fiecare sumă posibilă a două elemente din array și compară fiecare pereche de indici de două ori. (De exemplu, când i = 1 și j = 2 — aceasta este, de fapt, aceeași comparație cu i = 2 și j = 1, dar în această soluție încercăm ambele variante).
Dat fiind că soluția noastră utilizează două cicluri for imbricate, este quadratică cu complexitate temporală O (N²).
Soluția 2. Căutare binară
Complexitate temporală: O(Nlog(N)).
Complexitate spațială: O(1).
Deoarece array-urile sunt ordonate, putem căuta o soluție folosind căutarea binară. Acesta este cel mai eficient algoritm pentru array-uri ordonate. Căutarea binară, în sine, are un timp de executare O (log (N)). Totuși, trebuie să folosim un ciclu for pentru a verifica fiecare element cu toate celelalte valori.
Iată cum poate arăta soluția. Pentru a clarifica, folosim o funcție separată pentru controlul căutării binare. De asemenea, avem funcția removeIndex (), care returnează versiunea array-ului fără indexul specificat.
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;
};Algoritmul pornește de la indexul [0]. Apoi, creează o versiune a array-ului, excluzând primul index, și folosește căutarea binară pentru a verifica dacă se poate adăuga oricare dintre valorile rămase la array pentru a obține suma dorită. Această acțiune se repete o dată pentru fiecare element din array.
Singurul ciclu for va avea o complexitate temporală liniară O (N), dar în interiorul ciclului for executăm căutare binară, ceea ce dă o complexitate temporală totală O (Nlog (N)). Această soluție este mai bună decât precedenta, dar încă există loc de îmbunătățiri.
Soluția 3. Timp liniar
Complexitatea temporală: O(N).
Complexitate spațială: O(1).
Acum vom rezolva problema, având în vedere că array-ul este sortat. Soluția constă în a lua două numere: unul la început și unul la sfârșit. Dacă suma diferă de cea dorită, schimăm punctul de început și cel de final.
În cele din urmă, fie întâlnim valoarea dorită și returnăm true, fie punctele de început și sfârșit se întâlnesc și returnăm 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;
};Acum totul este bine, soluția pare optimă. Dar cine ne garantează că array-ul a fost ordonat?
Ce facem atunci?
La o privire inițială, am putea pur și simplu să ordonăm array-ul și apoi să folosim soluția de mai sus. Dar cum va afecta asta timpul de execuție?
Cel mai bun algoritm este sortarea rapidă cu complexitate temporală O (Nlog (N)). Dacă îl folosim în soluția noastră optimă, performanța se va schimba de la O (N) la O (Nlog (N)). Se poate găsi o soluție liniară cu un array neordonat?
Soluția 4
Complexitatea temporală: O(N).
Complexitatea spațială: O(N).
Da, există o soluție liniară, pentru aceasta trebuie să creăm un nou array care să conțină lista potrivirilor pe care le căutăm. Compromisul aici este utilizarea mai activă a memoriei: aceasta este singura soluție din articol cu o complexitate spațială care depășește O(1).
Dacă prima valoare a acestui array este 1, iar valoarea căutată este 8, putem adăuga valoarea 7 în array-ul „valori de căutare”.
Apoi, procesând fiecare element al array-ului, putem verifica array-ul „valori de căutare” și să vedem dacă una dintre ele este egală cu valoarea noastră. Dacă da, returnăm 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;
};Bazele soluției sunt un ciclu for, care, așa cum am văzut mai sus, are o complexitate temporală liniară O(N).
A doua parte iterativă a funcției noastre este Array.prototype.include(), un metod JavaScript care va returna true sau false, în funcție de faptul dacă array-ul conține valoarea dată.
Pentru a determina complexitatea temporală a Array.prototype.includes(), putem considera polyfill-ul furnizat de MDN (și scris în JavaScript), sau putem utiliza metoda din codul sursă al motorului 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 un ciclu while la pasul 7, care (aproape) traversează întreaga lungime a acestui array dat. Asta înseamnă că complexitatea sa temporală este de asemenea liniară. Și, deoarece este întotdeauna cu un pas în urma array-ului nostru principal, complexitatea temporală este O(N + (N - 1)). Folosind notația Big O, o simplificăm la O(N) — pentru că N are cea mai mare influență pe măsură ce dimensiunea de intrare crește.
În ceea ce privește complexitatea spațială, este necesar un array suplimentar, a cărui lungime reflectă array-ul inițial (minus unul, da, dar asta se poate ignora), ceea ce conduce la o complexitate spațială O(N). Iar utilizarea crescută a memoriei asigură o eficiență maximă a algoritmului.
Sper că articolul va fi util pentru tine ca anexă la interviul video. Arată că o sarcină simplă poate fi rezolvată în mai multe moduri diferite, cu diferite resurse utilizate (timp, memorie).
Skillbox recomandă:
- Curs online aplicat .
- Curs online .
- Curs practic anual .
Sursa: habr.com
