Wéi ech d'Performance vun Algorithmen studéiert hunn, sinn ech op dëst begéint . Et gëtt net nëmmen eng Iddi wéi Interviewe bei groussen Technologiekonzerner duerchgefouert ginn, awer erlaabt Iech och ze verstoen wéi algorithmesch Probleemer sou effizient wéi méiglech geléist ginn.
Dësen Artikel ass eng Zort Begleedung zum Video. An et ginn ech Kommentarer iwwer all déi gewisen Léisungen, plus meng eege Versioun vun der Léisung am JavaScript. D'Nuancen vun all Algorithmus ginn och diskutéiert.
Mir erënneren Iech: fir all Habr Lieser - eng Remise vun 10 Rubel wann Dir Iech an all Skillbox Cours aschreift mat dem Habr Promo Code.
Skillbox recommandéiert: Praktesch Cours .
Problemerklärung
Mir kréien eng bestallt Array an e spezifesche Wäert. Et gëtt dann opgefuerdert eng Funktioun ze kreéieren déi richteg oder falsch zréckkënnt ofhängeg ob d'Zomm vun zwou Zuelen an der Array e bestëmmte Wäert gläich kann.
An anere Wierder, ginn et zwee ganz Zuelen an der Array, x an y, déi wann se zesummegefaasst sinn de spezifizéierte Wäert gläich sinn?
Beispill A
Wa mir en Array kréien [1, 2, 4, 9] an de Wäert ass 8, gëtt d'Funktioun falsch zréck, well keng zwou Zuelen an der Array kënne bis zu 8 addéieren.
Beispill B
Awer wann et eng Array ass [1, 2, 4, 4] an de Wäert ass 8, da sollt d'Funktioun richteg zréckkommen well 4 + 4 = 8.
Léisung 1: Brute Kraaft
Zäitkomplexitéit: O(N²).
Raumkomplexitéit: O(1).
Déi offensichtlechst Bedeitung ass e Paar vu nestéierte Schleifen ze benotzen.
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;
};Dës Léisung ass net effizient well se all méiglech Zomm vun zwee Elementer am Array iwwerpréift an och all Pair vun Indizes zweemol vergläicht. (Zum Beispill, wann i = 1 an j = 2 ass eigentlech d'selwecht wéi am Verglach mat i = 2 an j = 1, mä an dëser Léisung probéieren mir béid Optiounen).
Well eis Léisung e Paar nestéiert fir Schleifen benotzt, ass et quadratesch mat O(N²) Zäitkomplexitéit.
Léisung 2: Binär Sich
Zäitkomplexitéit: O(Nlog(N)).
Raumkomplexitéit: O(1).
Well d'Arrays bestallt sinn, kënne mir no enger Léisung sichen mat der binärer Sich. Dëst ass den effizientesten Algorithmus fir bestallt Arrays. Binär Sich selwer huet eng Lafenzäit vun O(log(N)). Wéi och ëmmer, Dir musst nach ëmmer e For Loop benotzen fir all Element géint all aner Wäerter ze kontrolléieren.
Hei ass wéi eng Léisung kéint ausgesinn. Fir d'Saache kloer ze maachen, benotze mir eng separat Funktioun fir d'binär Sich ze kontrolléieren. An och d'Funktion removeIndex (), déi d'Versioun vum Array minus de gegebene Index zréckginn.
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;
};Den Algorithmus fänkt vum Index [0] un. Et erstellt dann eng Versioun vum Array ausser den éischten Index a benotzt binär Sich fir ze kucken ob ee vun de verbleiwen Wäerter an d'Array bäigefüügt ka ginn fir déi gewënscht Zomm ze produzéieren. Dës Aktioun gëtt eemol fir all Element an der Array gemaach.
De for Loop selwer wäert eng linear Zäitkomplexitéit vun O(N) hunn, awer bannent der for Loop maache mir eng binär Sich, déi eng Gesamtzäitkomplexitéit vun O(Nlog(N) gëtt). Dës Léisung ass besser wéi déi virdrun, awer et ass nach ëmmer Plaz fir Verbesserung.
Léisung 3: Linearzäit
Zäitkomplexitéit: O(N).
Raumkomplexitéit: O(1).
Elo wäerte mir de Problem léisen, drun erënneren datt d'Array zortéiert ass. D'Léisung ass zwou Zuelen ze huelen: eng am Ufank an eng um Enn. Wann d'Resultat vun der erfuerderter ënnerscheet, da ännert d'Start- an Ennpunkten.
Eventuell wäerte mir entweder de gewënschten Wäert begéinen a richteg zréckkommen, oder d'Start- an Ennpunkte konvergéieren a falen zréck.
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;
};Elo ass alles gutt, d'Léisung schéngt optimal ze sinn. Awer wien ka garantéieren datt d'Array bestallt gouf?
Wat dann?
Op den éischte Bléck hätte mir einfach d'Array als éischt bestallt an dann d'Léisung hei uewen benotzt. Awer wéi wäert dëst d'Ausféierungszäit beaflossen?
De beschten Algorithmus ass Quicksort mat Zäitkomplexitéit O (Nlog (N)). Wa mir et an eiser optimaler Léisung benotzen, ännert se seng Leeschtung vun O(N) op O(Nlog(N)). Ass et méiglech eng linear Léisung mat engem onorderten Array ze fannen?
4 Léisung
Zäitkomplexitéit: O(N).
Raumkomplexitéit: O(N).
Jo, et gëtt eng linear Léisung; fir dëst ze maachen, musse mir eng nei Array erstellen mat der Lëscht vun de Matcher déi mir sichen. Den Handel hei ass méi Erënnerungsverbrauch: et ass déi eenzeg Léisung am Pabeier mat Raumkomplexitéit méi grouss wéi O(1).
Wann den éischte Wäert vun enger bestëmmter Array 1 ass an de Sichwäert 8 ass, kënne mir de Wäert 7 an d'Array "Sichwäerter" addéieren.
Dann, wa mir all Element vun der Array veraarbecht, kënne mir d'Array vun "Sichwäerter" iwwerpréiwen a kucken ob ee vun hinnen gläich ass mat eisem Wäert. Wann jo, zréck wouer.
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;
};D'Basis vun der Léisung ass eng for-Loop, déi, wéi mir hei uewen gesinn, eng linear Zäitkomplexitéit vun O(N) huet.
Den zweeten iterativen Deel vun eiser Funktioun ass Array.prototype.include(), eng JavaScript-Methode déi richteg oder falsch zréckkënnt ofhängeg ob d'Array de gegebene Wäert enthält.
Fir erauszefannen d'Zäit Komplexitéit vun Array.prototype.includes (), kënne mir op der polyfill vun MDN (a geschriwwe JavaScript) kucken oder eng Method am Quellcode vun engem JavaScript-Moteur wéi Google V8 benotzen (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;
}
});
}Hei ass den iterativen Deel vun Array.prototype.include () d'While Loop am Schrëtt 7 deen (bal) d'ganz Längt vun der bestëmmter Array duerchkreest. Dëst bedeit datt seng Zäitkomplexitéit och linear ass. Gutt, well et ëmmer ee Schrëtt hannert eisem Haaptarray ass, ass d'Zäitkomplexitéit O (N + (N - 1)). Mat Big O Notation vereinfachen mir et op O(N) - well et N ass deen de gréissten Impakt huet wann d'Inputgréisst erhéicht gëtt.
Wat raimlech Komplexitéit ugeet, ass eng zousätzlech Array gebraucht, där hir Längt déi ursprénglech Array spigelt (minus een, jo, awer dat kann ignoréiert ginn), wat zu O(N) raimlech Komplexitéit resultéiert. Gutt, erhéicht Erënnerungsverbrauch garantéiert maximal Effizienz vum Algorithmus.
Ech hoffen Dir fannt den Artikel nëtzlech als Ergänzung zu Ärem Videointerview. Et weist datt en einfache Problem op verschidde Manéiere mat verschiddene Quantitéite vu Ressourcen geléist ka ginn (Zäit, Erënnerung).
Skillbox recommandéiert:
- Applizéiert online Course .
- Online Cours .
- Praktesch ee Joer Cours .
Source: will.com
