
Kada sam proučavao performanse algoritama, naišao sam na ovo . Ono ne samo da daje uvid u to kako izgledaju intervjui u velikim tehnološkim kompanijama, već i omogućava razumijevanje kako se algoritamski zadaci riješavaju, pritom maksimalno efikasno.
Ovaj članak je svojevrsno pratnja videu. U njemu komentarišem sve prikazane solucije, a takođe pružam vlastitu verziju rješenja na JavaScriptu. Takođe se raspravlja o nijansama svakog algoritma.
Podsećamo: za sve čitaoce „Habra“ — popust od 10.000 rubalja prilikom upisa na bilo koji kurs Skillbox uz promo kod „Habr“.
Skillbox preporučuje: Praktični kurs .
Postavljanje zadatka
Dobijamo sortirani niz i određenu vrijednost. Onda se traži da kreiramo funkciju koja vraća true ili false, u zavisnosti od toga da li suma bilo koja dva broja iz niza može biti jednaka zadanoj vrijednosti.
Drugim riječima, postoje li u nizu dva cijela broja x i y koja pri sabiranju daju navedenu vrijednost?
Primjer A
Ako nam je dat niz [1, 2, 4, 9] i vrijednost 8, funkcija će vratiti false, jer nijedna dva broja iz niza ne mogu dati 8 u sumi.
Primjer B
Ali ako je ovo niz [1, 2, 4, 4] i vrijednost 8, funkcija bi trebala vratiti true, jer 4 + 4 = 8.
Rješenje 1. Brute force
Vremenska složenost: O(N²).
Prostorna složenost: O(1).
Najlogičnije 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 efikasnim, jer provjerava svaku moguću sumu dva elementa u nizu, a takođe upoređuje svaki par indeksa dvaput. (Na primjer, kada je i = 1 i j = 2 — to je zapravo isto kao upoređivanje sa i = 2 i j = 1, ali u ovom rješenju probamo 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. Ovo je najučinkovitiji algoritam za sortirane nizove. Sama binarna pretraga ima vrijeme izvršenja O (log (N)). Ipak, još uvijek trebamo koristiti for petlju da provjerimo svaki element s ostalim vrijednostima.
Evo kako može izgledati rješenje. Da bismo sve objasnili, koristimo posebnu funkciju za kontrolu binarne pretrage. Također imamo 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 binarnu pretragu kako bi provjerio može li se dodati jedno od preostalih vrijednosti kako bi se postigla željena suma. Ova radnja se izvršava jedanput za svaki element u nizu.
Sama for petlja će imati linearni vremenski kompleks O(N), ali unutar for petlje vršimo binarnu pretragu, što daje ukupni vremenski kompleks 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).
Prostorna složenost: O(1).
Sada ćemo rješavati problem s saznanjem da je niz sortiran. Rješenje je uzeti dva broja: jedan na početku i jedan na kraju. Ako je rezultat različit od traženog, mijenjamo 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 završna točka susresti 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. Ali tko može jamčiti da je niz bio sortiran?
Što onda?
Na prvi pogled, mogli smo prvo jednostavno sortirati niz, a zatim koristiti gornje rješenje. Ali kako će to utjecati na vrijeme izvođenja?
Najbolji algoritam je brza sorta s vremenskom složenošću O(Nlog(N)). Ako ga primijenimo u našem optimalnom rješenju, to će promijeniti njegovu performansu s O(N) na O(Nlog(N)). Možemo li pronaći linearno rješenje za neuredan niz?
Rješenje 4
Vremenska složenost: O(N).
Prostorna složenost: O(N).
Da, linearno rješenje postoji, za to treba stvoriti novi niz koji sadrži listu podudaranja koja tražimo. Kompromis ovdje je veće korištenje memorije: to je jedino rješenje u članku sa 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 pretrage".
Zatim, obrađujući svaki element niza, možemo provjeriti niz "vrijednosti pretrage" i vidjeti da li je neka od njih jednaka 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 iterativni dio naše funkcije je Array.prototype.include (), JavaScript metoda koja će vraćati true ili false ovisno o tome da li niz sadrži zadanu vrijednost.
Da bismo utvrdili vremensku složenost Array.prototype.includes (), možemo razmotriti polyfill koji pruža MDN (i napisan je u JavaScript-u), ili se osloniti na metodu u izvornoj 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 na koraku 7, koja ( gotovo) pokriva cijelu dužinu datog 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 je O (N + (N — 1)). Koristeći Big O Notation, pojednostavljujemo je na O (N) — jer samo N ima najveći utjecaj prilikom povećanja ulazne veličine.
Što se tiče prostorne složenosti, potreban je dodatni niz, čija dužina odražava izvorni niz (minus jedan, da, ali to se može ignorirati), što dovodi do prostorne složenosti O (N). A povećano korištenje memorije osigurava maksimalnu efikasnost algoritma.
Nadam se da će vam članak biti koristan kao dodatak videointervjuu. P pokazuje da se jednostavan zadatak može riješiti na nekoliko različitih načina s različitim količinama upotrebljenih resursa (vrijeme, memorija).
Skillbox preporučuje:
- Praktični online kurs .
- Online kurs .
- Praktični godišnji kurs .
Izvor: habr.com
