Když jsem se zabýval studiem výkonu algoritmů, narazil jsem na . Nejen že poskytuje představu o tom, jak probíhají pohovory ve velkých technologických společnostech, ale také pomáhá pochopit, jak se řeší algoritmické úkoly, a to co nejefektivněji.
Tento článek je jakýmsi doprovodem k videu. Uvádím v něm komentáře k všem uvedeným řešením, plus svou vlastní verzi řešení v JavaScriptu. Také se probírají nuance každého algoritmu.
Připomínáme: pro všechny čtenáře "Habra" – sleva 10 000 korun při registraci na jakýkoli kurz Skillbox s promokódem "Habr".
Skillbox doporučuje: Praktický kurz .
Formulace úkolu
Dostáváme se k uspořádanému poli a určité hodnotě. Poté jsme požádáni, abychom vytvořili funkci, která vrací true nebo false, v závislosti na tom, zda může být součet jakýchkoli dvou čísel z pole roven zadané hodnotě.
Jinými slovy, existují v poli dvě celá čísla x a y, která po sečtení dávají uvedenou hodnotu?
Příklad A
Pokud nám dali pole [1, 2, 4, 9] a hodnotu 8, funkce vrátí false, protože žádná dvě čísla z pole nemohou dát 8 v součtu.
Příklad B
Ale pokud je to pole [1, 2, 4, 4] a hodnota 8, funkce by měla vrátit true, protože 4 + 4 = 8.
Řešení 1. Brutforce
Časová složitost: O(N²).
Prostorová složitost: O(1).
Nejvíce očividný způsob je použití páru vnořených cyklů.
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 řešení nelze považovat za efektivní, protože kontroluje každou možnou sumu dvou prvků v poli, a také porovnává každý pár indexů dvakrát. (Například, když i = 1 a j = 2, je to vlastně totéž jako porovnávat s i = 2 a j = 1, ale v tomto řešení zkoušíme oba varianty).
Jelikož naše řešení používá pár vnořených cyklů for, je kvadratické s časovou složitostí O(N²).
Řešení 2. Dvojité (binární) vyhledávání
Časová složitost: O(Nlog(N)).
Prostorová složitost: O(1).
Jelikož jsou pole uspořádána, můžeme hledat řešení pomocí binárního vyhledávání. To je nejefektivnější algoritmus pro uspořádaná pole. Samotné binární vyhledávání má časovou složitost O(log(N)). Nicméně je stále potřeba použít cyklus for, abychom zkontrolovali každý prvek vůči všem ostatním hodnotám.
Takto může vypadat řešení. Aby bylo vše jasné, použijeme samostatnou funkci pro kontrolu binárního vyhledávání. A také funkci removeIndex (), která vrací verzi pole bez zadané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číná na indexu [0]. Poté vytváří verzi pole, která vylučuje první index, a používá binární vyhledávání, aby zjistil, zda lze k poli přidat některou z zbývajících hodnot pro dosažení požadovaného součtu. Tato operace se provádí jednou pro každý prvek v poli.
Sám o sobě bude cyklus for mít lineární časovou složitost O (N), ale uvnitř cyklu for provádíme binární vyhledávání, což dává celkovou časovou složitost O (N log (N)). Toto řešení je lepší než předchozí, ale stále je co zlepšovat.
Řešení 3. Lineární čas
Časová složitost: O(N).
Prostorová složitost: O(1).
Nyní budeme řešit úkol s vědomím, že pole je seřazeno. Řešení spočívá v tom, že vezmeme dvě čísla: jedno na začátku a jedno na konci. Pokud se výsledek liší od požadovaného, změníme počáteční a koncovou bod.
Nakonec buď narazíme na požadovanou hodnotu a vrátíme true, nebo se počáteční a koncové body setkají a vrátí 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;
};Nyní je vše v pořádku, řešení se zdá být optimální. Ale kdo zaručí, že pole bylo seřazeno?
Co teď?
Na první pohled bychom mohli nejprve jednoduše seřadit pole a poté použít výše uvedené řešení. Jak by to ovlivnilo čas provádění?
Nejlepší algoritmus je rychlé třídění s časovou složitostí O (N log (N)). Pokud ho použijeme v našem optimálním řešení, změní to jeho výkon z O (N) na O (N log (N)). Je možné najít lineární řešení pro neuspořádané pole?
Řešení 4
Časová složitost: O(N).
Prostorová složitost: O(N).
Ano, lineární řešení existuje, k tomu je třeba vytvořit nové pole obsahující seznam shod, které hledáme. Kompromisem je zde aktivnější využití paměti: toto je jediné řešení v článku s prostorovou složitostí přesahující O (1).
Pokud je první hodnota daného pole rovna 1 a hledaná hodnota je 8, můžeme přidat hodnotu 7 do pole „hledaných hodnot“.
Pak, při zpracovávání každého prvku pole, můžeme zkontrolovat pole „hledaných hodnot“ a zjistit, zda se některá z nich rovná naší hodnotě. Pokud ano, vrátí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ákladem řešení je cyklus for, který, jak jsme viděli výše, má lineární časovou složitost O (N).
Druhá iterativní část naší funkce — Array.prototype.include (), metoda JavaScriptu, která vrátí true nebo false v závislosti na tom, zda pole obsahuje danou hodnotu.
Abychom zjistili časovou složitost Array.prototype.includes (), můžeme se podívat na polyfill poskytovaný MDN (a napsaný v JavaScriptu) nebo využít metodu v zdrojovém kódu JavaScriptového enginu, jako 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;
}
});
}Zde je iterativní část Array.prototype.include () cyklus while ve kroku 7, který (téměř) pokrývá celou délku daného pole. To znamená, že jeho časová složitost je také lineární. A protože je vždy o krok pozadu za naším hlavním polem, časová složitost se rovná O (N + (N — 1)). Využitím Big O Notation ji zjednodušíme na O (N) — protože N má největší vliv při zvyšování velikosti vstupu.
Pokud jde o prostorovou složitost, je potřeba další pole, jehož délka odráží původní pole (minus jedna, ano, ale to lze ignorovat), což vede k prostorové složitosti O (N). No a zvýšené využití paměti zajišťuje maximální efektivitu algoritmu.
Doufám, že článek bude pro vás užitečný jako doplněk k video pohovoru. Ukazuje, že jednoduchý úkol může být řešen několika různými způsoby s různým množstvím využívaných zdrojů (čas, paměť).
Skillbox doporučuje:
- Aplikovaný online kurz .
- Online kurz .
- Praktický roční kurz .
Zdroj: habr.com
