
NÀr jag studerade algoritmers prestanda stötte jag pÄ . Den ger inte bara en inblick i hur intervjuer gÄr till i stora teknikföretag, utan hjÀlper ocksÄ till att förstÄ hur algoritmiska problem löses pÄ det mest effektiva sÀttet.
Denna artikel Àr ett slags komplement till videon. HÀr ger jag kommentarer till alla visade lösningar samt min egen version av lösningen i JavaScript. Dessutom diskuteras detaljerna kring varje algoritm.
PĂ„minnelse: för alla lĂ€sare av "Habr" â 10 000 rubel rabatt vid registrering för vilken kurs som helst pĂ„ Skillbox med rabattkoden "Habr".
Skillbox rekommenderar: Praktisk kurs .
UppgiftsstÀllande
Vi fÄr en sorterad lista och ett givet vÀrde. Vi ombeds sedan skapa en funktion som returnerar true eller false, beroende pÄ om summan av tvÄ vilka som helst av talen i listan kan bli lika med det givna vÀrdet.
Med andra ord, finns det tvÄ heltal x och y i listan som blir lika med det angivna vÀrdet nÀr de adderas?
Exempel A
Om vi fÄr listan [1, 2, 4, 9] och vÀrdet 8, kommer funktionen att returnera false, eftersom inga tvÄ tal frÄn listan kan ge 8 nÀr de adderas.
Exempel B
Men om listan Àr [1, 2, 4, 4] och vÀrdet 8, bör funktionen returnera true, eftersom 4 + 4 = 8.
Lösning 1. Brute Force
Tidskomplexitet: O(NÂČ).
Rymdkomplexitet: O(1).
Det mest uppenbara tillvÀgagÄngssÀttet Àr att anvÀnda ett par inre loopar.
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;
};Denna lösning kan inte kallas effektiv, eftersom den kontrollerar varje möjlig summa av tvĂ„ element i listan, och den jĂ€mför ocksĂ„ varje indexpar tvĂ„ gĂ„nger. (Till exempel, nĂ€r i = 1 och j = 2 â Ă€r det faktiskt samma som att jĂ€mföra med i = 2 och j = 1, men i denna lösning försöker vi bĂ„da alternativen).
Eftersom vĂ„r lösning anvĂ€nder ett par inre for-loopar Ă€r den kvadratisk med tidskomplexiteten O (NÂČ).
Lösning 2. BinÀr sökning
Tidskomplexitet: O(Nlog(N)).
Rymdkomplexitet: O(1).
Eftersom listorna Àr sorterade, kan vi söka efter en lösning med hjÀlp av binÀr sökning. Detta Àr den mest effektiva algoritmen för sorterade listor. SjÀlva den binÀra sökningen har en körtid pÄ O (log (N)). Men vi behöver ÀndÄ anvÀnda en for-loop för att kontrollera varje element mot alla andra vÀrden.
SÄ hÀr kan en lösning se ut. För att allt ska vara klart och tydligt anvÀnder vi en separat funktion för att kontrollera det binÀra sökandet. Dessutom en funktion removeIndex() som returnerar en version av arrayen utan det angivna indexet.
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;
};Algoritmen börjar med index [0]. DÀrefter skapas en version av arrayen som utesluter det första indexet, och den binÀra sökningen anvÀnds för att kontrollera om nÄgot av de ÄterstÄende vÀrdena kan lÀggas till arrayen för att uppnÄ den önskade summan. Denna ÄtgÀrd utförs en gÄng för varje element i arrayen.
SjÀlva for-loopen kommer att ha en linjÀr tidskomplexitet O(N), men inom for-loopen utför vi en binÀr sökning, vilket ger en total tidskomplexitet O(N log(N)). Denna lösning Àr bÀttre Àn den föregÄende, men det finns fortfarande utrymme för förbÀttring.
Lösning 3. LinjÀr tid
Tidskomplexitet: O(N).
Rymdkomplexitet: O(1).
Nu ska vi lösa problemet under antagandet att arrayen Àr sorterad. Lösningen bestÄr i att ta tvÄ siffror: en i början och en i slutet. Om resultatet avviker frÄn det som krÀvs, byter vi start- och slutpunkten.
Till slut kommer vi antingen att trÀffa det önskade vÀrdet och returnera true, eller sÄ kommer start- och slutpunkten att mötas och returnera 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;
};Nu Àr allt bra, lösningen verkar vara optimal. Men vem ger garantin att arrayen var sorterad?
Vad gör vi dÄ?
Vid första anblick kan vi först bara sortera arrayen och sedan anvÀnda ovanstÄende lösning. Men hur skulle det pÄverka körtiden?
Den bÀsta algoritmen Àr QuickSort med tidskomplexitet O(N log(N)). Om vi anvÀnder den i vÄr optimala lösning kommer dess prestanda att Àndras frÄn O(N) till O(N log(N)). Finns det en linjÀr lösning med en osorterad array?
Lösning 4
Tidskomplexitet: O(N).
Rumskomplexitet: O(N).
Ja, en linjÀr lösning finns. För detta behöver vi skapa en ny array som innehÄller den lista av matchningar som vi letar efter. Kompromissen hÀr Àr en mer aktiv anvÀndning av minnet: detta Àr den enda lösningen i artikeln med en rumslig komplexitet som överstiger O (1).
Om det första vÀrdet i denna array Àr 1 och det sökta vÀrdet Àr 8, kan vi lÀgga till vÀrdet 7 i arrayen "sökvÀrden".
Sedan, genom att bearbeta varje element i arrayen, kan vi kontrollera arrayen "sökvÀrden" och se om nÄgot av dem Àr lika med vÄrt vÀrde. Om ja, returnerar vi 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;
};Grunden för lösningen Àr en for-loop, som vi sÄg ovan, och som har en linjÀr tidskomplexitet O (N).
Den andra iterativa delen av vÄr funktion Àr Array.prototype.includes(), en JavaScript-metod som returnerar true eller false beroende pÄ om arrayen innehÄller det angivna vÀrdet.
För att ta reda pÄ tidskomplexiteten för Array.prototype.includes() kan vi övervÀga en polyfill som tillhandahÄlls av MDN (och som Àr skriven i JavaScript), eller anvÀnda metoden i kÀllkoden för en JavaScript-motor, som 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;
}
});
}HĂ€r Ă€r den iterativa delen av Array.prototype.includes() en while-loop i steg 7 som (nĂ€stan) gĂ„r igenom hela lĂ€ngden av den givna arrayen. Detta innebĂ€r att dess tidskomplexitet ocksĂ„ Ă€r linjĂ€r. Eftersom den alltid ligger ett steg bakom vĂ„r huvudarray, Ă€r tidskomplexiteten O (N + (N - 1)). Genom att anvĂ€nda Big O-notationen förenklar vi den till O (N) â eftersom det Ă€r N som har störst pĂ„verkan nĂ€r inmatningsstorleken ökar.
NÀr det gÀller rumslig komplexitet behövs en extra array vars lÀngd speglar den ursprungliga arrayen (minus ett, ja, men det kan ignoreras) vilket ger en rumslig komplexitet av O (N). Den ökade anvÀndningen av minnet sÀkerstÀller maximal effektivitet i algoritmen.
Jag hoppas att artikeln kommer att vara anvÀndbar för dig som ett komplement till videointervjun. Den visar att en enkel uppgift kan lösas pÄ flera olika sÀtt med olika mÀngder av anvÀnda resurser (tid, minne).
Skillbox rekommenderar:
- TillÀmplig onlinekurs .
- Onlinekurs .
- Praktisk Ärskurs .
KĂ€lla: habr.com
