Keď som sa zaoberal štúdiom výkonnosti algoritmov, natrafil som na toto . Nie lenže poskytuje predstavu o tom, ako prebiehajú pohovory vo veľkých technologických spoločnostiach, ale taktiež umožňuje pochopiť, ako sa riešia algoritmické úlohy, a to maximálne efektívne.
Tento článok je akýmsi sprievodom k videu. V ňom poskytujem komentáre k všetkým zobrazeným riešeniam plus vlastnú verziu riešenia v JavaScripte. Diskutujem aj o nuansách každého algoritmu.
Pripomíname: pre všetkých čitateľov „Habr“ — zľava 10 000 rubľov pri zapísaní na akýkoľvek kurz Skillbox s promo kódom „Habr“.
Skillbox odporúča: Praktický kurz .
Stanovenie úlohy
Dostaneme usporiadané pole a určitú hodnotu. Potom nás požiadajú, aby sme vytvorili funkciu, ktorá vracia true alebo false, v závislosti od toho, či môže byť súčet akýchkoľvek dvoch čísel z poľa rovný zadanej hodnote.
Inými slovami, existujú v poli dve celé čísla x a y, ktorých súčet je rovný uvedenej hodnote?
Príklad A
Ak dostaneme pole [1, 2, 4, 9] a hodnotu 8, funkcia vráti false, pretože žiadne dve čísla z poľa nemôžu dať 8 v súčte.
Príklad B
Ale ak ide o pole [1, 2, 4, 4] a hodnotu 8, funkcia by mala vrátiť true, pretože 4 + 4 = 8.
Riešenie 1. Brute-force
Časová zložitosť: O(N²).
Priestorová zložitosť: O(1).
Najzjavnejšou hodnotou je použitie dvojice vnorených cyklov.
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;
};Toto riešenie nemožno považovať za efektívne, pretože kontroluje každý možný súčet dvoch prvkov v poli a tiež porovnáva každú dvojicu indexov dvakrát. (Napríklad, keď i = 1 a j = 2 — to je v podstate rovnaké ako porovnávať s i = 2 a j = 1, ale v tomto riešení skúšame oba varianty).
Keďže naše riešenie používa pár vnorených cyklov for, je kvadratické s časovou zložitosťou O(N²).
Riešenie 2. Binárne vyhľadávanie
Časová zložitosť: O(Nlog(N)).
Priestorová zložitosť: O(1).
Keďže sú polia usporiadané, môžeme hľadať riešenie s použitím binárneho vyhľadávania. To je najefektívnejší algoritmus pre usporiadané polia. Samotné binárne vyhľadávanie má časovú náročnosť O(log(N)). Avšak aj tak je potrebné použiť cyklus for, aby sa skontroloval každý prvok voči všetkým ostatným hodnotám.
Takto môže vyzerať riešenie. Aby bolo všetko jasné, používame samostatnú funkciu na kontrolu binárneho vyhľadávania. A tiež funkciu removeIndex (), ktorá vráti verziu poľa bez uvedeného indexu.
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;
};Algoritmus začína od indexu [0]. Potom vytvorí verziu poľa s vylúčeným prvým indexom a používa binárne vyhľadávanie, aby skontroloval, či je možné k poľu pridať niektorú z zostávajúcich hodnôt na dosiahnutie požadovanej sumy. Táto operácia sa vykoná raz pre každý prvok v poli.
Sám o sebe for cyklus bude mať lineárnu časovú zložitosť O (N), ale vo vnútri for cyklu vykonávame binárne vyhľadávanie, čo dáva celkovú časovú zložitosť O (Nlog (N)). Toto riešenie je lepšie ako predchádzajúce, ale stále je čo zlepšovať.
Riešenie 3. Lineárny čas
Časová zložitosť: O(N).
Priestorová zložitosť: O(1).
Teraz budeme riešiť úlohu s vedomím, že pole je zoradené. Riešením je vziať dve čísla: jedno na začiatku a jedno na konci. Ak je výsledok iný ako požadované, meníme počiatočný a konečný bod.
Nakoniec buď nájdeme požadovanú hodnotu a vrátime true, alebo sa počiatočné a konečné body zjednotia a vráti sa 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;
};Teraz je všetko v poriadku, riešenie sa zdá byť optimálne. Ale kto dá záruku, že pole bolo usporiadané?
Čo potom?
Na prvý pohľad by sme mohli najprv jednoducho usporiadať pole a potom použiť vyššie uvedené riešenie. Ale ako by to ovplyvnilo čas vykonávania?
Najlepší algoritmus je rýchle triedenie s časovou zložitosťou O (Nlog (N)). Ak ho použijeme v našom optimálnom riešení, změní sa jeho výkon z O (N) na O (Nlog (N)). Je možné nájsť lineárne riešenie s neusporiadaným poľom?
Riešenie 4
Časová zložitosť: O(N).
Priestorová zložitosť: O(N).
Áno, existuje lineárne riešenie, na to je potrebné vytvoriť nové pole, ktoré bude obsahovať zoznam zhod, ktoré hľadáme. Kompromisom je tu aktívnejšie využívanie pamäte: to je jediné riešenie v článku s priestorovou zložitostí presahujúcou O (1).
Ak je prvá hodnota v tomto poli rovná 1 a hľadaná hodnota rovná 8, môžeme pridať hodnotu 7 do poľa „hľadaných hodnôt“.
Potom, spracovaním každého prvku poľa, môžeme skontrolovať pole „hľadaných hodnôt“ a pozrieť sa, či je niektorá z nich rovná našej hodnote. Ak áno, vráťme 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;
};Základom riešenia je cyklus for, ktorý, ako sme videli vyššie, má lineárnu časovú zložitost O (N).
Druhá iteratívna časť našej funkcie — Array.prototype.include (), metóda JavaScript, ktorá vráti true alebo false v závislosti od toho, či pole obsahuje danú hodnotu.
Aby sme zistili časovú zložitost Array.prototype.includes (), môžeme zvážiť polyfill poskytnutý MDN (a napísaný v JavaScripte) alebo využiť metódu v zdrojovom kóde JavaScriptového enginu, ako 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 iteratívna časť Array.prototype.include () cyklom while na kroku 7, ktorý (takmer) prechádza celou dĺžkou daného poľa. To znamená, že jeho časová zložitost je tiež lineárna. A pretože je vždy o jeden krok za naším hlavným poľom, časová zložitost je O (N + (N — 1)). Pomocou Big O Notation to zjednodušíme na O (N) — pretože N má najväčší vplyv pri zvyšovaní vstupnej veľkosti.
Čo sa týka priestorovej zložitosti, je potrebné ďalšie pole, ktorého dĺžka odráža pôvodné pole (minus jedno, áno, ale to sa dá ignorovať), čo vedie k priestorovej zložitosti O (N). A zvýšené využívanie pamäte zabezpečuje maximálnu efektívnosť algoritmu.
Dúfam, že článok vám bude užitočný ako príloha k video rozhovoru. Ukazuje, že jednoduchá úloha môže byť riešená niekoľkými rôznymi spôsobmi s rôznym množstvom využívaných zdrojov (čas, pamäť).
Skillbox odporúča:
- Aplikovaný online kurz .
- Online kurz .
- Praktický ročný kurz .
Zdroj: habr.com
