Když jsem studoval výkon algoritmů, narazil jsem na toto . Poskytuje nejen představu o tom, jak jsou vedeny rozhovory ve velkých technologických korporacích, ale také vám umožňuje porozumět tomu, jak jsou algoritmické problémy řešeny co nejúčinněji.
Tento článek je jakýmsi doprovodem k videu. V něm poskytuji komentáře ke všem zobrazeným řešením plus svou vlastní verzi řešení v JavaScriptu. Jsou také diskutovány nuance každého algoritmu.
Připomínáme: pro všechny čtenáře "Habr" - sleva 10 000 rublů při zápisu do jakéhokoli kurzu Skillbox pomocí propagačního kódu "Habr".
Skillbox doporučuje: Praktický kurz .
Formulace problému
Dostaneme uspořádané pole a konkrétní hodnotu. Poté je požádán o vytvoření funkce, která vrátí hodnotu true nebo false v závislosti na tom, zda se součet libovolných dvou čísel v poli může rovnat dané hodnotě.
Jinými slovy, existují v poli dvě celá čísla, x a y, která se po sečtení rovnají zadané hodnotě?
Příklad A
Pokud dostaneme pole [1, 2, 4, 9] a hodnota je 8, funkce vrátí hodnotu false, protože žádná dvě čísla v poli nemohou být součtem 8.
Příklad B
Ale pokud je to pole [1, 2, 4, 4] a hodnota je 8, funkce by měla vrátit true, protože 4 + 4 = 8.
Řešení 1: Hrubá síla
Časová složitost: O(N²).
Prostorová složitost: O(1).
Nejzřetelnějším významem je použití dvojice vnořených smyček.
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í není efektivní, protože kontroluje každý možný součet dvou prvků v poli a také dvakrát porovnává každý pár indexů. (Například, když i = 1 a j = 2 je ve skutečnosti totéž jako srovnání s i = 2 a j = 1, ale v tomto řešení zkoušíme obě možnosti).
Protože naše řešení používá pár vnořených smyček for, je kvadratické s časovou složitostí O(N²).
Řešení 2: Binární vyhledávání
Časová složitost: O(Nlog(N)).
Prostorová složitost: O(1).
Protože jsou pole uspořádaná, můžeme hledat řešení pomocí binárního vyhledávání. Toto je nejúčinnější algoritmus pro uspořádaná pole. Samotné binární vyhledávání má průběžnou dobu O(log(N)). Stále však musíte použít cyklus for ke kontrole každého prvku se všemi ostatními hodnotami.
Zde je návod, jak může vypadat řešení. Aby bylo vše jasné, používáme samostatnou funkci pro ovládání binárního vyhledávání. A také funkce removeIndex(), která vrátí verzi pole mínus daný index.
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;
};Algoritmus začíná od indexu [0]. Poté vytvoří verzi pole s vyloučením prvního indexu a pomocí binárního vyhledávání zjistí, zda lze do pole přidat některou ze zbývajících hodnot a vytvořit požadovaný součet. Tato akce se provede jednou pro každý prvek v poli.
Samotný cyklus for bude mít lineární časovou složitost O(N), ale uvnitř cyklu for provedeme binární vyhledávání, které dává celkovou časovou složitost O(Nlog(N)). Toto řešení je lepší než to 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í vyřešíme problém, přičemž si pamatujeme, že pole je tříděno. Řešením je vzít dvě čísla: jedno na začátku a jedno na konci. Pokud se výsledek liší od požadovaného, změňte počáteční a koncový bod.
Nakonec buď narazíme na požadovanou hodnotu a vrátíme hodnotu true, nebo se počáteční a koncový bod sblíží a vrátí hodnotu false.
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;
};
Nyní je vše v pořádku, řešení se zdá být optimální. Ale kdo může zaručit, že pole bylo objednáno?
Co pak?
Na první pohled jsme mohli jednoduše nejprve objednat pole a poté použít výše uvedené řešení. Jak to ale ovlivní dobu provedení?
Nejlepší algoritmus je quicksort s časovou složitostí O (Nlog (N)). Pokud jej použijeme v našem optimálním řešení, změní svůj výkon z O(N) na O(Nlog(N)). Je možné najít lineární řešení s neuspořádaným polem?
Řešení 4
Časová složitost: O(N).
Prostorová složitost: O(N).
Ano, existuje lineární řešení; k tomu musíme vytvořit nové pole obsahující seznam shod, které hledáme. Kompromisem je zde větší využití paměti: je to jediné řešení v článku s prostorovou složitostí větší než O(1).
Pokud je první hodnota daného pole 1 a hledaná hodnota je 8, můžeme do pole „hledané hodnoty“ přidat hodnotu 7.
Poté, jak zpracováváme každý prvek pole, můžeme zkontrolovat pole „hledaných hodnot“ a zjistit, zda se jedna z nich rovná naší hodnotě. Pokud ano, vraťte 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 smyčka for, která, jak jsme viděli výše, má lineární časovou složitost O(N).
Druhou iterativní částí naší funkce je Array.prototype.include(), metoda JavaScriptu, která vrátí hodnotu 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 poskytovanou MDN (a napsanou v JavaScriptu) nebo použít metodu ve zdrojovém kódu JavaScript motoru, 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() smyčka while v kroku 7, která (téměř) prochází celou délkou daného pole. To znamená, že i jeho časová složitost je lineární. Protože je vždy o krok za naším hlavním polem, časová složitost je O (N + (N - 1)). Pomocí Big O Notation to zjednodušíme na O(N) – protože právě N má největší dopad při zvětšování vstupní velikosti.
Pokud jde o prostorovou složitost, je potřeba další pole, jehož délka zrcadlí původní pole (mínus jedna, ano, ale to lze ignorovat), což má za následek prostorovou složitost O(N). Zvýšené využití paměti zajišťuje maximální efektivitu algoritmu.
Doufám, že vám článek bude užitečný jako doplněk vašeho videorozhovoru. Ukazuje, že jednoduchý problém lze vyřešit několika různými způsoby s různým množstvím použitých zdrojů (čas, paměť).
Skillbox doporučuje:
- Aplikovaný online kurz .
- Online kurz .
- Praktický roční kurz .
Zdroj: www.habr.com