Kur unë isha duke studiuar performancën e algoritmeve, takova këtë . Ajo jo vetëm që jep një ide se si zhvillohen intervistat në kompanitë e mëdha teknologjike, por gjithashtu ndihmon për të kuptuar se si zgjidhen detyrat algoritmike, në mënyrën më efektive të mundshme.
Ky artikull është një lloj shoqërimi me videon. Në të jep komentet e mia për të gjitha zgjidhjet e paraqitura, si dhe versionin tim të zgjidhjes në JavaScript. Grishen gjithashtu nuancat e çdo algoritmi.
Kujtojmë: për të gjithë lexuesit e «Habra» — zbritje prej 10,000 rublesh për regjistrimin në çdo kurs Skillbox me kodin promovues «Habr».
Skillbox rekomandon: Kurs praktik .
Formulimi i detyrës
Na jepet një array të renditur dhe një vlerë të caktuar. Pastaj kërkohet të krijojmë një funksion që kthen true ose false, në varësi të faktit nëse shuma e dy numrave nga array është e barabartë me vlerën e dhënë.
Në terma të tjerë, a ka në array dy numra të plotë x dhe y që, kur janë të përmbledhur, japin vlerën e përmendur?
Shembulli A
Nëse na është dhënë array [1, 2, 4, 9] dhe vlera 8, funksioni do të kthejë false, sepse asnjëhetë dy numra nga array nuk mund të japin 8 në shuma.
Shembulli B
Por nëse ky është array [1, 2, 4, 4] dhe vlera 8, funksioni duhet të kthejë true, sepse 4 + 4 = 8.
Zgjidhja 1. Bruteforce
Kompleksiteti temporal: O(N²).
Kompleksiteti hapësinor: O(1).
Vlera më e dukshme është përdorimi i dy cikleve të ngulitur.
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;
};Këtë zgjidhje nuk mund ta quajmë efikase, pasi kontrollon çdo mundësi të shënëdhjes së dy elementeve në array dhe gjithashtu krahasohet çdo çift indekse dy herë. (Për shembull, kur i = 1 dhe j = 2, kjo në të vërtetë është e njëjta gjë si të krahasosh me i = 2 dhe j = 1, por në këtë zgjidhje provohet të dyja variantet).
Duke qenë se zgjidhja jonë përdor një çift ciklesh të ngulitur for, ajo është katrore me kompleksitetin temporal O (N²).
Zgjidhja 2. Kërkimi binar
Kompleksiteti temporal: O(Nlog(N)).
Kompleksiteti hapësinor: O(1).
Duke qenë se array-t janë të renditur, ne mund të kërkojmë zgjidhjen duke përdorur kërkimin binar. Ky është algoritmi më efikas për array të renditur. Kërkimi binar vetë ka një kohë ekzekutimi O (log (N)). Megjithatë, ndihmohet nga një cikël for për të kontrolluar çdo element për të gjitha vlerat e tjera.
Kjo është se si mund të duket zgjidhja. Për t'u siguruar që gjithçka është e qartë, ne përdorim një funksion të veçantë për të kontrolluar kërkimin binar. Po ashtu, një funksion removeIndex (), i cili kthen versionin e arrays pa indekson e caktuar.
const findSum = (arr, val) => {
for (let i = 0; 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]) {
start = pivot + 1;
};
pivot = Math.floor((start + end) / 2);
if (arr[pivot] === val) {
return true;
}
};
return false;
};Algoritmi fillon nga indeksi [0]. Më pas krijon një version të arrays pa indekson e parë dhe përdor kërkimin binar për të kontrolluar nëse mund të shtohet ndonjë nga vlerat e mbetura në array për të arritur shumën e dëshiruar. Ky veprim kryhet një herë për çdo element në array.
Vete cikli for do të ketë një kompleksitet temporal linear O (N), por brenda ciklit for ne kryejmë një kërkim binar, çka jep një kompleksitet të përgjithshëm temporal O (Nlog (N)). Kjo zgjidhje është më e mirë se e mëparshmja, por ende ka vend për përmirësim.
Zgjidhja 3. Koha lineare
Kompleksiteti temporal: O(N).
Kompleksiteti hapësinor: O(1).
Tani do të zgjidhim problemin, duke mbajtur mend se array është i renditur. Zgjidhja konsiston në marrjen e dy numrave: një në fillim dhe një në fund. Nëse rezultati ndryshon nga ajo që kërkohet, ne ndërron fillimin dhe pikën fundore.
Në fund, madje do të takojmë vlerën e dëshiruar dhe do të kthejmë true, ose pikat fillestare dhe fundore do të përputhen dhe do të kthehet false.
const findSum = (arr, val) => {
let start = 0;
let end = arr.length - 1;
while (start val) {
end -= 1;
} else if (sum < val) {
start += 1;
} else {
return true;
};
};
return false;
};Tani gjithçka është në rregull, zgjidhja duket se është optimale. Por kush garanton që array ishte i renditur?
Çfarë bëjmë atëherë?
Në shikim të parë, mund të rendisim fillimisht array dhe pastaj të përdorim zgjidhjen e sipërme. Por si do të ndikon kjo në kohën e ekzekutimit?
Algoritmi më i mirë është renditja e shpejtë me kompleksitet temporal O (Nlog (N)). Nëse e përdorim atë në zgjidhjen tonë optimale, ajo do të ndryshojë performancën e saj nga O (N) në O (Nlog (N)). A mund të gjejmë një zgjidhje lineare me një array të pa renditur?
Zgjidhja 4
Kompleksiteti temporal: O(N).
Kompleksiteti hapësinor: O(N).
Po, po ato, një zgjidhje lineare ekziston; për ta arritur këtë, duhet të krijoni një array të ri që përmban listën e përputhjeve që po kërkojmë. Kompromisi këtu është përdorimi më aktiv i memorjes: kjo është zgjidhja e vetme në artikull me kompleksitet hapësinor që tejkalon O (1).
Nëse vlera e parë e këtij array është 1, dhe vlera e kërkuar është 8, mund të shtojmë vlerën 7 në array-n 'vlerave të kërkimit'.
Pas kësaj, duke përpunuar çdo element të array-it, mund të kontrollojmë array-n 'vlerave të kërkimit' dhe të shohim nëse ndonjëra nga ato është e barabartë me vlerën tonë. Nëse po, kthejmë true.
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;
};Baze e zgjidhjes është cikli for, i cili, siç e pamë më sipër, ka një kompleksitet koresh O (N).
Pjesa e dytë iteruese e funksionit tonë është Array.prototype.include (), një metodë JavaScript që do të kthejë true ose false në varësi të faktit nëse array përmban një vlerë të caktuar.
Për të zbuluar kompleksitetin temporal të Array.prototype.includes (), mund të shqyrtojmë polyfill-in e ofruar nga MDN (dhe shkruar në JavaScript) ose të përdorim metodën në kodin burimor të motorit JavaScript, si 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;
}
});
}Këtu, pjesa iteruese e Array.prototype.include () është një cikël while në hapin 7, i cili (gati) kalon të gjithë gjatësinë e këtij array. Kjo do të thotë se kompleksiteti i saj temporal është gjithashtu linear. Dhe meqenëse ajo gjithmonë është një hap pas array-it tonë kryesor, atëherë kompleksiteti temporal është O (N + (N — 1)). Duke përdorur Big O Notation, e thjeshtojmë atë në O (N) — sepse N ka ndikimin më të madh kur rritet madhësia e inputit.
Sa i përket kompleksitetit hapësinor, nevojitet një array shtesë, gjatësia e të cilit e pasqyron array-n origjinal (minus një, po, por kjo mund të injorohet), që çon në një kompleksitet hapësinor O (N). Dhe përdorimi i shtuar i memorjes siguron efikasitetin maksimal të algoritmit.
Shpresoj që ky artikull të jetë i dobishëm për ju si një shtesë ndaj video-intervistës. Ai tregon se një detyrë e thjeshtë mund të zgjidhet në disa mënyra të ndryshme me një sasi të ndryshme të burimeve të përdorura (kohë, memorie).
Skillbox rekomandon:
- Kurs online aplikativ .
- Kurs online .
- Kurs praktik njëvjeçar .
Burimi: habr.com
