Dema ku min performansa algorîtmayan dixwend, ez rastî vê yekê hatim . Ew ne tenê ramanek dide ka hevpeyivîn çawa li pargîdaniyên teknolojiya mezin têne kirin, lê di heman demê de dihêle hûn fêm bikin ka pirsgirêkên algorîtmîkî çawa bi qasî ku gengaz têne çareser kirin.
Ev gotar celebek pêvekek vîdyoyê ye. Di wê de ez şîroveyan li ser hemî çareseriyên ku têne xuyang kirin, plus guhertoya xweya çareseriyê di JavaScript de pêşkêşî dikim. Nîşaneyên her algorîtmayê jî têne nîqaş kirin.
Em bînin bîra xwe: ji bo hemî xwendevanên "Habr" - dema ku hûn beşdarî qursek Skillbox-ê bi karanîna koda danasînê ya "Habr" têne qeyd kirin 10 rubleyan dakêşin.
Skillbox pêşniyar dike: Kursa pratîk .
Formulkirina pirsgirêkê
Ji me re rêzek rêzkirî û nirxek taybetî tê dayîn. Dûv re tê xwestin ku fonksiyonek biafirîne ku rast an xelet vedigere li gorî ka berhevoka her du hejmarên di rêzê de dikare nirxek diyarkirî wekhev be.
Bi gotineke din, gelo di rêzê de du hejmar hene, x û y, ku gava li hev werin zêdekirin nirxa diyarkirî wekhev e?
Mînak A
Ger rêzek [1, 2, 4, 9] ji me re were dayîn û nirx 8 be, fonksiyon dê xelet vegere ji ber ku di rêzê de du hejmar nikarin 8-ê lê zêde bikin.
Mînak B
Lê heke ew rêzek [1, 2, 4, 4] be û nirx 8 be, divê fonksiyon rast vegere ji ber ku 4 + 4 = 8.
Çareserî 1: Hêza hovane
Tevliheviya demê: O(N²).
Tevliheviya cihan: O(1).
Wateya herî eşkere ev e ku meriv cotek lûpên hêlîn bikar bîne.
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;
};Ev çareserî ne bikêr e ji ber ku ew her berhevoka gengaz a du hêmanan di rêzê de kontrol dike û her cotek nîşanan jî du caran dide ber hev. (Mînakî, gava i = 1 û j = 2 bi rastî heman e ku bi i = 2 û j = 1 re berhev bikin, lê di vê çareseriyê de em herdu vebijarkan diceribînin).
Ji ber ku çareseriya me cotek hêlînê ji bo lûpkan bikar tîne, ew bi tevliheviya dema O(N²) çargoşe ye.
Çareserî 2: Lêgerîna Binary
Tevliheviya demê: O(Nlog(N)).
Tevliheviya cîhê: O(1).
Ji ber ku rêzik têne rêz kirin, em dikarin bi karanîna lêgerîna binary li çareseriyê bigerin. Ev algorîtmaya herî bikêrhatî ye ji bo rêzikên rêzkirî. Lêgerîna binary bixwe demek xebitandinê O(log(N)) heye. Lêbelê, hûn hîn jî hewce ne ku lûpek for-ê bikar bînin da ku her elementek li hember hemî nirxên din kontrol bikin.
Li vir dibe ku çareseriyek çawa xuya bike. Ji bo ku tiştan zelal bikin, em fonksiyonek cihêreng bikar tînin da ku lêgerîna binary kontrol bikin. Û di heman demê de fonksiyona removeIndex() jî, ku guhertoya rêzê ji xeynî indexa hatî dayîn vedigerîne.
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;
};Algorîtma ji index [0] dest pê dike. Dûv re ew guhertoyek rêzê diafirîne ku pêveka yekem jê derdixe û lêgerîna binary bikar tîne da ku bibîne ka yek ji nirxên mayî dikare li rêzê were zêdekirin da ku berhevoka xwestî hilberîne. Ev çalakî ji bo her hêmanek di rêzê de carekê tê kirin.
Xala for bixwe dê xwedan tevliheviyek dema xêzkirî ya O(N) be, lê di hundurê çerxa for de em lêgerînek binar pêk tînin, ku tevliheviyek demkî ya giştî ya O(Nlog(N)) dide. Ev çareserî ji ya berê çêtir e, lê hîn jî cîh ji bo pêşkeftinê heye.
Çareserî 3: Dema xêzikî
Tevliheviya demê: O(N).
Tevliheviya cihan: O(1).
Naha em ê pirsgirêkê çareser bikin, ji bîr mekin ku array rêzkirî ye. Çareserî ev e ku meriv du hejmaran bigire: yek li destpêkê û yek jî li dawiyê. Ger encam ji ya pêwîst cuda ye, wê hingê xalên destpêk û dawiyê biguherînin.
Di dawiyê de em ê an bi nirxa xwestinê re rûbirû bibin û rast vegerînin, an jî xalên destpêk û dawiyê dê li hev bicivin û xelet vegerin.
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;
};
Niha her tişt baş e, çareserî çêtirîn xuya dike. Lê kî dikare garantî bike ku array hatî ferman kirin?
Wê demê çi?
Di nihêrîna pêşîn de, me dikaribû pêşî rêzê bi tenê ferman bikira û dûv re çareseriya li jor bikar bînin. Lê ev ê çawa bandorê li dema darvekirinê bike?
Algorîtmaya çêtirîn bi tevliheviya demê O ye (Nlog (N)). Ger em wê di çareseriya xweya çêtirîn de bikar bînin, ew ê performansa xwe ji O(N) biguhezîne O(Nlog(N)). Ma gengaz e ku meriv çareseriyek xêzek bi rêzek nerêkûpêk bibîne?
Çareserî 4
Tevliheviya demê: O(N).
Tevliheviya cih: O(N).
Erê, çareseriyek xêzikî heye; ji bo vê yekê, em hewce ne ku rêzek nû ya ku tê de navnîşa maçên ku em lê digerin biafirînin. Bazirganiya li vir bêtir karanîna bîranînê ye: ew di kaxezê de çareseriya yekane ye ku tevliheviya cîhê ji O(1) mezintir e.
Ger nirxa yekem a rêzek diyar 1 be û nirxa lêgerînê 8 be, em dikarin nirxa 7 li rêzika "nirxên lêgerînê" zêde bikin.
Dûv re, dema ku em her hêmanek rêzê pêvajo dikin, em dikarin rêzika "nirxên lêgerînê" kontrol bikin û bibînin ka yek ji wan bi nirxa me re wekhev e. Ger erê, rast vegere.
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;
};Bingeha çareseriyê pêlekek for e, ku, wekî me li jor jî dît, xwedan tevliheviya dema xêz a O(N) ye.
Duyemîn beşa dubare ya fonksiyona me Array.prototype.include() e, rêbazek JavaScriptê ye ku dê rast an xelet vegere li gorî ka array nirxa diyarkirî dihewîne.
Ji bo ku em tevliheviya demê ya Array.prototype.includes() nas bikin, em dikarin li polyfillê ku ji hêla MDN ve hatî peyda kirin (û bi JavaScript hatî nivîsandin) binihêrin an jî di koda çavkaniyê ya motorek JavaScriptê de wekî Google V8 (C++) rêbazek bikar bînin.
// 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;
}
});
}Li vir beşa dubarekirî ya Array.prototype.include() di gava 7-an de çerxa while ye ku (hema bêje) dirêjahiya rêza diyarkirî diherike. Ev tê wê wateyê ku tevliheviya dema wê jî xêz e. Welê, ji ber ku ew her gav yek gav li paş rêzika meya sereke ye, tevliheviya demê O ye (N + (N - 1)). Bi karanîna Big O Notation, em wê bi O(N) re hêsan dikin - ji ber ku ew N e ku dema ku mezinahiya têketinê zêde dike bandora herî mezin heye.
Di derbarê tevliheviya cîhê de, rêzek pêvek hewce ye ku dirêjahiya wê rêzika orîjînal neynikê dike (kêm yek, erê, lê ew dikare were paşguh kirin), ku di encamê de tevliheviya cîhê O(N) çêdibe. Welê, zêdebûna karanîna bîranînê karûbarê herî zêde ya algorîtmê peyda dike.
Ez hêvî dikim ku hûn gotarê wekî pêvekek ji hevpeyvîna vîdyoya xwe re kêrhatî bibînin. Ew destnîşan dike ku pirsgirêkek hêsan dikare bi çend awayên cûda bi çavkaniyên cûda yên ku têne bikar anîn (dem, bîranîn) çareser bibe.
Skillbox pêşniyar dike:
- Kursa serhêl sepandin .
- Kursa serhêl .
- Kursa sala pratîk .
Source: www.habr.com