Kada sam proučavao performanse algoritama, naišao sam na ovo . Ne samo da daje ideju o tome kako se intervjui provode u velikim tehnološkim korporacijama, već vam omogućava da shvatite kako se algoritamski problemi rješavaju što je efikasnije moguće.
Ovaj članak je svojevrsna pratnja videu. U njemu dajem komentare na sva prikazana rješenja, plus svoju vlastitu verziju rješenja u JavaScript-u. Također se raspravlja o nijansama svakog algoritma.
Podsećamo: za sve čitaoce "Habra" - popust od 10 rubalja pri upisu na bilo koji Skillbox kurs koristeći "Habr" promotivni kod.
Skillbox preporučuje: Praktični kurs .
Izjava o problemu
Dat nam je uređen niz i određena vrijednost. Zatim se traži da kreira funkciju koja vraća true ili false u zavisnosti od toga da li zbir bilo koja dva broja u nizu može biti jednak datoj vrednosti.
Drugim riječima, postoje li dva cijela broja u nizu, x i y, koji kada se zbroje jednaki su navedenoj vrijednosti?
Primjer A
Ako nam je dat niz [1, 2, 4, 9] i vrijednost je 8, funkcija će vratiti false jer dva broja u nizu ne mogu sabrati 8.
Primjer B
Ali ako je to niz [1, 2, 4, 4] i vrijednost je 8, funkcija bi trebala vratiti true jer je 4 + 4 = 8.
Rješenje 1: Gruba sila
Vremenska složenost: O(N²).
Složenost prostora: O(1).
Najočiglednije značenje je korištenje para ugniježđenih 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 nije efikasno jer provjerava svaki mogući zbir dva elementa u nizu i također dva puta upoređuje svaki par indeksa. (Na primjer, kada je i = 1 i j = 2 je zapravo isto kao poređenje sa i = 2 i j = 1, ali u ovom rješenju isprobavamo obje opcije).
Budući da naše rješenje koristi par ugniježđenih for petlji, ono je kvadratno sa O(N²) vremenskom složenošću.
Rješenje 2: Binarno pretraživanje
Vremenska složenost: O(Nlog(N)).
Složenost prostora: O(1).
Pošto su nizovi uređeni, možemo tražiti rješenje koristeći binarno pretraživanje. Ovo je najefikasniji algoritam za uređene nizove. Samo binarno pretraživanje ima vrijeme rada O(log(N)). Međutim, i dalje morate koristiti for petlju da provjerite svaki element u odnosu na sve druge vrijednosti.
Evo kako bi rješenje moglo izgledati. Da stvari budu jasne, koristimo posebnu funkciju za kontrolu binarnog pretraživanja. I također funkcija removeIndex(), koja vraća verziju niza minus dati indeks.
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;
};Algoritam počinje od indeksa [0]. Zatim kreira verziju niza isključujući prvi indeks i koristi binarno pretraživanje da vidi može li se bilo koja od preostalih vrijednosti dodati nizu kako bi se proizveo željeni zbroj. Ova akcija se izvodi jednom za svaki element u nizu.
Sama for petlja će imati linearnu vremensku složenost od O(N), ali unutar for petlje vršimo binarno pretraživanje, što daje ukupnu vremensku složenost od O(Nlog(N)). Ovo rješenje je bolje od prethodnog, ali još uvijek ima prostora za poboljšanje.
Rješenje 3: Linearno vrijeme
Vremenska složenost: O(N).
Složenost prostora: O(1).
Sada ćemo riješiti problem, prisjećajući se da je niz sortiran. Rješenje je uzeti dva broja: jedan na početku i jedan na kraju. Ako se rezultat razlikuje od traženog, promijenite početnu i završnu točku.
Na kraju ćemo ili naići na željenu vrijednost i vratiti true, ili će se početna i krajnja točka konvergirati i vratiti 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;
};
Sada je sve u redu, rješenje se čini optimalnim. Ali ko može garantovati da je niz naručen?
Šta onda?
Na prvi pogled, mogli smo jednostavno prvo naručiti niz, a zatim koristiti gornje rješenje. Ali kako će to uticati na vrijeme izvršenja?
Najbolji algoritam je brzo sortiranje sa vremenskom složenošću O (Nlog (N)). Ako ga koristimo u našem optimalnom rješenju, promijenit će svoje performanse sa O(N) na O(Nlog(N)). Da li je moguće pronaći linearno rješenje sa neuređenim nizom?
4 rješenje
Vremenska složenost: O(N).
Složenost prostora: O(N).
Da, postoji linearno rješenje; da bismo to učinili, moramo kreirati novi niz koji sadrži listu podudaranja koje tražimo. Ovdje je kompromis veća upotreba memorije: to je jedino rješenje u radu sa kompleksnošću prostora većom od O(1).
Ako je prva vrijednost datog niza 1, a vrijednost pretraživanja 8, možemo dodati vrijednost 7 u niz "vrijednosti pretraživanja".
Zatim, dok obrađujemo svaki element niza, možemo provjeriti niz "vrijednosti pretraživanja" i vidjeti da li je jedan od njih jednak našoj vrijednosti. Ako da, vratite 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 gore, ima linearnu vremensku složenost od O(N).
Drugi iterativni dio naše funkcije je Array.prototype.include(), JavaScript metoda koja će vratiti true ili false u zavisnosti od toga da li niz sadrži datu vrijednost.
Da bismo shvatili vremensku složenost Array.prototype.includes(), možemo pogledati polifil koji pruža MDN (i napisan u JavaScriptu) ili koristiti metodu u izvornom kodu JavaScript motora 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 iterativni dio Array.prototype.include() while petlja u koraku 7 koja (skoro) prelazi cijelu dužinu datog niza. To znači da je i njegova vremenska složenost linearna. Pa, pošto je uvek jedan korak iza našeg glavnog niza, vremenska složenost je O (N + (N - 1)). Koristeći Big O notaciju, pojednostavljujemo je na O(N) - jer je N ono što ima najveći utjecaj pri povećanju veličine ulaza.
Što se tiče prostorne složenosti, potreban je dodatni niz čija dužina odražava originalni niz (minus jedan, da, ali to se može zanemariti), što rezultira O(N) prostornom složenošću. Pa, povećana upotreba memorije osigurava maksimalnu efikasnost algoritma.
Nadam se da će vam članak biti koristan kao dodatak vašem video intervjuu. Pokazuje da se jednostavan problem može riješiti na nekoliko različitih načina s različitim količinama korištenih resursa (vrijeme, memorija).
Skillbox preporučuje:
- Primijenjeni online kurs .
- Online kurs .
- Praktična godina kursa .
izvor: www.habr.com