Sa dihang nagtuon ko sa pasundayag sa mga algorithm, nakit-an nako kini . Dili lamang kini naghatag usa ka ideya kung giunsa ang mga interbyu gihimo sa dagkong mga korporasyon sa teknolohiya, apan gitugotan ka usab nga masabtan kung giunsa masulbad ang mga problema sa algorithm nga labing epektibo kutob sa mahimo.
Kini nga artikulo usa ka matang sa pagduyog sa video. Niini naghatag ako og mga komentaryo sa tanan nga mga solusyon nga gipakita, dugang sa akong kaugalingong bersyon sa solusyon sa JavaScript. Ang mga nuances sa matag algorithm gihisgutan usab.
Gipahinumduman namon ikaw: alang sa tanan nga mga magbabasa sa "Habr" - usa ka diskwento sa 10 nga mga rubles kung nagpalista sa bisan unsang kurso sa Skillbox gamit ang code sa promosyon nga "Habr".
Girekomenda sa Skillbox: Praktikal nga kurso .
Pagbuot sa problema
Gihatagan kami og usa ka ordered array ug usa ka piho nga bili. Gihangyo dayon kini nga maghimo usa ka function nga nagbalik nga tinuod o sayup depende kung ang kantidad sa bisan unsang duha nga numero sa array mahimong katumbas sa gihatag nga kantidad.
Sa laing pagkasulti, aduna bay duha ka integer sa laray, x ug y, nga kon idugang magkaparehas ang espesipikong bili?
Pananglitan A
Kung hatagan kita ug array [1, 2, 4, 9] ug ang value kay 8, ang function mobalik og false tungod kay walay duha ka numero sa array ang makadugang sa 8.
Pananglitan B
Apan kung kini usa ka laray [1, 2, 4, 4] ug ang kantidad mao ang 8, ang function kinahanglan mobalik nga tinuod tungod kay 4 + 4 = 8.
Solusyon 1: Brute force
Pagkakomplikado sa oras: O(N²).
Pagkakomplikado sa kawanangan: O(1).
Ang labing klaro nga kahulogan mao ang paggamit sa usa ka parisan sa nested loops.
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;
};Kini nga solusyon dili episyente tungod kay kini nagsusi sa matag posible nga sumada sa duha ka elemento sa laray ug nagtandi usab sa matag parisan sa mga indeks kaduha. (Pananglitan, kung ang i = 1 ug j = 2 sa tinuud parehas sa pagtandi sa i = 2 ug j = 1, apan sa kini nga solusyon gisulayan namon ang duha nga kapilian).
Tungod kay ang among solusyon naggamit og usa ka pares nga nested para sa mga loop, kini mao ang quadratic nga adunay O(N²) nga pagkakomplikado sa oras.
Solusyon 2: Binary nga Pagpangita
Pagkakomplikado sa oras: O(Nlog(N)).
Pagkakomplikado sa kawanangan: O(1).
Tungod kay gi-order ang mga arrays, makapangita kami og solusyon gamit ang binary search. Kini ang labing episyente nga algorithm alang sa gi-order nga mga arrays. Ang binary nga pagpangita mismo adunay oras sa pagdagan sa O(log(N)). Bisan pa, kinahanglan nimo nga mogamit usa ka para loop aron masusi ang matag elemento batok sa tanan nga ubang mga kantidad.
Ania kung unsa ang hitsura sa usa ka solusyon. Aron maklaro ang mga butang, naggamit kami og bulag nga function aron makontrol ang binary nga pagpangita. Ug usab ang removeIndex() function, nga nagbalik sa bersyon sa array minus ang gihatag nga indeks.
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;
};Ang algorithm nagsugod gikan sa index [0]. Naghimo kini usa ka bersyon sa array nga wala’y labot ang una nga indeks ug gigamit ang binary nga pagpangita aron mahibal-an kung adunay nahabilin nga mga kantidad nga mahimong idugang sa array aron makagama ang gusto nga kantidad. Kini nga aksyon gihimo kausa alang sa matag elemento sa array.
Ang for loop mismo adunay usa ka linear time complexity sa O(N), apan sa sulod sa for loop naghimo kami og binary search, nga naghatag sa kinatibuk-ang pagkakomplikado sa oras sa O(Nlog(N)). Kini nga solusyon mas maayo kaysa sa nauna, apan adunay lugar alang sa pag-uswag.
Solusyon 3: Linear nga oras
Pagkakomplikado sa oras: O(N).
Pagkakomplikado sa kawanangan: O(1).
Karon atong sulbaron ang problema, paghinumdom nga ang laray gihan-ay. Ang solusyon mao ang pagkuha sa duha ka numero: usa sa sinugdanan ug usa sa katapusan. Kung ang resulta lahi sa gikinahanglan, unya usba ang pagsugod ug pagtapos nga mga punto.
Sa kadugayan atong masugatan ang gitinguha nga kantidad ug mobalik nga tinuod, o ang pagsugod ug katapusan nga mga punto magtagbo ug mobalik nga sayup.
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;
};
Karon maayo na ang tanan, ang solusyon daw labing maayo. Apan kinsa ang makagarantiya nga ang laray gimando?
Unya unsa man?
Sa una nga pagtan-aw, mahimo ra unta namon nga i-order ang array ug dayon gamiton ang solusyon sa ibabaw. Apan sa unsang paagi kini makaapekto sa panahon sa pagpatay?
Ang labing kaayo nga algorithm mao ang quicksort nga adunay pagkakomplikado sa oras O (Nlog (N)). Kung gamiton nato kini sa atong labing maayo nga solusyon, kini mag-usab sa performance niini gikan sa O(N) ngadto sa O(Nlog(N)). Posible ba nga makit-an ang usa ka linear nga solusyon nga adunay usa ka wala masunud nga laray?
Solusyon 4
Pagkakomplikado sa oras: O(N).
Pagkakomplikado sa kawanangan: O(N).
Oo, adunay usa ka linear nga solusyon; aron mahimo kini, kinahanglan namon nga maghimo usa ka bag-ong laray nga adunay sulud nga lista sa mga posporo nga among gipangita. Ang trade-off dinhi mao ang dugang nga paggamit sa memorya: kini ang bugtong solusyon sa papel nga adunay kakomplikado sa wanang nga labaw pa sa O(1).
Kung ang una nga kantidad sa gihatag nga array kay 1 ug ang search value kay 8, mahimo natong idugang ang value 7 sa array nga "search values".
Dayon, samtang giproseso nato ang matag elemento sa array, atong masusi ang han-ay sa "mga bili sa pagpangita" ug tan-awon kon ang usa niini katumbas ba sa atong bili. Kung oo, balik nga tinuod.
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;
};Ang sukaranan sa solusyon mao ang usa ka para loop, nga, ingon sa atong nakita sa ibabaw, adunay usa ka linear nga panahon komplikado sa O(N).
Ang ikaduha nga iterative nga bahin sa atong function mao ang Array.prototype.include(), usa ka JavaScript nga pamaagi nga mobalik nga tinuod o bakak depende kung ang array naglangkob sa gihatag nga kantidad.
Aron mahibal-an ang pagkakomplikado sa oras sa Array.prototype.includes(), mahimo natong tan-awon ang polyfill nga gihatag sa MDN (ug gisulat sa JavaScript) o mogamit usa ka pamaagi sa source code sa usa ka JavaScript engine sama sa 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;
}
});
}Dinhi ang iterative nga bahin sa Array.prototype.include() mao ang while loop sa lakang 7 nga (halos) moagi sa tibuok gitas-on sa gihatag nga array. Kini nagpasabut nga ang pagkakomplikado sa oras niini linear usab. Aw, tungod kay kini kanunay nga usa ka lakang sa luyo sa among panguna nga laray, ang pagkakomplikado sa oras mao ang O (N + (N - 1)). Gamit ang Big O Notation, gipasimple namo kini sa O(N) - tungod kay kini ang N nga adunay labing dako nga epekto kung nagdugang ang gidak-on sa input.
Mahitungod sa spatial complexity, usa ka dugang nga array ang gikinahanglan kansang gitas-on nagsalamin sa orihinal nga array (minus one, oo, apan kana mahimong ibaliwala), nga moresulta sa O(N) spatial complexity. Aw, ang dugang nga paggamit sa panumduman nagsiguro sa labing kadaghan nga kahusayan sa algorithm.
Nanghinaut ko nga makita nimo nga mapuslanon ang artikulo ingon usa ka suplemento sa imong interbyu sa video. Nagpakita kini nga ang usa ka yano nga problema mahimong masulbad sa daghang lainlaing mga paagi nga adunay lainlaing kantidad sa mga kapanguhaan nga gigamit (oras, memorya).
Girekomenda sa Skillbox:
- Nag-apply online nga kurso .
- Online nga kurso .
- Praktikal nga tuig nga kurso .
Source: www.habr.com