Nigbati Mo n ṣe ikẹkọ iṣẹ ti awọn algoridimu, Mo wa kọja eyi . Kii ṣe fun imọran nikan ti bii awọn ifọrọwanilẹnuwo ṣe ṣe ni awọn ile-iṣẹ imọ-ẹrọ nla, ṣugbọn tun gba ọ laaye lati loye bii awọn iṣoro algorithmic ṣe yanju bi daradara bi o ti ṣee.
Nkan yii jẹ iru accompaniment si fidio naa. Ninu rẹ Mo pese awọn asọye lori gbogbo awọn solusan ti o han, pẹlu ẹya ti ara mi ti ojutu ni JavaScript. Awọn nuances ti kọọkan alugoridimu ti wa ni tun sísọ.
A leti: fun gbogbo awọn oluka ti "Habr" - ẹdinwo ti 10 rubles nigbati o forukọsilẹ ni eyikeyi iṣẹ-ẹkọ Skillbox nipa lilo koodu ipolowo “Habr”.
Skillbox ṣe iṣeduro: Ilana ti o wulo .
Igbekalẹ iṣoro naa
A fun wa ni eto ti o paṣẹ ati iye kan pato. Lẹhinna o beere lọwọ lati ṣẹda iṣẹ kan ti o da pada ni otitọ tabi eke da lori boya apapọ awọn nọmba meji eyikeyi ninu titobi le dọgba iye ti a fun.
Ni awọn ọrọ miiran, awọn odidi meji wa ninu titobi, x ati y, pe nigba ti a ba fi kun papọ dogba iye pàtó kan?
Apẹẹrẹ A
Ti a ba fun wa ni opo kan [1, 2, 4, 9] ati pe iye rẹ jẹ 8, iṣẹ naa yoo pada si eke nitori pe ko si awọn nọmba meji ti o le ṣe afikun si 8.
Apẹẹrẹ B
Ṣugbọn ti o ba jẹ titobi [1, 2, 4, 4] ati pe iye naa jẹ 8, iṣẹ naa yẹ ki o pada si otitọ nitori 4 + 4 = 8.
Solusan 1: Brute agbara
Idiju akoko: O(N²).
Idiju aaye: O (1).
Itumọ ti o han julọ julọ ni lati lo bata ti awọn iyipo itẹ-ẹiyẹ.
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;
};Ojutu yii ko ṣiṣẹ daradara nitori pe o ṣayẹwo gbogbo apao awọn eroja meji ti o ṣee ṣe ninu titobi ati tun ṣe afiwe gbogbo awọn atọka meji lẹmeji. (Fun apẹẹrẹ, nigbati i = 1 ati j = 2 jẹ gangan kanna bi a ṣe afiwe pẹlu i = 2 ati j = 1, ṣugbọn ninu ojutu yii a gbiyanju awọn aṣayan mejeeji).
Nitoripe ojutu wa nlo bata ti itẹ-ẹiyẹ fun awọn lupu, o jẹ kuadiratiki pẹlu idiju akoko O(N²).
Solusan 2: Iwadi alakomeji
Idiju akoko: O(Nlog(N)).
Idiju aaye: O(1).
Niwọn igba ti a ti paṣẹ awọn akojọpọ, a le wa ojutu kan nipa lilo wiwa alakomeji. Eyi jẹ algoridimu ti o munadoko julọ fun awọn eto ti a paṣẹ. Wiwa alakomeji funrararẹ ni akoko ṣiṣe ti O(log(N)). Sibẹsibẹ, o tun nilo lati lo fun lupu lati ṣayẹwo ipin kọọkan lodi si gbogbo awọn iye miiran.
Eyi ni ohun ti ojutu kan le dabi. Lati jẹ ki awọn nkan ṣe kedere, a lo iṣẹ lọtọ lati ṣakoso wiwa alakomeji. Ati ki o tun awọn removeIndex () iṣẹ, eyi ti o pada awọn ti ikede ti awọn orun iyokuro awọn ti fi fun Ìwé.
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;
};Algoridimu bẹrẹ lati atọka [0]. Lẹhinna o ṣẹda ẹya ti orun laisi itọka akọkọ ati lo wiwa alakomeji lati rii boya eyikeyi ninu awọn iye to ku ni a le ṣafikun si titobi lati gbejade apao ti o fẹ. Iṣe yii ni a ṣe ni ẹẹkan fun eroja kọọkan ninu titobi.
Awọn fun lupu ara yoo ni a laini akoko complexity ti O (N), ṣugbọn inu awọn fun lupu a ṣe a alakomeji search, eyi ti yoo fun ẹya ìwò akoko complexity ti O (Nlog (N)). Ojutu yii dara ju ti iṣaaju lọ, ṣugbọn aaye tun wa fun ilọsiwaju.
Solusan 3: Akoko laini
Idiju akoko: O (N).
Idiju aaye: O (1).
Bayi a yoo yanju iṣoro naa, ni iranti pe a ti ṣeto titobi naa. Ojutu ni lati mu awọn nọmba meji: ọkan ni ibẹrẹ ati ọkan ni ipari. Ti abajade ba yatọ si ọkan ti o nilo, lẹhinna yi awọn ibẹrẹ ati awọn aaye ipari pada.
Ni ipari a yoo pade iye ti o fẹ ki a pada si otitọ, tabi awọn aaye ibẹrẹ ati ipari yoo ṣajọpọ ati pada eke.
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;
};
Bayi ohun gbogbo dara, ojutu dabi pe o dara julọ. Ṣugbọn tani le ṣe ẹri pe a ti paṣẹ titobi naa?
Kini nigbana?
Ni wiwo akọkọ, a le ti paṣẹ ni irọrun ni akọkọ ati lẹhinna lo ojutu loke. Ṣugbọn bawo ni eyi yoo ṣe ni ipa lori akoko ipaniyan?
Algoridimu ti o dara julọ jẹ ọna iyara pẹlu idiju akoko O (Nlog (N)). Ti a ba lo ninu ojutu ti o dara julọ, yoo yi iṣẹ rẹ pada lati O (N) si O (Nlog(N)). Ṣe o ṣee ṣe lati wa ojutu laini pẹlu opo ti a ko paṣẹ?
Ojutu 4
Idiju akoko: O (N).
Idiju aaye: O (N).
Bẹẹni, ojutu laini kan wa; lati ṣe eyi, a nilo lati ṣẹda akojọpọ tuntun ti o ni atokọ awọn ere-kere ti a n wa. Iṣowo-pipa nibi jẹ lilo iranti diẹ sii: o jẹ ojutu nikan ninu iwe pẹlu idiju aaye ti o tobi ju O (1).
Ti iye akọkọ ti titobi ti a fun jẹ 1 ati pe iye wiwa jẹ 8, a le ṣafikun iye 7 si titobi “awọn iye wiwa”.
Lẹ́yìn náà, bí a ṣe ń ṣe àkópọ̀ ọ̀kọ̀ọ̀kan àkójọpọ̀ ọ̀rọ̀ náà, a lè ṣàyẹ̀wò ìtòpọ̀ “àwọn iye ìṣàwárí” kí a sì rí i bóyá ọ̀kan nínú wọn bá iye wa dọ́gba. Ti o ba jẹ bẹẹni, pada otitọ.
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;
};Ipilẹ ti ojutu jẹ fun lupu, eyiti, bi a ti rii loke, ni idiju akoko laini ti O (N).
Apakan aṣetunṣe keji ti iṣẹ wa ni Array.prototype.include (), ọna JavaScript ti yoo pada si otitọ tabi eke da lori boya titobi ni iye ti a fun.
Lati mọ idiju akoko ti Array.prototype.includes (), a le wo polyfill ti a pese nipasẹ MDN (ati ti a kọ sinu JavaScript) tabi lo ọna kan ninu koodu orisun ti ẹrọ JavaScript bii 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;
}
});
}Nibi apakan aṣetunṣe ti Array.prototype.include () jẹ nigba ti lupu ni igbese 7 ti (fere) kọja gbogbo ipari ti titobi ti a fun. Eyi tumọ si pe idiju akoko rẹ tun jẹ laini. O dara, niwọn igba ti o jẹ igbesẹ kan nigbagbogbo lẹhin titobi akọkọ wa, idiju akoko jẹ O (N + (N - 1)). Lilo Big O Akọsilẹ, a jẹ ki o rọrun si O (N) - nitori pe o jẹ N ti o ni ipa ti o tobi julọ nigbati o nmu iwọn titẹ sii.
Nipa idiju aye, a nilo afikun orun ti gigun rẹ ṣe afihan titobi atilẹba (iyokuro ọkan, bẹẹni, ṣugbọn iyẹn le ṣe akiyesi), ti o mu abajade O(N) eka aaye. O dara, lilo iranti pọ si ni idaniloju ṣiṣe ti o pọju ti algorithm.
Mo nireti pe nkan naa wulo bi afikun si ifọrọwanilẹnuwo fidio rẹ. O fihan pe iṣoro ti o rọrun ni a le yanju ni awọn ọna oriṣiriṣi pẹlu awọn oriṣiriṣi awọn ohun elo ti a lo (akoko, iranti).
Skillbox ṣe iṣeduro:
- Ohun elo online dajudaju .
- Ẹkọ ori ayelujara .
- Eko odun to wulo .
orisun: www.habr.com