Da jeg studerte ytelsen til algoritmer, kom jeg over dette . Det gir ikke bare en ide om hvordan intervjuer gjennomføres ved store teknologiselskaper, men lar deg også forstå hvordan algoritmiske problemer løses så effektivt som mulig.
Denne artikkelen er et slags akkompagnement til videoen. I den gir jeg kommentarer til alle løsningene som vises, pluss min egen versjon av løsningen i JavaScript. Nyansene til hver algoritme blir også diskutert.
Vi minner om: for alle lesere av "Habr" - en rabatt på 10 000 rubler når du melder deg på et hvilket som helst Skillbox-kurs ved å bruke kampanjekoden "Habr".
Skillbox anbefaler: Praktisk kurs .
Formulering av problemet
Vi får en ordnet matrise og en spesifikk verdi. Det blir deretter bedt om å lage en funksjon som returnerer sant eller usant avhengig av om summen av to tall i matrisen kan være lik en gitt verdi.
Med andre ord, er det to heltall i matrisen, x og y, som når de legges sammen tilsvarer den angitte verdien?
Eksempel A
Hvis vi får en matrise [1, 2, 4, 9] og verdien er 8, vil funksjonen returnere falsk fordi ingen to tall i matrisen kan legge sammen til 8.
Eksempel B
Men hvis det er en matrise [1, 2, 4, 4] og verdien er 8, skal funksjonen returnere sann fordi 4 + 4 = 8.
Løsning 1: Brut force
Tidskompleksitet: O(N²).
Romkompleksitet: O(1).
Den mest åpenbare betydningen er å bruke et par nestede løkker.
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;
};Denne løsningen er ikke effektiv fordi den sjekker hver mulig sum av to elementer i matrisen og sammenligner også hvert indekspar to ganger. (For eksempel, når i = 1 og j = 2 er faktisk det samme som å sammenligne med i = 2 og j = 1, men i denne løsningen prøver vi begge alternativene).
Fordi løsningen vår bruker et par nestede for løkker, er den kvadratisk med O(N²) tidskompleksitet.
Løsning 2: Binært søk
Tidskompleksitet: O(Nlog(N)).
Romkompleksitet: O(1).
Siden matrisene er ordnet, kan vi søke etter en løsning ved hjelp av binært søk. Dette er den mest effektive algoritmen for ordnede arrays. Binærsøk i seg selv har en kjøretid på O(log(N)). Du må imidlertid fortsatt bruke en for-løkke for å sjekke hvert element mot alle andre verdier.
Slik kan en løsning se ut. For å gjøre ting klart bruker vi en egen funksjon for å kontrollere binært søk. Og også removeIndex()-funksjonen, som returnerer versjonen av matrisen minus den gitte indeksen.
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;
};Algoritmen starter fra indeks [0]. Den oppretter deretter en versjon av matrisen uten den første indeksen og bruker binært søk for å se om noen av de gjenværende verdiene kan legges til matrisen for å produsere den ønskede summen. Denne handlingen utføres én gang for hvert element i matrisen.
Selve for-løkken vil ha en lineær tidskompleksitet på O(N), men inne i for-løkken utfører vi et binært søk, som gir en samlet tidskompleksitet på O(Nlog(N)). Denne løsningen er bedre enn den forrige, men det er fortsatt rom for forbedring.
Løsning 3: Lineær tid
Tidskompleksitet: O(N).
Romkompleksitet: O(1).
Nå skal vi løse problemet, og huske at matrisen er sortert. Løsningen er å ta to tall: ett i begynnelsen og ett på slutten. Hvis resultatet avviker fra det påkrevde, endrer du start- og sluttpunktene.
Til slutt vil vi enten møte den ønskede verdien og returnere sann, eller start- og sluttpunktene vil konvergere og returnere usann.
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;
};
Nå er alt bra, løsningen ser ut til å være optimal. Men hvem kan garantere at arrayet ble bestilt?
Hva da?
Ved første øyekast kunne vi ganske enkelt ha bestilt matrisen først og deretter brukt løsningen ovenfor. Men hvordan vil dette påvirke gjennomføringstiden?
Den beste algoritmen er quicksort med tidskompleksitet O (Nlog (N)). Hvis vi bruker den i vår optimale løsning, vil den endre ytelsen fra O(N) til O(Nlog(N)). Er det mulig å finne en lineær løsning med en uordnet matrise?
4-løsning
Tidskompleksitet: O(N).
Romkompleksitet: O(N).
Ja, det er en lineær løsning; for å gjøre dette må vi lage en ny matrise som inneholder listen over treff som vi ser etter. Avveiningen her er mer minnebruk: det er den eneste løsningen i papiret med plasskompleksitet større enn O(1).
Hvis den første verdien av en gitt matrise er 1 og søkeverdien er 8, kan vi legge til verdien 7 til «search values»-matrisen.
Så, mens vi behandler hvert element i matrisen, kan vi sjekke matrisen med "søkeverdier" og se om en av dem er lik verdien vår. Hvis ja, returner sant.
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;
};Grunnlaget for løsningen er en for-løkke, som, som vi så ovenfor, har en lineær tidskompleksitet på O(N).
Den andre iterative delen av funksjonen vår er Array.prototype.include(), en JavaScript-metode som vil returnere true eller false avhengig av om matrisen inneholder den gitte verdien.
For å finne ut tidskompleksiteten til Array.prototype.includes(), kan vi se på polyfillen levert av MDN (og skrevet i JavaScript) eller bruke en metode i kildekoden til 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;
}
});
}Her er den iterative delen av Array.prototype.include() while-løkken i trinn 7 som (nesten) krysser hele lengden av den gitte matrisen. Dette betyr at tidskompleksiteten også er lineær. Vel, siden det alltid er ett skritt bak hovedmatrisen vår, er tidskompleksiteten O (N + (N - 1)). Ved å bruke Big O Notation forenkler vi det til O(N) – fordi det er N som har størst innvirkning når man øker inngangsstørrelsen.
Når det gjelder romlig kompleksitet, er det nødvendig med en ekstra matrise hvis lengde speiler den opprinnelige matrisen (minus én, ja, men det kan ignoreres), noe som resulterer i O(N) romlig kompleksitet. Vel, økt minnebruk sikrer maksimal effektivitet av algoritmen.
Jeg håper du finner artikkelen nyttig som et supplement til videointervjuet ditt. Den viser at et enkelt problem kan løses på flere forskjellige måter med ulik mengde ressurser som brukes (tid, minne).
Skillbox anbefaler:
- Anvendt nettkurs .
- Online kurs .
- Praktisk årskurs .
Kilde: www.habr.com