Kun tutkin algoritmien suorituskykyä, törmäsin tähän . Se ei vain anna käsitystä siitä, kuinka haastatteluja tehdään suurissa teknologiayrityksissä, vaan myös auttaa ymmärtämään, kuinka algoritmiset ongelmat ratkaistaan mahdollisimman tehokkaasti.
Tämä artikkeli on eräänlainen liite videolle. Siinä kommentoin kaikkia esitettyjä ratkaisuja sekä omaa JavaScript-versiota ratkaisusta. Jokaisen algoritmin vivahteita käsitellään myös.
Muistutamme sinua: kaikille "Habrin" lukijoille - 10 000 ruplan alennus ilmoittautuessaan mille tahansa Skillbox-kurssille "Habr" -tarjouskoodilla.
Skillbox suosittelee: Käytännön kurssi .
Ongelma
Meille annetaan tilattu taulukko ja tietty arvo. Sitten sitä pyydetään luomaan funktio, joka palauttaa tosi tai epätosi sen mukaan, voiko taulukon minkä tahansa kahden luvun summa olla yhtä suuri kuin annettu arvo.
Toisin sanoen, onko taulukossa kaksi kokonaislukua, x ja y, jotka yhteenlaskettuina vastaavat määritettyä arvoa?
Esimerkki A
Jos meille annetaan taulukko [1, 2, 4, 9] ja arvo on 8, funktio palauttaa arvon epätosi, koska taulukon kahdella numerolla ei voi olla 8.
Esimerkki B
Mutta jos se on taulukko [1, 2, 4, 4] ja arvo on 8, funktion pitäisi palauttaa tosi, koska 4 + 4 = 8.
Ratkaisu 1: Raaka voima
Aika monimutkaisuus: O(N²).
Avaruuden monimutkaisuus: O(1).
Ilmeisin merkitys on käyttää sisäkkäisiä silmukoita.
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;
};Tämä ratkaisu ei ole tehokas, koska se tarkistaa taulukon jokaisen mahdollisen kahden elementin summan ja vertaa myös jokaista indeksiparia kahdesti. (Esimerkiksi kun i = 1 ja j = 2 on itse asiassa sama kuin verrattaessa i = 2 ja j = 1, mutta tässä ratkaisussa kokeillaan molempia vaihtoehtoja).
Koska ratkaisumme käyttää sisäkkäisten silmukoiden paria, se on neliöllinen O(N²)-aikakompleksisuudella.
Ratkaisu 2: Binäärihaku
Aika monimutkaisuus: O(Nlog(N)).
Avaruuden monimutkaisuus: O(1).
Koska taulukot ovat järjestettyjä, voimme etsiä ratkaisua binäärihaulla. Tämä on tehokkain algoritmi järjestetyille taulukoille. Itse binäärihaun suoritusaika on O(log(N)). Sinun on kuitenkin silti käytettävä for-silmukkaa tarkistaaksesi kunkin elementin kaikkiin muihin arvoihin.
Ratkaisu voi näyttää tältä. Selvittääksemme asiat, käytämme erillistä toimintoa binäärihaun ohjaamiseen. Ja myös removeIndex()-funktio, joka palauttaa taulukon version miinus annettu indeksi.
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;
};Algoritmi alkaa indeksistä [0]. Sitten se luo taulukosta version, joka ei sisällä ensimmäistä indeksiä, ja käyttää binaarihakua nähdäkseen, voidaanko jokin jäljellä olevista arvoista lisätä taulukkoon halutun summan tuottamiseksi. Tämä toiminto suoritetaan kerran jokaiselle taulukon elementille.
Itse for-silmukalla on lineaarinen aikamonimutkaisuus O(N), mutta for-silmukan sisällä suoritamme binäärihaun, joka antaa kokonaisaikaisen monimutkaisuuden O(Nlog(N)). Tämä ratkaisu on parempi kuin edellinen, mutta parantamisen varaa on vielä.
Ratkaisu 3: Lineaarinen aika
Aika monimutkaisuus: O(N).
Avaruuden monimutkaisuus: O(1).
Nyt ratkaisemme ongelman muistaen, että taulukko on lajiteltu. Ratkaisu on ottaa kaksi numeroa: yksi alussa ja yksi lopussa. Jos tulos poikkeaa vaaditusta, muuta aloitus- ja lopetuskohtaa.
Lopulta joko kohtaamme halutun arvon ja palautamme tosi, tai aloitus- ja loppupisteet lähentyvät ja palauttavat epätosi.
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;
};
Nyt kaikki on hyvin, ratkaisu näyttää olevan optimaalinen. Mutta kuka voi taata, että sarja on tilattu?
Mitä sitten?
Ensi silmäyksellä olisimme voineet yksinkertaisesti tilata taulukon ensin ja sitten käyttää yllä olevaa ratkaisua. Mutta miten tämä vaikuttaa toteutusaikaan?
Paras algoritmi on pikalajittelu aikakompleksisuudella O (Nlog (N)). Jos käytämme sitä optimaalisessa ratkaisussamme, se muuttaa suorituskykynsä O(N):sta O(Nlog(N)). Onko mahdollista löytää lineaarinen ratkaisu järjestämättömällä taulukolla?
4-ratkaisu
Aika monimutkaisuus: O(N).
Avaruuden monimutkaisuus: O(N).
Kyllä, on olemassa lineaarinen ratkaisu; tätä varten meidän on luotava uusi taulukko, joka sisältää etsimiemme osumien luettelon. Kompromissi tässä on enemmän muistin käyttöä: se on paperin ainoa ratkaisu, jonka tilan monimutkaisuus on suurempi kuin O(1).
Jos tietyn taulukon ensimmäinen arvo on 1 ja hakuarvo on 8, voimme lisätä arvon 7 "hakuarvot" -taulukkoon.
Sitten kun käsittelemme taulukon jokaista elementtiä, voimme tarkistaa "hakuarvojen" taulukon ja nähdä, vastaako jokin niistä arvoamme. Jos kyllä, palauta tosi.
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;
};Ratkaisun perustana on for-silmukka, jonka lineaarinen aikakompleksisuus, kuten edellä näimme, on O(N).
Funktiomme toinen iteratiivinen osa on Array.prototype.include(), JavaScript-metodi, joka palauttaa tosi tai epätosi sen mukaan, sisältääkö taulukko annetun arvon.
Array.prototype.includes(:n) aikamonimutkaisuuden selvittämiseksi voimme tarkastella MDN:n tarjoamaa polytäyttöä (ja kirjoitettu JavaScriptillä) tai käyttää menetelmää JavaScript-moottorin lähdekoodissa, kuten 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;
}
});
}Tässä Array.prototype.include():n iteratiivinen osa on while-silmukka vaiheessa 7, joka (melkein) kulkee annetun taulukon koko pituuden. Tämä tarkoittaa, että sen aikamonimutkaisuus on myös lineaarinen. No, koska se on aina askeleen jäljessä päätaulukostamme, aikamonimutkaisuus on O (N + (N - 1)). Isoa O-merkintää käyttämällä yksinkertaistamme sen muotoon O(N), koska N:llä on suurin vaikutus syötekokoa kasvatettaessa.
Tilallisen monimutkaisuuden osalta tarvitaan lisätaulukko, jonka pituus heijastaa alkuperäistä taulukkoa (miinus yksi, kyllä, mutta se voidaan jättää huomiotta), mikä johtaa O(N) spatiaaliseen monimutkaisuuteen. No, lisääntynyt muistin käyttö varmistaa algoritmin maksimaalisen tehokkuuden.
Toivon, että artikkelista on hyötyä videohaastattelusi täydennykseksi. Se osoittaa, että yksinkertainen ongelma voidaan ratkaista useilla eri tavoilla erilaisilla käytetyillä resursseilla (aika, muisti).
Skillbox suosittelee:
- Sovellettu verkkokurssi .
- Verkkokurssi .
- Käytännön vuoden kurssi .
Lähde: will.com