Ko sem preučeval delovanje algoritmov, sem naletel na to . Ne le daje predstavo o tem, kako potekajo razgovori v velikih tehnoloških korporacijah, temveč vam omogoča tudi razumevanje, kako se algoritemske težave rešujejo čim bolj učinkovito.
Ta članek je nekakšna priloga k videu. V njem podajam komentarje o vseh prikazanih rešitvah in svojo različico rešitve v JavaScriptu. Obravnavane so tudi nianse vsakega algoritma.
Spomnimo: za vse bralce "Habr" - popust v višini 10 rubljev ob vpisu v kateri koli tečaj Skillbox s promocijsko kodo "Habr".
Skillbox priporoča: Praktični tečaj .
Izjava o težavah
Podana nam je urejena matrika in določena vrednost. Nato se zahteva, da ustvari funkcijo, ki vrne true ali false, odvisno od tega, ali je lahko vsota katerih koli dveh števil v matriki enaka dani vrednosti.
Z drugimi besedami, ali sta v matriki dve celi števili, x in y, ki sta, ko se seštejeta, enaki podani vrednosti?
Primer A
Če nam je dana matrika [1, 2, 4, 9] in je vrednost 8, bo funkcija vrnila false, ker nobeni dve števili v matriki ne moreta sešteti 8.
Primer B
Če pa gre za polje [1, 2, 4, 4] in je vrednost 8, mora funkcija vrniti true, ker je 4 + 4 = 8.
1. rešitev: Surova sila
Časovna zahtevnost: O(N²).
Zahtevnost prostora: O(1).
Najbolj očiten pomen je uporaba para ugnezdenih zank.
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;
};Ta rešitev ni učinkovita, ker preveri vsako možno vsoto dveh elementov v matriki in dvakrat primerja vsak par indeksov. (Na primer, ko je i = 1 in j = 2, je dejansko enako kot primerjava z i = 2 in j = 1, vendar v tej rešitvi poskusimo obe možnosti).
Ker naša rešitev uporablja par ugnezdenih zank for, je kvadratna s časovno kompleksnostjo O(N²).
Rešitev 2: Binarno iskanje
Časovna zahtevnost: O(Nlog(N)).
Prostorska kompleksnost: O(1).
Ker so nizi urejeni, lahko rešitev iščemo z binarnim iskanjem. To je najučinkovitejši algoritem za urejene nize. Samo binarno iskanje ima čas delovanja O(log(N)). Vendar pa morate še vedno uporabiti zanko for, da preverite vsak element glede na vse druge vrednosti.
Tako bi lahko izgledala rešitev. Da bi stvari bile jasne, uporabljamo ločeno funkcijo za nadzor binarnega iskanja. In tudi funkcijo removeIndex(), ki vrne različico matrike minus dani 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;
};Algoritem se začne z indeksom [0]. Nato ustvari različico matrike brez prvega indeksa in uporabi binarno iskanje, da ugotovi, ali je mogoče matriki dodati katero koli od preostalih vrednosti, da dobimo želeno vsoto. To dejanje se izvede enkrat za vsak element v matriki.
Sama zanka for bo imela linearno časovno zapletenost O(N), vendar znotraj zanke for izvajamo binarno iskanje, ki daje skupno časovno zapletenost O(Nlog(N)). Ta rešitev je boljša od prejšnje, vendar je še vedno prostor za izboljšave.
3. rešitev: linearni čas
Časovna zahtevnost: O(N).
Zahtevnost prostora: O(1).
Sedaj bomo rešili problem, ne pozabimo, da je niz razvrščen. Rešitev je, da vzamemo dve številki: eno na začetku in eno na koncu. Če se rezultat razlikuje od zahtevanega, spremenite začetno in končno točko.
Sčasoma bomo naleteli na želeno vrednost in vrnili true ali pa se bosta začetna in končna točka zbližali in vrnili 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;
};
Zdaj je vse v redu, rešitev se zdi optimalna. Kdo pa lahko jamči, da je bil niz naročen?
Kaj potem?
Na prvi pogled bi lahko preprosto najprej naročili niz in nato uporabili zgornjo rešitev. Toda kako bo to vplivalo na čas izvedbe?
Najboljši algoritem je hitro razvrščanje s časovno kompleksnostjo O (Nlog (N)). Če ga uporabimo v naši optimalni rešitvi, bo spremenil svojo zmogljivost iz O(N) v O(Nlog(N)). Ali je mogoče najti linearno rešitev z neurejenim nizom?
4 rešitev
Časovna zahtevnost: O(N).
Zahtevnost prostora: O(N).
Da, obstaja linearna rešitev; za to moramo ustvariti novo matriko, ki vsebuje seznam ujemanj, ki jih iščemo. Kompromis tukaj je večja uporaba pomnilnika: to je edina rešitev v članku s prostorsko kompleksnostjo, večjo od O(1).
Če je prva vrednost dane matrike 1 in je iskalna vrednost 8, lahko dodamo vrednost 7 v matriko "iskanih vrednosti".
Potem, ko obdelujemo vsak element matrike, lahko preverimo matriko »iskalnih vrednosti« in vidimo, ali je ena od njih enaka naši vrednosti. Če da, vrni 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 rešitve je zanka for, ki ima, kot smo videli zgoraj, linearno časovno kompleksnost O(N).
Drugi iterativni del naše funkcije je Array.prototype.include(), metoda JavaScript, ki vrne true ali false, odvisno od tega, ali matrika vsebuje dano vrednost.
Da ugotovimo časovno kompleksnost Array.prototype.includes(), si lahko ogledamo polifill, ki ga zagotavlja MDN (in je napisan v JavaScriptu), ali uporabimo metodo v izvorni kodi motorja JavaScript, kot 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;
}
});
}Tu je iterativni del Array.prototype.include() zanka while v 7. koraku, ki (skoraj) prečka celotno dolžino podane matrike. To pomeni, da je tudi njegova časovna kompleksnost linearna. No, ker je vedno en korak za našim glavnim nizom, je časovna kompleksnost O (N + (N - 1)). Z uporabo zapisa Big O ga poenostavimo na O(N) - ker ima N največji vpliv pri povečanju velikosti vnosa.
Kar zadeva prostorsko kompleksnost, je potrebna dodatna matrika, katere dolžina zrcali prvotno matriko (minus ena, da, vendar se to lahko prezre), kar ima za posledico O(N) prostorsko kompleksnost. No, povečana poraba pomnilnika zagotavlja maksimalno učinkovitost algoritma.
Upam, da vam bo članek koristen kot dodatek k vašemu video intervjuju. Pokaže, da je preprost problem mogoče rešiti na več različnih načinov z različnimi količinami porabljenih virov (čas, pomnilnik).
Skillbox priporoča:
- Uporabni spletni tečaj .
- Spletni tečaj .
- Praktični enoletni tečaj .
Vir: www.habr.com