Dok 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 također omogućuje da shvatite kako se algoritamski problemi rješavaju što učinkovitije.
Ovaj članak je svojevrsna pratnja videu. U njemu dajem komentare na sva prikazana rješenja, plus 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 pri upisu na bilo koji tečaj Skillbox koristeći promotivni kod "Habr".
Skillbox preporučuje: Praktični tečaj .
Formuliranje problema
Dobili smo uređeni niz i određenu vrijednost. Zatim se od njega traži da stvori funkciju koja vraća true ili false ovisno o tome može li zbroj bilo koja dva broja u nizu biti jednak zadanoj vrijednosti.
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 dan niz [1, 2, 4, 9], a vrijednost je 8, funkcija će vratiti false jer nijedna dva broja u nizu ne mogu zbrojiti 8.
Primjer B
Ali ako je to polje [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čitije 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 učinkovito jer provjerava svaki mogući zbroj dva elementa u nizu i uspoređuje svaki par indeksa dva puta. (Na primjer, kada je i = 1 i j = 2 zapravo je isto što i usporedba s 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 s O(N²) vremenskom složenošću.
Rješenje 2: Binarno pretraživanje
Vremenska složenost: O(Nlog(N)).
Složenost prostora: O(1).
Budući da su nizovi poredani, rješenje možemo tražiti pomoću binarnog pretraživanja. Ovo je najučinkovitiji algoritam za uređene nizove. Samo binarno pretraživanje ima vrijeme izvođenja O(log(N)). Međutim, i dalje morate koristiti for petlju za provjeru svakog elementa u odnosu na sve ostale vrijednosti.
Evo kako bi rješenje moglo izgledati. Kako bismo razjasnili stvari, koristimo zasebnu funkciju za kontrolu binarnog pretraživanja. Također i funkciju removeIndex(), koja vraća verziju polja minus zadani 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 stvara 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 dobio željeni zbroj. Ova se radnja izvodi jednom za svaki element u nizu.
Sama for petlja će imati linearnu vremensku složenost od O(N), ali unutar for petlje izvodimo binarno pretraživanje, što daje ukupnu vremensku složenost od O(Nlog(N)). Ovo rješenje je bolje od prethodnog, ali ima još prostora za napredak.
Rješenje 3: Linearno vrijeme
Vremenska složenost: O(N).
Složenost prostora: O(1).
Sada ćemo riješiti problem, imajući na umu 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 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 tko može jamčiti da je niz naručen?
Što onda?
Na prvi pogled, mogli smo jednostavno prvo naručiti niz, a zatim upotrijebiti gornje rješenje. Ali kako će to utjecati na vrijeme izvršenja?
Najbolji algoritam je brzo sortiranje s vremenskom složenošću O (Nlog (N)). Ako ga koristimo u našem optimalnom rješenju, promijenit će svoju izvedbu iz O(N) u O(Nlog(N)). Je li moguće pronaći linearno rješenje s neuređenim nizom?
Rješenje 4
Vremenska složenost: O(N).
Složenost prostora: O(N).
Da, postoji linearno rješenje; da bismo to učinili, moramo stvoriti novi niz koji sadrži popis podudaranja koje tražimo. Kompromis je ovdje veća upotreba memorije: to je jedino rješenje u radu čija je prostorna složenost veća od O(1).
Ako je prva vrijednost zadanog niza 1, a vrijednost pretraživanja 8, možemo dodati vrijednost 7 nizu "vrijednosti pretraživanja".
Zatim, dok obrađujemo svaki element niza, možemo provjeriti niz "vrijednosti pretraživanja" i vidjeti je li jedna od njih jednaka našoj vrijednosti. Ako da, vrati 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 O(N).
Drugi iterativni dio naše funkcije je Array.prototype.include(), JavaScript metoda koja će vratiti true ili false ovisno o tome sadrži li niz zadanu vrijednost.
Da bismo shvatili vremensku složenost Array.prototype.includes(), možemo pogledati polyfill koji daje 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 (gotovo) prelazi cijelu duljinu zadanog niza. To znači da je njegova vremenska složenost također linearna. Pa, budući da je uvijek jedan korak iza našeg glavnog niza, vremenska složenost je O (N + (N - 1)). Koristeći Big O notaciju, pojednostavljujemo ga na O(N) - jer N ima najveći utjecaj pri povećanju veličine unosa.
Što se tiče prostorne složenosti, potreban je dodatni niz čija duljina odražava izvorni 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 učinkovitost 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 tečaj .
- Mrežni tečaj .
- Praktični godišnji tečaj .
Izvor: www.habr.com