Toen ik de prestaties van algoritmen bestudeerde, kwam ik dit tegen . Het geeft niet alleen een idee van hoe interviews worden afgenomen bij grote technologiebedrijven, maar laat je ook begrijpen hoe algoritmische problemen zo efficiënt mogelijk worden opgelost.
Dit artikel is een soort begeleiding bij de video. Daarin geef ik commentaar op alle getoonde oplossingen, plus mijn eigen versie van de oplossing in JavaScript. De nuances van elk algoritme worden ook besproken.
Herinnering: voor alle lezers van "Habr" - een korting van 10 roebel bij inschrijving voor een Skillbox-cursus met behulp van de promotiecode "Habr".
Skillbox beveelt aan: Praktische cursus .
Formulering van het probleem
We krijgen een geordende array en een specifieke waarde. Vervolgens wordt gevraagd om een functie te maken die waar of onwaar retourneert, afhankelijk van de vraag of de som van twee willekeurige getallen in de array gelijk kan zijn aan een bepaalde waarde.
Met andere woorden: zijn er twee gehele getallen in de array, x en y, die bij elkaar opgeteld gelijk zijn aan de opgegeven waarde?
Voorbeeld A
Als we een array [1, 2, 4, 9] krijgen en de waarde is 8, zal de functie false retourneren omdat geen van de twee getallen in de array opgeteld 8 kan zijn.
Voorbeeld B
Maar als het een array [1, 2, 4, 4] is en de waarde 8 is, moet de functie waar retourneren omdat 4 + 4 = 8.
Oplossing 1: brute kracht
Tijdcomplexiteit: O(N²).
Ruimtecomplexiteit: O(1).
De meest voor de hand liggende betekenis is het gebruik van een paar geneste lussen.
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;
};Deze oplossing is niet efficiënt omdat elke mogelijke som van twee elementen in de array wordt gecontroleerd en ook elk paar indices twee keer wordt vergeleken. (Bijvoorbeeld: wanneer i = 1 en j = 2 is eigenlijk hetzelfde als vergelijken met i = 2 en j = 1, maar in deze oplossing proberen we beide opties).
Omdat onze oplossing een paar geneste for-lussen gebruikt, is deze kwadratisch met de tijdcomplexiteit van O(N²).
Oplossing 2: binair zoeken
Tijdcomplexiteit: O(Nlog(N)).
Ruimtecomplexiteit: O(1).
Omdat de arrays geordend zijn, kunnen we met behulp van binair zoeken naar een oplossing zoeken. Dit is het meest efficiënte algoritme voor geordende arrays. Binair zoeken zelf heeft een looptijd van O(log(N)). U moet echter nog steeds een for-lus gebruiken om elk element te vergelijken met alle andere waarden.
Hier ziet u hoe een oplossing eruit zou kunnen zien. Om het duidelijk te maken, gebruiken we een aparte functie om binair zoeken te beheren. En ook de functie removeIndex(), die de versie van de array minus de gegeven index retourneert.
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;
};Het algoritme begint met index [0]. Vervolgens wordt er een versie van de array gemaakt met uitzondering van de eerste index en wordt er binair gezocht om te zien of een van de resterende waarden aan de array kan worden toegevoegd om de gewenste som te produceren. Deze actie wordt één keer uitgevoerd voor elk element in de array.
De for-lus zelf heeft een lineaire tijdscomplexiteit van O(N), maar binnen de for-lus voeren we een binaire zoekopdracht uit, die een algehele tijdscomplexiteit van O(Nlog(N)) oplevert. Deze oplossing is beter dan de vorige, maar er is nog ruimte voor verbetering.
Oplossing 3: lineaire tijd
Tijdcomplexiteit: O(N).
Ruimtecomplexiteit: O(1).
Nu zullen we het probleem oplossen, waarbij we onthouden dat de array is gesorteerd. De oplossing is om twee getallen te nemen: één aan het begin en één aan het einde. Als het resultaat afwijkt van het vereiste resultaat, wijzig dan het begin- en eindpunt.
Uiteindelijk zullen we ofwel de gewenste waarde tegenkomen en waar retourneren, of de begin- en eindpunten zullen convergeren en onwaar retourneren.
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;
};
Nu is alles in orde, de oplossing lijkt optimaal. Maar wie kan garanderen dat de array is besteld?
Wat dan?
Op het eerste gezicht hadden we eenvoudigweg eerst de array kunnen bestellen en vervolgens de bovenstaande oplossing kunnen gebruiken. Maar welke invloed heeft dit op de uitvoeringstijd?
Het beste algoritme is quicksort met tijdcomplexiteit O (Nlog (N)). Als we het in onze optimale oplossing gebruiken, zullen de prestaties veranderen van O(N) naar O(Nlog(N)). Is het mogelijk om een lineaire oplossing te vinden met een ongeordende array?
4-oplossing
Tijdcomplexiteit: O(N).
Ruimtecomplexiteit: O(N).
Ja, er is een lineaire oplossing; om dit te doen, moeten we een nieuwe array maken met de lijst met overeenkomsten waarnaar we op zoek zijn. De wisselwerking hier is meer geheugengebruik: het is de enige oplossing in het artikel met een ruimtecomplexiteit groter dan O(1).
Als de eerste waarde van een bepaalde array 1 is en de zoekwaarde 8 is, kunnen we de waarde 7 toevoegen aan de array "zoekwaarden".
Vervolgens kunnen we, terwijl we elk element van de array verwerken, de array met ‘zoekwaarden’ controleren en kijken of een daarvan gelijk is aan onze waarde. Zo ja, retourneer waar.
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;
};De basis van de oplossing is een for-lus, die, zoals we hierboven zagen, een lineaire tijdscomplexiteit van O(N) heeft.
Het tweede iteratieve deel van onze functie is Array.prototype.include(), een JavaScript-methode die waar of onwaar retourneert, afhankelijk van of de array de gegeven waarde bevat.
Om de tijdscomplexiteit van Array.prototype.includes() te achterhalen, kunnen we kijken naar de polyfill van MDN (en geschreven in JavaScript) of een methode gebruiken in de broncode van een JavaScript-engine zoals 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;
}
});
}Hier is het iteratieve deel van Array.prototype.include() de while-lus in stap 7 die (bijna) de gehele lengte van de gegeven array doorloopt. Dit betekent dat de tijdscomplexiteit ook lineair is. Omdat het altijd één stap achterloopt op onze hoofdarray, is de tijdscomplexiteit O (N + (N - 1)). Met behulp van Big O Notation vereenvoudigen we het tot O(N) - omdat N de grootste impact heeft bij het vergroten van de invoergrootte.
Met betrekking tot de ruimtelijke complexiteit is een extra array nodig waarvan de lengte de oorspronkelijke array weerspiegelt (minus één, ja, maar dat kan worden genegeerd), wat resulteert in O(N) ruimtelijke complexiteit. Welnu, een verhoogd geheugengebruik zorgt voor maximale efficiëntie van het algoritme.
Ik hoop dat je het artikel nuttig vindt als aanvulling op je video-interview. Het laat zien dat een eenvoudig probleem op verschillende manieren kan worden opgelost met verschillende hoeveelheden gebruikte bronnen (tijd, geheugen).
Skillbox beveelt aan:
- Toegepaste online cursus .
- Online cursus .
- Praktische jaarcursus .
Bron: www.habr.com