Ko sem se ukvarjal s preučevanjem učinkovitosti algoritmov, sem naletel na to Ne samo, da daje predstavo, kako potekajo razgovori v velikih tehnoloških podjetjih, ampak tudi omogoča razumevanje, kako se algoritmične naloge rešujejo na najučinkovitejši način.
Ta članek je nekakšno spremljevalno gradivo k videu. V njem podajam komentarje k vsem prikazanim rešitvam ter svojo različico rešitve v JavaScriptu. Prav tako obravnavamo nianse vsakega algoritma.
Opominjamo: za vse bralce »Habra« — popust 10 000 rubljev ob vpisu na kateri koli tečaj Skillbox s promo kodo »Habr«.
Skillbox priporoča: Praktični tečaj .
Definisanje zadatka
Dobili smo urejen seznam in določeno vrednost. Nato nas prosijo, da ustvarimo funkcijo, ki vrne true ali false, odvisno od tega, ali lahko vsota katerikoli dve števili iz seznama ustreza določeni vrednosti.
Drugimi besedami, ali v nizu obstajata dve cela števila x in y, katerih vsota je enaka navedeni vrednosti?
Primer A
Če je dan seznam [1, 2, 4, 9] in vrednost 8, funkcija vrne false, ker nobeni dve števili iz seznama ne moreta dati 8 v seštevanju.
Primer B
Toda če gre za seznam [1, 2, 4, 4] in vrednost 8, mora funkcija vrniti true, ker 4 + 4 = 8.
Rešitev 1. Brute force
Časovna kompleksnost: O(N²).
Prostorna kompleksnost: O(1).
Najbolj očiten pristop je uporaba para vgnjenih 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;
};Te rešitve ne moremo šteti za učinkovito, saj preveri vsak možni seštevek dveh elementov v seznamu in prav tako primerja vsak par indeksov dvakrat. (Na primer, ko je i = 1 in j = 2 — to je dejansko isto kot primerjati z i = 2 in j = 1, ampak v tej rešitvi preizkusimo obe možnosti).
Ker naša rešitev uporablja par vgnjenih zank for, je kvadratna s časovno kompleksnostjo O (N²).
Rešitev 2. Dvojno iskanje (binarno iskanje)
Časovna kompleksnost: O(Nlog(N)).
Prostorna kompleksnost: O(1).
Ker so seznami urejeni, lahko iščemo rešitev z uporabo binarnega iskanja. To je najučinkovitejši algoritem za urejene sezname. Binarno iskanje samo po sebi ima časovno kompleksnost O (log (N)). Kljub temu pa je še vedno treba uporabiti zanko for, da preverimo vsak element vseh drugih vrednosti.
Tako lahko izgleda rešitev. Da bo vse jasno, uporabljamo ločeno funkcijo za nadzor binarnega iskanja. Prav tako funkcijo removeIndex (), ki vrne različico seznama brez določenega 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;
};Algoritem začne z indeksom [0]. Nato ustvari različico seznama, ki izključuje prvi indeks, in uporabi binarno iskanje, da preveri, ali je mogoče katero od preostalih vrednosti dodati k seznamu, da dobimo želeno vsoto. To dejanje se izvede enkrat za vsak element v seznamu.
Sama zanka for bo imela linearno časovno kompleksnost O (N), vendar znotraj zanke for izvajamo binarno iskanje, kar daje skupno časovno kompleksnost O (N log (N)). Ta rešitev je boljša od prejšnje, a še vedno je prostora za izboljšave.
Rešitev 3. Linearni čas
Časovna kompleksnost: O(N).
Prostorna kompleksnost: O(1).
Zdaj bomo rešili nalogo, ob tem pa pomnili, da je seznam urejen. Rešitev je, da vzamemo dva števila: eno na začetku in eno na koncu. Če se rezultat razlikuje od zahtevanega, spremenimo začetno in končno točko.
Na koncu bomo bodisi naleteli na želeni vrednost in vrnili true, bodisi se bodo začetna in končna točka srečali in vrnili 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;
};Zdaj je vse v redu, rešitev se zdi optimalna. A kdo zagotavlja, da je seznam urejen?
Kaj pa zdaj?
Na prvi pogled bi lahko najprej preprosto uredili seznam in nato uporabili zgornjo rešitev. Kako pa to vpliva na čas izvajanja?
Najboljši algoritem je hitra sortiranja s časovno kompleksnostjo O (N log (N)). Če ga uporabimo v našem optimalnem reševanju, se njegova zmogljivost spremeni iz O (N) na O (N log (N)). Ali lahko najdemo linearno rešitev z neurejenim seznamom?
Rešitev 4
Časovna kompleksnost: O(N).
Prostorska kompleksnost: O(N).
Da, linearna rešitev obstaja, za to je potrebno ustvariti novo polje, ki vsebuje seznam ujemanj, ki jih iščemo. Kompromis tukaj je bolj aktivna uporaba pomnilnika: to je edina rešitev v članku z prostorsko kompleksnostjo, ki presega O(1).
Če je prva vrednost tega polja enaka 1, in iskana vrednost je 8, lahko dodamo vrednost 7 v polje »iskane vrednosti«.
Nato, pri obdelavi vsakega elementa polja, lahko preverimo polje »iskane vrednosti« in vidimo, ali je ena od njih enaka naši vrednosti. Če je, vrnemo 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 cikel for, ki, kot smo videli zgoraj, ima linearno časovno kompleksnost O(N).
Drugi del naše funkcije je Array.prototype.include(), metoda JavaScript, ki bo vrnila true ali false glede na to, ali polje vsebuje dano vrednost.
Da bi ugotovili časovno kompleksnost Array.prototype.includes(), lahko razmislimo o polyfillu, ki ga zagotavlja MDN (in je napisan v JavaScriptu), ali pa uporabimo metodo v izvorni kodi JavaScript motorja, 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;
}
});
}Tukaj je iterativni del Array.prototype.include() cikel while na koraku 7, ki (skoraj) prečka celo dolžino danega polja. To pomeni, da je njegova časovna kompleksnost prav tako linearna. Ker je vedno en korak za našim osnovnim poljem, je časovna kompleksnost O(N + (N - 1)). Z uporabo Big O Notation jo poenostavimo na O(N) — ker N najbolj vpliva na povečanje vhodne velikosti.
Gledej na prostorsko kompleksnost, za to potrebujemo dodatno polje, katere dolžina odraža izvorno polje (minus en, ja, ampak to lahko ignoriramo), kar pripelje do prostorske kompleksnosti O(N). Povečana uporaba pomnilnika pa zagotavlja največjo učinkovitost algoritma.
Upam, da vam bo članek koristen kot dodatek k video intervjuju. Pokaže, da se lahko preprosta naloga reši na več različnih načinov z različno količino uporabljenih virov (čas, pomnilnik).
Skillbox priporoča:
- Praktični spletni tečaj .
- Spletni tečaj .
- Практический годовой курс .
Izvor: habr.com
