Toe ek die werkverrigting van algoritmes bestudeer het, het ek hierop afgekom . Dit gee nie net 'n idee van hoe onderhoude by groot tegnologie-ondernemings gevoer word nie, maar laat jou ook toe om te verstaan hoe algoritmiese probleme so doeltreffend moontlik opgelos word.
Hierdie artikel is 'n soort begeleiding van die video. Daarin lewer ek kommentaar op al die oplossings wat gewys word, plus my eie weergawe van die oplossing in JavaScript. Die nuanses van elke algoritme word ook bespreek.
Ons herinner: vir alle lesers van "Habr" - 'n afslag van 10 000 roebels wanneer u inskryf vir enige Skillbox-kursus met behulp van die "Habr"-promosiekode.
Skillbox beveel aan: Praktiese kursus .
Probleemstelling
Ons kry 'n geordende skikking en 'n spesifieke waarde. Dit word dan gevra om 'n funksie te skep wat waar of onwaar gee, afhangende van of die som van enige twee getalle in die skikking gelyk kan wees aan 'n gegewe waarde.
Met ander woorde, is daar twee heelgetalle in die skikking, x en y, wat, wanneer saamgetel, gelyk is aan die gespesifiseerde waarde?
Voorbeeld A
As ons 'n skikking [1, 2, 4, 9] gegee word en die waarde is 8, sal die funksie vals terugkeer omdat geen twee getalle in die skikking tot 8 kan optel nie.
Voorbeeld B
Maar as dit 'n skikking [1, 2, 4, 4] is en die waarde is 8, moet die funksie waar terugkeer omdat 4 + 4 = 8.
Oplossing 1: Brute krag
Tydskompleksiteit: O(N²).
Ruimtekompleksiteit: O(1).
Die mees voor die hand liggende betekenis is om 'n paar geneste lusse te gebruik.
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;
};Hierdie oplossing is nie doeltreffend nie, want dit kontroleer elke moontlike som van twee elemente in die skikking en vergelyk ook elke paar indekse twee keer. (Byvoorbeeld, wanneer i = 1 en j = 2 is eintlik dieselfde as om te vergelyk met i = 2 en j = 1, maar in hierdie oplossing probeer ons albei opsies).
Omdat ons oplossing 'n paar geneste vir lusse gebruik, is dit kwadraties met O(N²) tydkompleksiteit.
Oplossing 2: Binêre Soek
Tydskompleksiteit: O(Nlog(N)).
Ruimtekompleksiteit: O(1).
Aangesien die skikkings georden is, kan ons na 'n oplossing soek deur binêre soektog te gebruik. Dit is die mees doeltreffende algoritme vir geordende skikkings. Binêre soektog self het 'n looptyd van O(log(N)). Jy moet egter steeds 'n for-lus gebruik om elke element teen alle ander waardes te kontroleer.
Hier is hoe 'n oplossing kan lyk. Om dinge duidelik te maak, gebruik ons 'n aparte funksie om binêre soektog te beheer. En ook die removeIndex() funksie, wat die weergawe van die skikking minus die gegewe indeks terugstuur.
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;
};Die algoritme begin vanaf indeks [0]. Dit skep dan 'n weergawe van die skikking wat die eerste indeks uitsluit en gebruik binêre soektog om te sien of enige van die oorblywende waardes by die skikking gevoeg kan word om die verlangde som te produseer. Hierdie aksie word een keer vir elke element in die skikking uitgevoer.
Die for-lus self sal 'n lineêre tydkompleksiteit van O(N) hê, maar binne die for-lus voer ons 'n binêre soektog uit, wat 'n algehele tydkompleksiteit van O(Nlog(N) gee). Hierdie oplossing is beter as die vorige een, maar daar is nog ruimte vir verbetering.
Oplossing 3: Lineêre tyd
Tydskompleksiteit: O(N).
Ruimtekompleksiteit: O(1).
Nou sal ons die probleem oplos en onthou dat die skikking gesorteer is. Die oplossing is om twee getalle te neem: een aan die begin en een aan die einde. As die resultaat verskil van die vereiste een, verander dan die begin- en eindpunte.
Uiteindelik sal ons óf die verlangde waarde teëkom en waar terugkeer, óf die begin- en eindpunte sal konvergeer en vals terugkeer.
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;
};
Nou is alles reg, die oplossing blyk optimaal te wees. Maar wie kan waarborg dat die skikking bestel is?
Wat dan?
Met die eerste oogopslag kon ons eenvoudig eers die skikking bestel het en dan die oplossing hierbo gebruik het. Maar hoe sal dit die uitvoeringstyd beïnvloed?
Die beste algoritme is quicksort met tydkompleksiteit O (Nlog (N)). As ons dit in ons optimale oplossing gebruik, sal dit sy werkverrigting van O(N) na O(Nlog(N) verander). Is dit moontlik om 'n lineêre oplossing met 'n ongeordende skikking te vind?
4 Oplossing
Tydskompleksiteit: O(N).
Ruimtekompleksiteit: O(N).
Ja, daar is 'n lineêre oplossing; om dit te doen, moet ons 'n nuwe skikking skep wat die lys van pasmaats bevat waarna ons soek. Die uitruil hier is meer geheuegebruik: dit is die enigste oplossing in die vraestel met ruimtekompleksiteit groter as O(1).
As die eerste waarde van 'n gegewe skikking 1 is en die soekwaarde is 8, kan ons die waarde 7 by die "soekwaardes"-skikking voeg.
Dan, terwyl ons elke element van die skikking verwerk, kan ons die skikking van "soekwaardes" nagaan en kyk of een daarvan gelyk is aan ons waarde. Indien wel, gee 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;
};Die basis van die oplossing is 'n for-lus, wat, soos ons hierbo gesien het, 'n lineêre tydkompleksiteit van O(N) het.
Die tweede iteratiewe deel van ons funksie is Array.prototype.include(), 'n JavaScript-metode wat waar of onwaar sal terugkeer, afhangende van of die skikking die gegewe waarde bevat.
Om die tydskompleksiteit van Array.prototype.includes() uit te vind, kan ons kyk na die polyfill wat deur MDN verskaf word (en geskryf in JavaScript) of 'n metode in die bronkode van 'n JavaScript-enjin soos Google V8 (C++) gebruik.
// 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 die iteratiewe deel van Array.prototype.include() die while lus in stap 7 wat (amper) die hele lengte van die gegewe skikking deurkruis. Dit beteken dat die tydskompleksiteit daarvan ook lineêr is. Wel, aangesien dit altyd een stap agter ons hoofskikking is, is die tydkompleksiteit O (N + (N - 1)). Deur Groot O-notasie te gebruik, vereenvoudig ons dit na O(N) - want dit is N wat die grootste impak het wanneer die invoergrootte vergroot word.
Wat ruimtelike kompleksiteit betref, is 'n bykomende skikking nodig waarvan die lengte die oorspronklike skikking weerspieël (minus een, ja, maar dit kan geïgnoreer word), wat lei tot O(N) ruimtelike kompleksiteit. Wel, verhoogde geheuegebruik verseker maksimum doeltreffendheid van die algoritme.
Ek hoop jy vind die artikel nuttig as 'n aanvulling tot jou video-onderhoud. Dit wys dat 'n eenvoudige probleem op verskeie maniere opgelos kan word met verskillende hoeveelhede hulpbronne wat gebruik word (tyd, geheue).
Skillbox beveel aan:
- Toegepaste aanlyn kursus .
- Aanlyn kursus .
- Praktiese jaarkursus .
Bron: will.com