I koʻu aʻo ʻana i ka hana o nā algorithms, ʻike wau i kēia . ʻAʻole ia e hāʻawi wale i kahi manaʻo pehea e mālama ʻia ai nā nīnauele ma nā ʻoihana ʻenehana nui, akā hiki iā ʻoe ke hoʻomaopopo pehea e hoʻoponopono ʻia ai nā pilikia algorithmic e like me ka hiki.
He ʻano hoʻokani pila kēia ʻatikala i ke wikiō. Hāʻawi wau i nā manaʻo i nā hopena āpau i hōʻike ʻia, me kaʻu mana ponoʻī o ka hopena ma JavaScript. Kūkākūkā pū ʻia nā nuances o kēlā me kēia algorithm.
Hoʻomaopopo mākou iā ʻoe: no ka poʻe heluhelu a pau o "Habr" - kahi ho'ēmi o 10 rubles i ka wā e kākau inoa ai i kekahi papa Skillbox e hoʻohana ana i ka code promotional "Habr".
Manaʻo ʻo Skillbox: Papa hana .
Ka hoʻokumu ʻana i ka pilikia
Hāʻawi ʻia mākou i kahi papa kuhikuhi a me kahi waiwai kikoʻī. A laila, noi ʻia e hana i kahi hana e hoʻihoʻi i ka ʻoiaʻiʻo a i ʻole ka wahaheʻe e pili ana i ka like ʻana o ka huina o nā helu ʻelua i loko o ka laha me kahi waiwai i hāʻawi ʻia.
Ma nā huaʻōlelo ʻē aʻe, ʻelua mau helu helu i loko o ka laʻana, x a me y, i ka wā i hui pū ʻia e like me ka waiwai i ʻōlelo ʻia?
Laʻana A
Inā hāʻawi ʻia mākou i kahi laha [1, 2, 4, 9] a ʻo ka waiwai he 8, e hoʻihoʻi hewa ka hana no ka mea ʻaʻole hiki ke hoʻohui ʻia nā helu ʻelua i ka 8.
Laʻana B
Akā inā he laha [1, 2, 4, 4] a ʻo ka waiwai he 8, pono e hoʻi i ka ʻoiaʻiʻo no ka mea 4 + 4 = 8.
Pane 1: Ka ikaika ʻino
Paʻakikī o ka manawa: O(N²).
Paʻakikī lewa: O(1).
ʻO ka manaʻo maopopo loa ʻo ia ka hoʻohana ʻana i nā puka lousted.
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;
};ʻAʻole maikaʻi kēia hoʻonā no ka mea nānā ʻo ia i kēlā me kēia huina hiki o ʻelua mau mea i loko o ka laha a hoʻohālikelike i kēlā me kēia pālua o nā helu ʻelua. (No ka laʻana, inā i = 1 a me j = 2 ua like maoli me ka hoʻohālikelike ʻana me i = 2 a me j = 1, akā ma kēia hoʻonā e hoʻāʻo mākou i nā koho ʻelua).
No ka mea, hoʻohana kā mākou hoʻonā i ʻelua pūnana no nā puka lou, he quadratic me ka paʻakikī o ka manawa O(N²).
Helu 2: Huli Binary
Paʻakikī o ka manawa: O(Nlog(N)).
Paʻakikī lewa: O(1).
No ka mea ua kauoha ʻia nā arrays, hiki iā mākou ke ʻimi i kahi hopena me ka hoʻohana ʻana i ka huli binary. ʻO kēia ka algorithm maikaʻi loa no nā papa kuhikuhi. Loaʻa i ka ʻimi binary iho ka manawa holo o O(log(N)). Eia nō naʻe, pono ʻoe e hoʻohana i ka loop no ka nānā ʻana i kēlā me kēia mea i nā waiwai ʻē aʻe.
Eia ke ʻano o ka hopena. No ka hoʻomaʻamaʻa ʻana, hoʻohana mākou i kahi hana kaʻawale e hoʻomalu i ka ʻimi binary. A me ka hana removeIndex (), ka mea e hoʻihoʻi i ka mana o ka array e hoʻemi i ka ʻōlelo kuhikuhi i hāʻawi ʻia.
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;
};Hoʻomaka ka algorithm mai ka index [0]. A laila hana ia i kahi mana o ka laha me ka ʻole o ka papa kuhikuhi mua a hoʻohana i ka ʻimi binary e ʻike inā hiki ke hoʻohui ʻia kekahi o nā waiwai i koe i ka array e hana i ka huina i makemake ʻia. Hana ʻia kēia hana i hoʻokahi manawa no kēlā me kēia mea i loko o ka array.
E loaʻa i ka loop loop kahi paʻakikī o ka manawa laina o O (N), akā i loko o ka loop loop hana mākou i kahi hulina binary, e hāʻawi ana i ka paʻakikī o ka manawa o O (Nlog (N)). ʻOi aku ka maikaʻi o kēia hoʻonā ma mua o ka mea ma mua, akā aia kahi wahi no ka hoʻomaikaʻi ʻana.
Pane 3: Ka manawa laina
Paʻakikī o ka manawa: O(N).
Paʻakikī lewa: O(1).
I kēia manawa e hoʻoponopono mākou i ka pilikia, me ka hoʻomanaʻo ʻana ua hoʻonohonoho ʻia ka array. ʻO ka hopena e lawe i ʻelua helu: hoʻokahi ma ka hoʻomaka a hoʻokahi ma ka hopena. Inā ʻokoʻa ka hopena mai ka mea i koi ʻia, a laila e hoʻololi i nā helu hoʻomaka a me ka hopena.
I ka hopena, e ʻike mākou i ka waiwai i makemake ʻia a hoʻi i ka ʻoiaʻiʻo, a i ʻole e hui pū nā helu hoʻomaka a me nā hopena a hoʻi hewa.
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;
};
I kēia manawa ua maikaʻi nā mea a pau, ʻoi aku ka maikaʻi o ka hopena. Akā ʻo wai ka mea hiki ke hōʻoiaʻiʻo ua kauoha ʻia ka array?
Pehea la?
I ka nānā mua ʻana, hiki iā mākou ke kauoha mua i ka array a laila hoʻohana i ka hopena ma luna. Akā pehea e pili ai kēia i ka manawa hoʻokō?
ʻO ka algorithm maikaʻi loa ka wikiwiki me ka paʻakikī o ka manawa O (Nlog (N)). Inā mākou e hoʻohana iā ia i kā mākou hopena maikaʻi loa, e hoʻololi ia i kāna hana mai O (N) i O (Nlog (N)). Hiki ke loaʻa i kahi hoʻonā laina me kahi ʻano ʻole i hoʻonohonoho ʻia?
Hoʻolaha 4
Paʻakikī o ka manawa: O(N).
Paʻakikī lewa: O(N).
ʻAe, aia kahi hopena laina; no ka hana ʻana i kēia, pono mākou e hana i kahi ʻano hou i loaʻa ka papa inoa o nā pāʻani a mākou e ʻimi nei. ʻOi aku ka hoʻohana ʻana i ka hoʻomanaʻo: ʻo ia wale nō ka hopena o ka pepa me ka paʻakikī o ka lewa ma mua o O(1).
Inā he 1 ka waiwai mua o kahi pūʻali i hāʻawi ʻia a ʻo 8 ka waiwai huli, hiki iā mākou ke hoʻohui i ka waiwai 7 i ka pūʻulu "nā waiwai huli".
A laila, i kā mākou hana ʻana i kēlā me kēia ʻāpana o ka laha, hiki iā mākou ke nānā i ke ʻano o "nā waiwai huli" a ʻike inā like kekahi o lākou me kā mākou waiwai. Inā ʻae, e hoʻi ʻoiaʻiʻo.
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;
};ʻO ke kumu o ka hoʻonā ʻana he loop loop, e like me kā mākou i ʻike ai ma luna, he laina laina paʻakikī o O (N).
ʻO ka ʻāpana ʻelua o kā mākou hana ʻo Array.prototype.include(), kahi ala JavaScript e hoʻihoʻi ʻoiaʻiʻo a i ʻole hoʻopunipuni ma muli o ka loaʻa ʻana o ka waiwai i hāʻawi ʻia.
No ka ʻike ʻana i ka paʻakikī o ka manawa o Array.prototype.includes(), hiki iā mākou ke nānā i ka polyfill i hāʻawi ʻia e MDN (a kākau ʻia ma JavaScript) a i ʻole e hoʻohana i kahi ala i ke kumu kumu o kahi mīkini JavaScript e like me 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;
}
});
}Eia ka ʻāpana hoʻololi o Array.prototype.include() ʻo ia ka loop loop ma ka ʻanuʻu 7 (kokoke) e hele i ka lōʻihi holoʻokoʻa o ka array i hāʻawi ʻia. 'O ia ho'i, he laina laina kona pa'akikī o ka manawa. ʻAe, ʻoiai he ʻanuʻu mau ia ma hope o kā mākou papa kuhikuhi nui, ʻo ka paʻakikī o ka manawa ʻo O (N + (N - 1)). Ke hoʻohana nei i ka Big O Notation, hoʻomaʻamaʻa mākou iā ia i O(N) - no ka mea ʻo N ka hopena nui loa i ka wā e hoʻonui ai i ka nui o ka hoʻokomo.
E pili ana i ka paʻakikī spatial, makemake ʻia kahi ʻāpana ʻē aʻe nona ka lōʻihi e like me ke ʻano kumu (emi hoʻokahi, ʻae, akā hiki ke nānā ʻole ʻia), ka hopena o ka paʻakikī spatial O(N). ʻAe, hoʻonui ka hoʻohana ʻana i ka hoʻomanaʻo e hōʻoia i ka maikaʻi loa o ka algorithm.
Manaʻo wau e ʻike ʻoe i ka ʻatikala he mea hoʻohui i kāu nīnauele wikiō. Hōʻike ia e hiki ke hoʻoponopono ʻia kahi pilikia maʻalahi ma nā ʻano like ʻole me ka nui o nā kumuwaiwai i hoʻohana ʻia (manawa, hoʻomanaʻo).
Manaʻo ʻo Skillbox:
- Hoʻohana i ka papa pūnaewele .
- Papa hana pūnaewele .
- Papa makahiki hoʻomaʻamaʻa .
Source: www.habr.com