Algoritmoen errendimendua aztertzen ari nintzela, honekin egin nuen topo . Teknologia korporazio handietan elkarrizketak nola egiten diren jakiteko ideia bat emateaz gain, arazo algoritmikoak ahalik eta modu eraginkorrenean konpontzen diren ulertzeko aukera ematen du.
Artikulu hau bideoaren osagarri moduko bat da. Bertan erakutsitako soluzio guztiei buruzko iruzkinak ematen ditut, baita JavaScript-en nire soluzioaren bertsio propioa ere. Algoritmo bakoitzaren Γ±abardurak ere eztabaidatzen dira.
Gogoratzen dugu: "Habr" irakurle guztientzat - 10 errubloko deskontua "Habr" promozio-kodea erabiliz Skillbox-eko edozein ikastarotan izena ematean.
Skillbox-ek gomendatzen du: Ikastaro praktikoa .
Arazoaren formulazioa
Array ordenatu bat eta balio zehatz bat ematen zaigu. Ondoren, egia ala gezurra itzultzen duen funtzio bat sortzea eskatzen da, matrizeko edozein bi zenbakiren batura balio jakin baten berdina izan daitekeenaren arabera.
Beste era batera esanda, ba al daude matrizean x eta y bi zenbaki osoak batuta zehaztutako balioarekin berdintzen dutenak?
A adibidea
[1, 2, 4, 9] matrize bat ematen badigute eta balioa 8 bada, funtzioak faltsua itzuliko du, matrizeko bi zenbaki ezin direlako 8 batu.
B adibidea
Baina [1, 2, 4, 4] array bat bada eta balioa 8 bada, funtzioak egia itzuli beharko luke 4 + 4 = 8 delako.
1. irtenbidea: indar gordina
Denboraren konplexutasuna: O(NΒ²).
Espazioaren konplexutasuna: O(1).
Esanahirik nabarmenena habiaraturiko begizta pare bat erabiltzea da.
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;
};Soluzio hau ez da eraginkorra, matrizeko bi elementuren batura posible guztiak egiaztatzen dituelako eta indize-pare bakoitza bi aldiz alderatzen duelako. (Adibidez, i = 1 eta j = 2 i = 2 eta j = 1-ekin alderatzea berdina denean, baina soluzio honetan bi aukerak probatzen ditugu).
Gure soluzioak for habiaraturiko begizta pare bat erabiltzen dituenez, koadratikoa da O(NΒ²) denbora-konplexutasunarekin.
2. irtenbidea: Bilaketa bitarra
Denboraren konplexutasuna: O(Nlog(N)).
Espazioaren konplexutasuna: O(1).
Arrayak ordenatuta daudenez, bilaketa bitarra erabiliz irtenbide bat bilatu dezakegu. Hau da array ordenatuetarako algoritmorik eraginkorrena. Bilaketa bitarrak berak O(log(N)-ko denbora du. Hala ere, oraindik for begizta erabili behar duzu elementu bakoitza beste balio guztiekin egiaztatzeko.
Hona hemen irtenbide bat nolakoa izan daitekeen. Gauzak argi uzteko, funtzio bereizi bat erabiltzen dugu bilaketa bitarra kontrolatzeko. Eta baita removeIndex() funtzioa, zeinak matrizearen bertsioa itzultzen du emandako indizea kenduta.
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;
};Algoritmoa [0] indizetik abiatzen da. Ondoren, matrizearen bertsio bat sortzen du lehen indizea kenduta eta bilaketa bitarra erabiltzen du gainerako balioetakoren bat gehitu daitekeen matrizean nahi den batura sortzeko. Ekintza hau behin egiten da arrayko elementu bakoitzeko.
For begiztak berak O(N) denboraren konplexutasun lineala izango du, baina for begizta barruan bilaketa bitarra egiten dugu, eta horrek O (Nlog(N)) denboraren konplexutasun orokorra ematen du. Irtenbide hau aurrekoa baino hobea da, baina oraindik badago zer hobetu.
3. soluzioa: denbora lineala
Denboraren konplexutasuna: O(N).
Espazioaren konplexutasuna: O(1).
Orain arazoa konponduko dugu, array ordenatuta dagoela gogoratuz. Irtenbidea bi zenbaki hartzea da: bat hasieran eta bestea amaieran. Emaitza behar denetik desberdina bada, aldatu hasierako eta amaierako puntuak.
Azkenean, nahi dugun balioa topatuko dugu eta egia itzuliko dugu, edo hasierako eta amaierako puntuak bat egingo dute eta faltsua itzuliko da.
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;
};
Orain dena ondo dago, badirudi irtenbidea optimoa dela. Baina nork bermatu dezake array agindua izan zela?
Zer orduan?
Lehen begiratuan, matrizea ordenatu eta gero goiko soluzioa erabili genezake. Baina nola eragingo du horrek exekuzio denboran?
Algoritmo onena denboraren konplexutasuna O (Nlog (N)) da. Gure soluzio optimoan erabiltzen badugu, bere errendimendua O(N)-tik O(Nlog(N)-ra aldatuko du). Posible al da ordenatu gabeko array batekin soluzio lineal bat aurkitzea?
4. irtenbidea
Denboraren konplexutasuna: O(N).
Espazioaren konplexutasuna: O(N).
Bai, irtenbide lineal bat dago; horretarako, matrize berri bat sortu behar dugu bilatzen ari garen partiden zerrendarekin. Konpromisoa hemen memoria gehiago erabiltzea da: O(1) baino espazio konplexutasun handiagoa duen paperean soluzio bakarra da.
Emandako matrize baten lehen balioa 1 bada eta bilaketa-balioa 8 bada, 7 balioa gehi diezaiokegu "bilaketa-balioak" arrayari.
Ondoren, matrizeko elementu bakoitza prozesatzen dugunean, "bilaketa-balioen" array-a egiaztatu ahal izango dugu eta horietako bat gure balioaren berdina den ikusi ahal izango dugu. Baiezkoa bada, itzuli egia.
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;
};Soluzioaren oinarria for begizta da, eta, arestian ikusi dugun bezala, O(N) denbora-konplexutasun lineala du.
Gure funtzioaren bigarren zati errepikakorra Array.prototype.include() da, egia ala gezurra itzuliko duen JavaScript metodoa, matrizeak emandako balioa duen ala ez.
Array.prototype.includes(ren) denbora-konplexutasuna jakiteko, MDN-k (eta JavaScript-en idatzita) emandako polyfill-a ikus dezakegu edo Google V8 (C++) bezalako JavaScript motor baten iturburu-kodean metodo bat erabil dezakegu.
// 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;
}
});
}Hemen Array.prototype.include()-ren zati iteratiboa 7. urratseko while begizta da (ia) emandako matrizearen luzera osoa zeharkatzen duena. Horrek esan nahi du denboraren konplexutasuna ere lineala dela. Beno, gure array nagusiaren atzetik beti dagoenez, denboraren konplexutasuna O (N + (N - 1) da). Big O notazioa erabiliz, sinplifikatu dugu O(N) - N delako sarreraren tamaina handitzean eragin handiena duena.
Konplexutasun espazialari dagokionez, matrize gehigarri bat behar da, zeinaren luzerak jatorrizko array ispilu duen (bat ken, bai, baina hori alde batera utzi daiteke), eta O(N) konplexutasun espaziala izango da. Beno, memoriaren erabilera handitzeak algoritmoaren eraginkortasun handiena bermatzen du.
Artikulua zure bideo elkarrizketaren osagarri gisa erabilgarria izatea espero dut. Erabiltzen diren baliabide kopuru ezberdinekin (denbora, memoria) arazo sinple bat hainbat modutan ebatzi daitekeela erakusten du.
Skillbox-ek gomendatzen du:
- Lineako ikastaroa aplikatua .
- Lineako ikastaroa .
- Ikastaro praktikoa .
Iturria: www.habr.com