Dok dok sam proučavao performanse algoritama, naišao sam na ovo . Ne samo da pruža uvid u to kako se odvijaju intervjui u velikim tehnološkim korporacijama, već također omogućuje shvaćanje kako se algoritamski problemi rješavaju, i to na maksimalno učinkovit način.
Ovaj članak je svojevrsno praćenje videa. U njemu dajem komentare na sve prikazane solucije uz vlastitu verziju rješenja u JavaScriptu. Također se raspravlja o nijansama svakog algoritma.
Podsjećamo: za sve čitatelje "Habra" — popust od 10 000 rubalja prilikom upisa na bilo koji tečaj Skillbox uz promo kod "Habr".
Skillbox preporučuje: Praktični tečaj .
Postavljanje zadatka
Daju nam sortirani niz i određenu vrijednost. Zatim traže da stvorimo funkciju koja vraća true ili false, ovisno o tome može li suma bilo koja dva broja iz niza biti jednaka zadanoj vrijednosti.
Drugim riječima, postoje li u nizu dva cijela broja x i y koja zbrojena daju navedenu vrijednost?
Primjer A
Ako imamo niz [1, 2, 4, 9] i vrijednost 8, funkcija će vratiti false, jer nijedna dva broja iz niza ne mogu dati 8 u zbroju.
Primjer B
Ali ako je to niz [1, 2, 4, 4] i vrijednost 8, funkcija bi trebala vratiti true, jer 4 + 4 = 8.
Rješenje 1. Bruteforce
Vremenska složenost: O(N²).
Prostorna složenost: O(1).
Najočiglednije rješenje je korištenje para ugniježdenih petlji.
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;
};Ovo rješenje se ne može smatrati učinkovitim, jer provjerava svaku moguću sumu dva elementa u nizu, a također upoređuje svaki par indeksa dvaput. (Na primjer, kada je i = 1 i j = 2 - to je zapravo isto kao uspoređivati kada je i = 2 i j = 1, ali u ovom rješenju isprobavamo oba varijante).
Budući da naše rješenje koristi par ugniježdenih for petlji, ono je kvadratno s vremenskom složenošću O(N²).
Rješenje 2. Binarna pretraga
Vremenska složenost: O(Nlog(N)).
Prostorna složenost: O(1).
Budući da su nizovi sortirani, možemo potražiti rješenje koristeći binarnu pretragu. To je najučinkovitiji algoritam za sortirane nizove. Sama binarna pretraga ima vrijeme izvođenja O(log(N)). Međutim, još uvijek je potrebno koristiti for petlju kako bi provjerili svaki element sa svim ostalim vrijednostima.
Evo kako može izgledati rješenje. Da bi sve bilo jasno, koristimo posebnu funkciju za kontrolu binarnog pretraživanja. Također, funkciju removeIndex(), koja vraća verziju niza bez zadanog indeksa.
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;
};Algoritam počinje s indeksom [0]. Zatim stvara verziju niza, isključujući prvi indeks, i koristi binarno pretraživanje kako bi provjerio može li se dodati bilo koja od preostalih vrijednosti u niz kako bi se postigla željena suma. Ova radnja se izvodi jednom za svaki element u nizu.
Sama for petlja će imati liniarnu vremensku složenost O(N), ali unutar for petlje izvodimo binarno pretraživanje, što daje ukupnu vremensku složenost O(Nlog(N)). Ovo rješenje je bolje od prethodnog, ali još uvijek ima prostora za poboljšanja.
Rješenje 3. Linarno vrijeme
Vremenska složenost: O(N).
Prostorna složenost: O(1).
Sada ćemo rješavati problem, sjećajući se da je niz sortiran. Rješenje se sastoji od uzimanja dva broja: jednog na početku i jednog na kraju. Ako se rezultat razlikuje od traženog, mijenjamo početnu i završnu točku.
Na kraju ćemo ili pronaći traženu vrijednost i vratiti true, ili će se početna i završna točka sresti i vratiti 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;
};Sada je sve u redu, rješenje izgleda optimalno. No, tko može jamčiti da je niz bio sortiran?
Što onda?
Na prvi pogled, mogli smo prvo jednostavno sortirati niz, a zatim koristiti rješenje iznad. No, kako bi to utjecalo na vrijeme izvršavanja?
Najbolji algoritam je brza sortiranja s vremenskom složenošću O(Nlog(N)). Ako ga iskoristimo u našem optimalnom rješenju, promijenit će svoju učinkovitost s O(N) na O(Nlog(N)). Može li se pronaći linearno rješenje s nesoortiranim nizom?
Rješenje 4
Vremenska složenost: O(N).
Prostorna složenost: O(N).
Da, linearno rješenje postoji, za to trebate stvoriti novi niz koji sadrži popis podudaranja koja tražimo. Kompromis ovdje je aktivnije korištenje memorije: ovo je jedino rješenje u članku s prostornom složenošću većom od O (1).
Ako je prva vrijednost ovog niza jednaka 1, a tražena vrijednost jednaka 8, možemo dodati vrijednost 7 u niz "vrijednosti pretraživanja".
Zatim, obrađujući svaki element niza, možemo provjeriti niz "vrijednosti pretraživanja" i vidjeti je li jedan od njih jednak našoj vrijednosti. Ako jest, vraćamo 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;
};Osnova rješenja je for petlja koja, kao što smo vidjeli ranije, ima linearnu vremensku složenost O (N).
Drugi iteracijski dio naše funkcije je Array.prototype.includes (), JavaScript metoda koja će vraćati true ili false ovisno o tome sadrži li niz zadanu vrijednost.
Da bismo utvrdili vremensku složenost Array.prototype.includes (), možemo pogledati polyfill koji pruža MDN (i napisan je u JavaScriptu), ili se osloniti na metodu u izvornoj kodu JavaScript enginea, kao što je 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;
}
});
}Ovdje je iteracijski dio Array.prototype.includes () while petlja u koraku 7, koja (gotovo) prelazi cijelu dužinu danog niza. To znači da je njegova vremenska složenost također linearna. A budući da je uvijek jedan korak iza našeg glavnog niza, vremenska složenost iznosi O (N + (N — 1)). Koristeći Big O notaciju, pojednostavljujemo ju na O (N) — jer N ima najveći utjecaj kada se poveća ulazna veličina.
Što se tiče prostorne složenosti, potreban je dodatni niz čija dužina odražava izvorni niz (minus jedan, da, ali to možemo zanemariti), što dovodi do prostorne složenosti O (N). A povećana upotreba memorije osigurava maksimalnu učinkovitost algoritma.
Nadam se da će vam članak biti koristan kao dodatak video intervjuu. Pokazuje da se jednostavan zadatak može riješiti na nekoliko različitih načina s različitim količinama korištenih resursa (vrijeme, memorija).
Skillbox preporučuje:
- Prijateljski online tečaj .
- Online tečaj .
- Praktični godišnji tečaj .
Izvor: habr.com
