Amikor az algoritmusok teljesítményét tanulmányoztam, akkor találkoztam ezzel . Nemcsak képet ad arról, hogyan zajlanak az interjúk a nagy technológiai vállalatoknál, hanem lehetővé teszi annak megértését is, hogyan oldják meg az algoritmikus problémákat a lehető leghatékonyabban.
Ez a cikk egyfajta kísérőanyag a videóhoz. Ebben megjegyzéseket fűzök az összes bemutatott megoldáshoz, valamint a megoldás saját JavaScript-verziójához. Az egyes algoritmusok árnyalatait is tárgyaljuk.
Emlékeztetünk: a "Habr" minden olvasója számára - 10 000 rubel kedvezmény, ha a "Habr" promóciós kóddal bármely Skillbox tanfolyamra jelentkezik.
A Skillbox a következőket ajánlja: Gyakorlati tanfolyam .
Probléma nyilatkozat
Kapunk egy rendezett tömböt és egy konkrét értéket. Ezután egy függvényt kell létrehozni, amely igaz vagy hamis értéket ad vissza attól függően, hogy a tömb bármely két számának összege megegyezhet-e egy adott értékkel.
Más szóval, van a tömbben két olyan egész szám, az x és az y, amelyek összeadva megegyeznek a megadott értékkel?
A példa
Ha kapunk egy tömböt [1, 2, 4, 9], és az értéke 8, akkor a függvény false értéket ad vissza, mert a tömbben nem lehet két szám összeadni 8-at.
B példa
De ha ez egy tömb [1, 2, 4, 4], és az értéke 8, akkor a függvénynek igazat kell visszaadnia, mert 4 + 4 = 8.
1. megoldás: nyers erő
Időbonyolultság: O(N²).
A tér összetettsége: O(1).
A legnyilvánvalóbb jelentése egy pár beágyazott hurok 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;
};Ez a megoldás nem hatékony, mert a tömb két elemének minden lehetséges összegét ellenőrzi, és minden indexpárt kétszer is összehasonlít. (Például, ha i = 1 és j = 2, az valójában ugyanaz, mint az i = 2 és j = 1 összehasonlítás, de ebben a megoldásban mindkét lehetőséget kipróbáljuk).
Mivel a megoldásunk egy pár egymásba ágyazott hurkot használ, ezért másodfokú O(N²) időbonyolítással.
2. megoldás: Bináris keresés
Időbonyolultság: O(Nlog(N)).
A tér összetettsége: O(1).
Mivel a tömbök rendezettek, ezért bináris kereséssel tudunk megoldást keresni. Ez a leghatékonyabb algoritmus rendezett tömbök esetén. Maga a bináris keresés futásideje O(log(N)). Azonban továbbra is a for ciklust kell használnia az egyes elemek összehasonlításához az összes többi értékkel.
Így nézhet ki a megoldás. A dolgok egyértelművé tétele érdekében külön függvényt használunk a bináris keresés vezérlésére. És a removeIndex() függvény is, amely a tömb verzióját adja vissza az adott index levonásával.
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;
};Az algoritmus a [0] indextől indul. Ezután létrehozza a tömb egy verzióját, amely nem tartalmazza az első indexet, és bináris keresést használ annak ellenőrzésére, hogy a fennmaradó értékek bármelyike hozzáadható-e a tömbhöz a kívánt összeg előállításához. Ez a művelet a tömb minden elemére egyszer kerül végrehajtásra.
Maga a for hurok lineáris időbonyolultsága O(N), de a for hurkon belül bináris keresést végzünk, ami O(Nlog(N) általános időbonyolultságot ad). Ez a megoldás jobb, mint az előző, de van még mit javítani.
3. megoldás: Lineáris idő
Időbonyolultság: O(N).
A tér összetettsége: O(1).
Most megoldjuk a problémát, ne felejtsük el, hogy a tömb rendezve van. A megoldás az, hogy két számot veszünk: egyet az elején és egyet a végén. Ha az eredmény eltér a kívánttól, módosítsa a kezdő- és végpontot.
Végül vagy találkozunk a kívánt értékkel, és igazat adunk vissza, vagy a kezdő- és végpont konvergál, és hamis értéket ad vissza.
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;
};
Most már minden rendben, a megoldás optimálisnak tűnik. De ki tudja garantálni, hogy a tömb megrendelésre került?
Akkor mit?
Első pillantásra egyszerűen megrendelhettük volna először a tömböt, majd alkalmazhattuk volna a fenti megoldást. De hogyan befolyásolja ez a végrehajtási időt?
A legjobb algoritmus az O (Nlog (N)) időbonyolítású gyorsrendezés. Ha optimális megoldásunkban használjuk, akkor O(N)-ról O(Nlog(N)-ra változtatja a teljesítményét). Lehet-e lineáris megoldást találni rendezetlen tömbbel?
4 megoldás
Időbonyolultság: O(N).
A tér összetettsége: O(N).
Igen, van egy lineáris megoldás, ehhez létre kell hoznunk egy új tömböt, amely tartalmazza a keresett egyezések listáját. A kompromisszum itt a nagyobb memóriahasználat: ez az egyetlen megoldás a papírban, amelynek térbonyolultsága nagyobb, mint O(1).
Ha egy adott tömb első értéke 1, a keresési érték pedig 8, akkor a "keresési értékek" tömbhöz hozzáadhatjuk a 7-es értéket.
Ezután a tömb egyes elemeinek feldolgozása során ellenőrizhetjük a „keresési értékek” tömbjét, és megnézhetjük, hogy az egyik megegyezik-e a mi értékünkkel. Ha igen, adja vissza igazat.
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 hurok, amelynek, mint fentebb láttuk, O(N) lineáris időbonyolultsága van.
Függvényünk második iteratív része az Array.prototype.include(), egy JavaScript metódus, amely igaz vagy hamis értéket ad vissza attól függően, hogy a tömb tartalmazza-e az adott értéket.
Az Array.prototype.includes() időbeli összetettségének kiderítéséhez megnézhetjük az MDN által biztosított (és JavaScriptben írt) polyfill-t, vagy használhatunk egy módszert egy JavaScript-motor, például a Google V8 (C++) forráskódjában.
// 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.include() iteratív része a while ciklus a 7. lépésben, amely (majdnem) bejárja az adott tömb teljes hosszát. Ez azt jelenti, hogy időbeli összetettsége is lineáris. Nos, mivel mindig egy lépéssel lemarad a fő tömbünktől, az időbonyolultság O (N + (N - 1)). A Big O jelölést használva leegyszerűsítjük O(N)-re, mivel az N-nek van a legnagyobb hatása a bemeneti méret növelésekor.
A térbeli komplexitás tekintetében szükség van egy további tömbre, amelynek hossza tükrözi az eredeti tömböt (mínusz egy, igen, de ez figyelmen kívül hagyható), ami O(N) térbeli komplexitást eredményez. Nos, a megnövekedett memóriahasználat biztosítja az algoritmus maximális hatékonyságát.
Remélem, hasznosnak találja a cikket a videóinterjú kiegészítéseként. Megmutatja, hogy egy egyszerű probléma többféle módon is megoldható különböző mennyiségű erőforrás felhasználásával (idő, memória).
A Skillbox a következőket ajánlja:
- Jelentkezett online tanfolyam .
- Online tanfolyam .
- Gyakorlati évfolyam .
Forrás: will.com