Ngenkathi ngifunda ukusebenza kwama-algorithms, ngathola lokhu . Ayinikezi nje umbono wokuthi izingxoxo zenziwa kanjani ezinkampanini ezinkulu zobuchwepheshe, kodwa futhi ikuvumela ukuthi uqonde ukuthi izinkinga ze-algorithmic zixazululwa kanjani ngempumelelo ngangokunokwenzeka.
Lesi sihloko siwuhlobo lokuhambisana nevidiyo. Kuyo nginikeza ukuphawula kuzo zonke izixazululo ezibonisiwe, kanye nenguqulo yami yesixazululo ku-JavaScript. Ama-nuances we-algorithm ngayinye nawo axoxwa ngawo.
Siyakukhumbuza: kubo bonke abafundi be-"Habr" - isaphulelo sama-ruble angu-10 lapho ubhalisa kunoma yisiphi isifundo se-Skillbox usebenzisa ikhodi yephromoshini ethi "Habr".
I-Skillbox iyancoma: Isifundo esiwusizo .
Ukwakheka kwenkinga
Sinikezwa amalungu afanayo a-odiwe kanye nenani elithile. Kube sekucelwa ukuthi udale umsebenzi obuyisela iqiniso noma amanga kuye ngokuthi isamba sanoma yiziphi izinombolo ezimbili ohlwini singalingana nenani elinikeziwe.
Ngamanye amazwi, ingabe akhona izinombolo ezimbili eziphelele ohlwini, x kanye no-y, okuthi uma zihlanganiswe ndawonye zilingane nenani elishiwo?
Isibonelo A
Uma sinikezwa amalungu afanayo [1, 2, 4, 9] futhi inani lingu-8, umsebenzi uzobuya ungamanga ngoba azikho izinombolo ezimbili ohlwini ezingahlanganisa kufika ku-8.
Isibonelo B
Kodwa uma kuwuhlelo [1, 2, 4, 4] futhi inani lingu-8, umsebenzi kufanele ubuyele kuyiqiniso ngoba 4 + 4 = 8.
Isixazululo 1: Amandla aqinile
Isikhathi esiyinkimbinkimbi: O(N²).
Ubunkimbinkimbi besikhala: O(1).
Incazelo esobala kakhulu ukusebenzisa amalophu afakwe isidleke.
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;
};Lesi sixazululo asisebenzi kahle ngoba sihlola yonke isamba esingaba khona sezinto ezimbili kuhlelo futhi siqhathanisa yonke ipheya yezinkomba kabili. (Isibonelo, uma i = 1 kanye no-j = 2 empeleni kufana nokuqhathanisa no-i = 2 no-j = 1, kodwa kulesi sixazululo sizama kokubili izinketho).
Ngoba isisombululo sethu sisebenzisa ipheya yezidleke zamalophu, siyi-quadratic ne-O(N²) yesikhathi esiyinkimbinkimbi.
Isixazululo 2: Ukusesha Kanambambili
Isikhathi esiyinkimbinkimbi: O(Nlog(N)).
Ubunkimbinkimbi besikhala: O(1).
Njengoba ama-array ehleliwe, singakwazi ukucinga isixazululo sisebenzisa ukusesha kanambambili. Lena i-algorithm esebenza kahle kakhulu kumalungu afanayo a-odiwe. Ukusesha kanambambili ngokwako kunesikhathi sokusebenza sika-O(log(N)). Nokho, usadinga ukusebenzisa iluphu ukuze uhlole i-elementi ngayinye ngokumelene nawo wonke amanye amanani.
Nakhu ukuthi isixazululo singabukeka kanjani. Ukwenza izinto zicace, sisebenzisa umsebenzi ohlukile ukulawula ukusesha kanambambili. Futhi nomsebenzi we-removeIndex(), obuyisela inguqulo yamalungu afanayo khipha inkomba enikeziwe.
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;
};I-algorithm iqala kunkomba [0]. Ibese idala inguqulo yamalungu afanayo ngaphandle kwenkomba yokuqala futhi isebenzisa ukusesha kanambambili ukuze ibone ukuthi noma imaphi amanani asele angengezwa kumalungu afanayo ukuze kukhiqizwe isamba esifiswayo. Lesi senzo senziwa kanye engxenyeni ngayinye ohlwini.
I-loop ngokwayo izoba nobunkimbinkimbi besikhathi somugqa ongu-O(N), kodwa ngaphakathi kwe-loop senza ukusesha okubili, okunikeza isikhathi sonke esiyinkimbinkimbi se-O(Nlog(N)). Lesi sixazululo singcono kunesangaphambilini, kodwa sisekhona indawo yokuthuthukiswa.
Isixazululo 3: Isikhathi somugqa
Isikhathi esiyinkimbinkimbi: O(N).
Ubunkimbinkimbi besikhala: O(1).
Manje sizoxazulula inkinga, sikhumbula ukuthi uhlu luhlungiwe. Isixazululo ukuthatha izinombolo ezimbili: eyodwa ekuqaleni nenye ekugcineni. Uma umphumela uhlukile kodingekayo, shintsha amaphuzu okuqala nawokugcina.
Ekugcineni sizohlangabezana nevelu esiyifunayo bese sibuyela eqinisweni, noma amaphuzu okuqala nawokugcina azohlangana futhi abuye angamanga.
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;
};
Manje konke kuhamba kahle, ikhambi libonakala lilungile. Kodwa ubani ongaqinisekisa ukuthi uhlu luyaliwe?
Kuthiwani-ke?
Uma uthi nhlá, besingahle si-ode amalungu afanayo kuqala bese sisebenzisa isisombululo esingenhla. Kodwa lokhu kuzosithinta kanjani isikhathi sokubulawa?
I-algorithm engcono kakhulu i-quicksort enobunzima besikhathi O (Nlog (N)). Uma siyisebenzisa kusixazululo sethu esilungile, izoshintsha ukusebenza kwayo isuke ku-O(N) iye ku-O(Nlog(N)). Ingabe kungenzeka ukuthola isixazululo esiwumugqa ngohlelo olunga-odelwe?
Isixazululo 4
Isikhathi esiyinkimbinkimbi: O(N).
Ubunkimbinkimbi besikhala: O(N).
Yebo, sikhona isisombululo somugqa; ukwenza lokhu, sidinga ukwakha uhlu olusha oluqukethe uhlu lwamameshi esiwafunayo. Ukuhwebelana lapha ukusetshenziswa kwenkumbulo okwengeziwe: ukuphela kwesixazululo ephepheni esinobunzima besikhala obukhulu kuno-O(1).
Uma inani lokuqala lelungu elifanayo elinikeziwe lingu-1 futhi inani lokubheka lingu-8, singakwazi ukwengeza inani elingu-7 "kumanani okubheka".
Bese, njengoba sicubungula i-elementi ngayinye yamalungu afanayo, singabheka uhlu "lwamanani okusesha" futhi sibone ukuthi ingabe eyodwa yawo ilingana nevelu yethu. Uma kunjalo, buyisela iqiniso.
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;
};Isisekelo sesixazululo i-loop, njengoba sibonile ngenhla, inobunzima besikhathi obuyi-O(N).
Ingxenye yesibili ephindaphindayo yomsebenzi wethu ithi Array.prototype.include(), indlela ye-JavaScript ezobuyisela iqiniso noma amanga kuye ngokuthi amalungu afanayo aqukethe inani elinikeziwe.
Ukuze sithole ubunkimbinkimbi besikhathi be-Array.prototype.includes(), singabheka i-polyfill ehlinzekwa yi-MDN (futhi ebhalwe nge-JavaScript) noma sisebenzise indlela ekukhodi yomthombo wenjini ye-JavaScript efana ne-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;
}
});
}Lapha ingxenye ephindaphindayo ye-Array.prototype.include() iyiluphu yesikhathi esinyathelweni sesi-7 lapho (cishe) inqamula bonke ubude bamalungu afanayo anikeziwe. Lokhu kusho ukuthi inkimbinkimbi yesikhathi sayo nayo iqondile. Nokho, njengoba kuhlale kuyisinyathelo esisodwa ngemuva kohlu lwethu oluyinhloko, ubunkimbinkimbi besikhathi bungu-O (N + (N - 1)). Sisebenzisa i-Big O Notation, siyenza ibe lula ibe ngu-O(N) - ngoba ingu-N enomthelela omkhulu kakhulu lapho ukhuphula usayizi wokufaka.
Ngokuphathelene nobunkimbinkimbi bendawo, kudingeka amalungu afanayo okwengeziwe ubude bawo bufanekisela uhlu lwangempela (susa okukodwa, yebo, kodwa lokho kunganakwa), okuholela ku-O(N) inkimbinkimbi yendawo. Nokho, ukwanda kokusetshenziswa kwenkumbulo kuqinisekisa ukusebenza kahle okuphezulu kwe-algorithm.
Ngithemba ukuthi uthola isihloko siwusizo njengesithasiselo kungxoxo yakho yevidiyo. Kubonisa ukuthi inkinga elula ingaxazululwa ngezindlela eziningana ezahlukene ngamanani ahlukene wezinsiza ezisetshenziswa (isikhathi, inkumbulo).
I-Skillbox iyancoma:
- Kusetshenziswe izifundo ze-inthanethi .
- Inkambo eku-inthanethi .
- Isifundo sonyaka esisebenzayo .
Source: www.habr.com