Amikor az algoritmusok teljesítményének tanulmányozásával foglalkoztam, belebotlottam ebbe . Ez nemcsak azt mutatja be, hogyan zajlanak az interjúk nagyobb technológiai vállalatoknál, hanem arra is lehetőséget ad, hogy megértsük, hogyan oldják meg az algoritmikus feladatokat, lehetőleg a legoptimálisabb módon.
Ez a cikk egyfajta kísérője a videónak. Itt kommentárokat adok minden bemutatott megoldáshoz, plusz a saját JavaScript megoldásomat is bemutatom. Az egyes algoritmusok részleteit is átbeszéljük.
Emlékeztetjük: minden «Habr» olvasónak 10 000 rubeles kedvezmény jár bármely Skillbox kurzus jelentkezésekor a «Habr» promóciós kód felhasználásával.
A Skillbox ajánlja: Gyakorlati kurzus .
Lépjünk át a kitűzött feladatra: írjunk egy XDP mechanizmust SYN cookie-kkal.
Egy rendezett tömböt és egy adott értéket kapunk. Ezután kérjük, hogy készítsünk egy függvényt, amely true vagy false értéket ad vissza attól függően, hogy a tömb bármely két szám összege egyenlő lehet-e a megadott értékkel.
Más szavakkal, van-e a tömbben két egész szám x és y, amelyek összege megegyezik a megadott értékkel?
A példa A
Ha a tömbünk [1, 2, 4, 9], és az érték 8, a függvény false értéket ad vissza, mivel a tömbből bármely két szám nem adhat 8-at összeadáskor.
A példa B
De ha ez a tömb [1, 2, 4, 4] és az érték 8, a függvénynek true-t kell visszaadnia, mert 4 + 4 = 8.
1. megoldás. Bruteforce
Időbeli bonyolultság: O(N²).
Térbeli bonyolultság: O(1).
A legnyilvánvalóbb megoldás a pár beágyazott ciklus használata.
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;
};Ezt a megoldást nem lehet hatékonynak nevezni, mivel minden lehetséges összeget ellenőriz minden tömbelem párosításhoz, és minden indexpárt kétszer hasonlít össze. (Például amikor i = 1 és j = 2 — valójában ugyanazt hasonlítjuk, mint i = 2 és j = 1, de ebben a megoldásban mindkét lehetőséget próbáljuk).
Mivel a megoldásunk pár beágyazott for ciklust használ, a bonyolultsági fok négyzetes O(N²).
2. megoldás. Kétirányú (bináris) keresés
Időbeli bonyolultság: O(Nlog(N)).
Térbeli bonyolultság: O(1).
Mivel a tömbök rendezettek, megpróbálhatunk megoldást keresni bináris kereséssel. Ez a legoptimálisabb algoritmus rendezett tömbök esetén. A bináris keresés saját magában O(log(N)) futási időt biztosít. Azonban a for ciklust még mindig használnunk kell minden elem ellenőrzésére más értékekkel.
Íme, így nézhet ki a megoldás. Annak érdekében, hogy minden világos legyen, külön függvényt használunk a bináris keresés ellenőrzésére. És van egy removeIndex() függvényünk is, amely visszaadja a tömb verzióját a megadott index levonásával.
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;
};Az algoritmus az [0] indexszel kezdődik. Ezután létrehoz egy tömb verziót, amely kizárja az első indexet, és bináris keresést használ annak ellenőrzésére, hogy hozzáadhatunk-e bármelyik fennmaradó értéket a tömbhöz az elérni kívánt összeghez. Ezt az eljárást egyszer hajtjuk végre minden tömbelem számára.
Magában a for ciklusnak lineáris időkomplexitása O(N) van, de a for cikluson belül bináris keresést végzünk, ami összesített időkomplexitást ad O(N log(N)). Ez a megoldás jobb, mint az előző, de van még mit javítani.
Megoldás 3. Lineáris idő
Időbeli komplexitás: O(N).
Térbeli bonyolultság: O(1).
Most azt a feladatot fogjuk megoldani, hogy a tömb rendezett. A megoldás abban áll, hogy két számot veszünk: az egyiket a kezdő és az egyiket a végén. Ha az összeg eltér a kívánttól, akkor cseréljük fel a kezdő és végpontokat.
Végül vagy megtaláljuk a kívánt értéket, és true-t adunk vissza, vagy a kezdő és végpontok találkoznak, és false-t adunk vissza.
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;
};Most minden rendben van, a megoldás úgy tűnik, optimális. De ki garantálja, hogy a tömb rendezett volt?
Mi akkor?
Első pillantásra egyszerűen csak rendeznünk kellett volna a tömböt, majd használni a fenti megoldást. De hogyan befolyásolja ez a végrehajtási időt?
A legjobb algoritmus a gyors rendezés O(N log(N) időbeli komplexitással). Ha ezt használjuk az optimális megoldásunkban, az teljesítménye O(N)-ről O(N log(N))-ra változik. Találhatunk-e lineáris megoldást rendezetlen tömbbel?
Megoldás 4
Időbeli komplexitás: O(N).
Térbeli komplexitás: O(N).
Igen, létezik lineáris megoldás, ehhez egy új tömböt kell létrehozni, amely tartalmazza a keresett egyezések listáját. A kompromisszum itt a memória aktívabb használata: ez az egyetlen megoldás, amelynek térbeli összetettsége O(1) felett van.
Ha ennek a tömbnek az első értéke 1, míg a keresett érték 8, hozzáadhatjuk a 7-es értéket a "keresett értékek" tömbhöz.
Ezután, miközben feldolgozzuk a tömb minden egyes elemét, ellenőrizhetjük a "keresett értékek" tömböt, és megnézhetjük, hogy az egyik értéke egyenlő-e a keresett értékünkkel. Ha igen, visszatérünk true értékkel.
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;
};A megoldás alapja egy for ciklus, amely, mint láttuk, lineáris időbeli összetettséggel rendelkezik O(N).
A funkciónk második iteráló része — az Array.prototype.includes() JavaScript metódus, amely true vagy false értéket ad vissza aszerint, hogy a tömb tartalmazza-e a megadott értéket.
Az Array.prototype.includes() időbeli összetettségének meghatározásához figyelembe vehetjük az MDN által biztosított polyfillt (és amely JavaScript-ben van megírva), vagy informálódhatunk a JavaScript motor, például a Google V8 forráskódjában található metódusról (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;
}
});
}Itt az Array.prototype.includes() iteráló része a 7. lépésnél található while ciklus, amely (majdnem) átfogja a megadott tömb teljes hosszát. Ez azt jelenti, hogy ennek időbeli összetettsége is lineáris. Mivel mindig egy lépéssel lemarad a fő tömbtől, az időbeli összetettsége O(N + (N — 1)). A Big O jelölés segítségével egyszerűsítjük O(N)-ra — mivel N van a legnagyobb hatással a bemeneti méret növekedésekor.
A térbeli összetettség szempontjából szükség van egy további tömbre, amelynek hossza a kiindulási tömbhöz viszonyítva (eggyel kevesebb, igen, de ezt figyelmen kívül lehet hagyni) O(N) térbeli összetettséget jelent. A megnövelt memóriahasználat maximális hatékonyságot biztosít az algoritmus számára.
Remélem, hogy cikkünk hasznos lesz számodra a videóinterjú kiegészítéseként. Megmutatja, hogy egy egyszerű feladatot több különböző módon lehet megoldani, különböző mértékű erőforrásfelhasználással (idő, memória).
A Skillbox ajánlja:
- Alkalmazott online kurzus .
- Online kurzus .
- Gyakorlati éves kurzus .
Forrás: habr.com
