Xa ndandifunda ukusebenza kwee-algorithms, ndadibana nale nto . Ayinikeli nje umbono wendlela udliwano-ndlebe oluqhutywa ngayo kwiinkampani ezinkulu zetekhnoloji, kodwa ikuvumela ukuba uqonde ukuba iingxaki ze-algorithmic zisonjululwa njani ngokufanelekileyo.
Eli nqaku luhlobo lokukhapha ividiyo. Kuyo ndinikezela ngezimvo kuzo zonke izisombululo ezibonisiweyo, kunye nenguqulelo yam yesisombululo kwiJavaScript. Iinuances ze-algorithm nganye zikwaxoxwa ngazo.
Siyakhumbuza: kubo bonke abafundi be "Habr" - isaphulelo se-ruble ye-10 xa ubhalisa kuyo nayiphi na ikhosi ye-Skillbox usebenzisa ikhowudi yokuphromotha "Habr".
I-Skillbox iyacebisa: Ikhosi esebenzayo .
Џџ ѕЃ ° °
Sinikwa uluhlu olucwangcisiweyo kunye nexabiso elithile. Iyacelwa ke ukuba yenze umsebenzi obuyisela inyani okanye asiyonyani ngokuxhomekeke ekubeni naliphi na inani lamanani amabini kuluhlu lingalingana nexabiso elinikiweyo.
Ngamanye amazwi, ingaba zimbini ii-integers kuluhlu, x kunye no-y, ezithi xa zidibene zilingana nexabiso elikhankanyiweyo?
Umzekelo A
Ukuba sinikwe uluhlu [1, 2, 4, 9] kwaye ixabiso ngu-8, umsebenzi uya kubuya ubuxoki kuba akukho manani mabini kuluhlu anokudibanisa ukuya ku-8.
Umzekelo B
Kodwa ukuba luluhlu [1, 2, 4, 4] kwaye ixabiso ngu-8, umsebenzi kufuneka ubuyele inyaniso kuba 4 + 4 = 8.
Isisombululo 1: Amandla abhuqe
Ubunzima bexesha: O(N²).
Ukuntsokotha kwendawo: O(1).
Eyona ntsingiselo icacileyo kukusebenzisa iperi ye-loops enendlwane.
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;
};Esi sisombululo asisebenzi kuba sijonga yonke into enokubakho yezinto ezimbini kuluhlu kwaye ithelekisa zonke izibini zezalathisi kabini. (Umzekelo, xa i = 1 kunye j = 2 ngokwenene iyafana nokuthelekisa kunye i = 2 kunye j = 1, kodwa kwesi sisombululo sizama zombini iinketho).
Kuba isisombululo sethu sisebenzisa iperi yendlwane ye-loops, i-quadratic kunye ne-O(N²) ixesha elinzima.
Isisombululo 2: Ukukhangela kweBhinary
Ubunzima bexesha: O(Nlog(N)).
Ukuntsokotha kwendawo: O(1).
Ekubeni ii-arrays zicwangcisiwe, sinokukhangela isisombululo ngokusebenzisa ukukhangela kokubini. Le yeyona algorithm isebenzayo kuluhlu olucwangcisiweyo. Uphendlo lokubini lunexesha elisebenzayo le-O(log(N)). Nangona kunjalo, kusafuneka usebenzise i-loop ukujonga into nganye ngokuchasene nawo onke amanye amaxabiso.
Nantsi indlela isisombululo esinokubonakala ngayo. Ukwenza izinto zicace, sisebenzisa umsebenzi owahlukileyo ukulawula ukukhangela kokubini. Kwaye kwakhona susaIndex () umsebenzi, obuyisela uguqulelo loluhlu thabatha isalathiso esinikiweyo.
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 kwisalathiso [0]. Idala ke uguqulelo loluhlu ngaphandle kwesalathiso sokuqala kwaye isebenzisa uphendlo lokubini ukubona ukuba nawaphi na amaxabiso aseleyo anokufakwa kuluhlu ukuvelisa isixa esifunwayo. Esi senzo senziwa kube kanye kwinto nganye kuluhlu.
Ilophu ngokwayo izakuba nexesha elinzima lokuntsonkotha kwe O(N), kodwa ngaphakathi kwilophu senza uphendlo lokubini, olunika ixesha elipheleleyo lokuntsokotha kwe O(Nlog(N)). Esi sisombululo singcono kuneso sangaphambili, kodwa kusekho indawo yokuphucula.
Isisombululo 3: Ixesha lomgca
Ubunzima bexesha: O(N).
Ukuntsokotha kwendawo: O(1).
Ngoku siza kusombulula ingxaki, sikhumbula ukuba uluhlu luhlelwe. Isisombululo kukuthatha amanani amabini: elinye ekuqaleni kunye nelinye ekugqibeleni. Ukuba isiphumo sihluke kwinto efunekayo, ke utshintshe amanqaku okuqala kunye nokuphela.
Ekugqibeleni siya kudibana nexabiso elifunekayo kwaye sibuyele ngokwenyani, okanye iindawo zokuqala kunye nesiphelo ziya kudibana kwaye zibuye zibubuxoki.
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;
};
Ngoku yonke into ilungile, isisombululo sibonakala siphezulu. Kodwa ngubani onokuqinisekisa ukuba uluhlu lwayalelwa?
Kuthiweni ke ngoko?
Kuqala krwaqu, sinokuthi silandelele uluhlu kuqala kwaye emva koko sisebenzise isisombululo esingentla. Kodwa oku kuya kulichaphazela njani ixesha lokubulawa?
Eyona algorithm ilungileyo yohlobo olukhawulezayo kunye nobunzima bexesha O (Nlog (N)). Ukuba siyisebenzisa kwisisombululo sethu esisiso, siya kutshintsha ukusebenza kwayo ukusuka ku-O(N) ukuya kwi-O(Nlog(N)). Ngaba kunokwenzeka ukufumana isisombululo somgca kunye noluhlu olungacwangciswanga?
Isisombululo 4
Ubunzima bexesha: O(N).
Ukuntsokotha kwendawo: O(N).
Ewe, kukho isisombululo somgca; ukwenza oku, kufuneka senze uluhlu olutsha oluqulathe uluhlu lweematshisi esizikhangelayo. Ukurhweba apha kusetyenziso lwenkumbulo ngakumbi: sisisombululo kuphela ephepheni esinesithuba esinobunzima obukhulu kuno-O(1).
Ukuba ixabiso lokuqala loluhlu olunikiweyo ngu-1 kwaye ixabiso lokukhangela ngu-8, sinokudibanisa ixabiso lesi-7 "kumaxabiso okukhangela" uluhlu.
Emva koko, njengoko siqhuba into nganye yoluhlu, sinokujonga uluhlu "lwamaxabiso okukhangela" kwaye sibone ukuba enye yawo ilingana nexabiso lethu. Ukuba ewe, buyisela inyaniso.
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;
};Isiseko sesisombululo yi-loop, ethe, njengoko sibonile ngasentla, inobunzima bexesha le-O(N).
Inxalenye yesibini ephindaphindwayo yomsebenzi wethu yi Array.prototype.include(), indlela yeJavaScript ezakubuyisela inyaniso okanye ayiyonyani kuxhomekeke ekubeni uluhlu luqulathe ixabiso elinikiweyo.
Ukubona ubunzima bexesha le-Array.prototype.includes (), sinokujonga kwi-polyfill enikezwe yi-MDN (kwaye ibhalwe kwiJavaScript) okanye sisebenzise indlela kwikhowudi yomthombo wenjini yeJavaScript njengeGoogle 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;
}
});
}Apha indawo ephindaphindayo ye Array.prototype.include() lixa iluphu kwinyathelo lesi-7 eli (phantse) linqumla bonke ubude boluhlu olunikiweyo. Oku kuthetha ukuba ixesha layo elintsonkothileyo likwanomgca. Ewe, kuba ihlala iyinyathelo elinye emva koluhlu lwethu oluphambili, ubunzima bexesha ngu-O (N + (N - 1)). Sisebenzisa iBig O Notation, siyenza lula ukuya ku-O(N) - kuba yi-N enempembelelo enkulu xa unyusa ubungakanani begalelo.
Ngokuphathelele ukuntsokotha kwendawo, uluhlu olongezelelweyo luyafuneka olubude bubonisa uluhlu lwemvelaphi (thabatha enye, ewe, kodwa inokungahoywa), okukhokelela kubunzima besithuba se-O(N). Ewe, ukwanda kokusetyenziswa kwememori kuqinisekisa ukusebenza kakuhle kwe-algorithm.
Ndiyathemba ukuba uya kulifumana eli nqaku liluncedo njengesongezelelo kudliwanondlebe lwakho lwevidiyo. Ibonisa ukuba ingxaki elula ingasonjululwa ngeendlela ezininzi ezahlukeneyo ngezixa ezahlukeneyo zezibonelelo ezisetyenziswayo (ixesha, inkumbulo).
I-Skillbox iyacebisa:
- Isicelo sekhosi ye-intanethi .
- Ikhosi ekwi-Intanethi .
- Ikhosi yonyaka osebenzayo .
umthombo: www.habr.com