Noong pinag-aaralan ko ang pagganap ng mga algorithm, nakita ko ito . Hindi lamang ito nagbibigay ng ideya kung paano isinasagawa ang mga panayam sa malalaking kumpanya ng teknolohiya, ngunit nagbibigay-daan din sa iyo na maunawaan kung paano nalulutas ang mga problema sa algorithm nang mas mahusay hangga't maaari.
Ang artikulong ito ay isang uri ng saliw sa video. Sa loob nito ay nagbibigay ako ng mga komento sa lahat ng mga solusyon na ipinakita, kasama ang sarili kong bersyon ng solusyon sa JavaScript. Ang mga nuances ng bawat algorithm ay tinalakay din.
Pinapaalala namin sa iyo: para sa lahat ng mga mambabasa ng "Habr" - isang diskwento na 10 rubles kapag nag-enroll sa anumang kurso sa Skillbox gamit ang code na pang-promosyon ng "Habr".
Inirerekomenda ng Skillbox ang: Praktikal na kurso .
Pahayag ng problema
Bibigyan kami ng isang ordered array at isang partikular na halaga. Pagkatapos ay hihilingin na lumikha ng isang function na nagbabalik ng totoo o mali depende sa kung ang kabuuan ng anumang dalawang numero sa array ay maaaring katumbas ng isang ibinigay na halaga.
Sa madaling salita, mayroon bang dalawang integer sa array, x at y, na kapag pinagsama-sama ay katumbas ng tinukoy na halaga?
Halimbawa A
Kung bibigyan tayo ng array [1, 2, 4, 9] at ang value ay 8, ang function ay magbabalik ng false dahil walang dalawang numero sa array ang maaaring magdagdag ng hanggang 8.
Halimbawa B
Ngunit kung ito ay isang array [1, 2, 4, 4] at ang value ay 8, ang function ay dapat magbalik ng true dahil 4 + 4 = 8.
Solusyon 1: Brute force
Pagiging kumplikado ng oras: O(N²).
Pagiging kumplikado ng espasyo: O(1).
Ang pinaka-halatang kahulugan ay ang paggamit ng isang pares ng 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;
};Ang solusyon na ito ay hindi mahusay dahil sinusuri nito ang bawat posibleng kabuuan ng dalawang elemento sa array at inihahambing din ang bawat pares ng mga indeks nang dalawang beses. (Halimbawa, kapag ang i = 1 at j = 2 ay talagang kapareho ng paghahambing sa i = 2 at j = 1, ngunit sa solusyon na ito sinubukan namin ang parehong mga pagpipilian).
Dahil ang aming solusyon ay gumagamit ng isang pares ng nested para sa mga loop, ito ay quadratic na may O(N²) time complexity.
Solusyon 2: Binary Search
Pagiging kumplikado ng oras: O(Nlog(N)).
Pagiging kumplikado ng espasyo: O(1).
Dahil nakaayos ang mga array, maaari tayong maghanap ng solusyon gamit ang binary search. Ito ang pinaka mahusay na algorithm para sa mga nakaayos na array. Ang binary search mismo ay may tumatakbong oras ng O(log(N)). Gayunpaman, kailangan mo pa ring gumamit ng for loop upang suriin ang bawat elemento laban sa lahat ng iba pang mga halaga.
Narito kung ano ang maaaring maging hitsura ng isang solusyon. Upang gawing malinaw ang mga bagay, gumagamit kami ng isang hiwalay na function upang kontrolin ang binary na paghahanap. At gayundin ang function na removeIndex(), na ibinabalik ang bersyon ng array na binawasan ang ibinigay na index.
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 ay nagsisimula sa index [0]. Pagkatapos ay gagawa ito ng isang bersyon ng array na hindi kasama ang unang index at gumagamit ng binary na paghahanap upang makita kung alinman sa mga natitirang halaga ay maaaring idagdag sa array upang makagawa ng nais na kabuuan. Ang pagkilos na ito ay ginagawa nang isang beses para sa bawat elemento sa array.
Ang for loop mismo ay magkakaroon ng linear time complexity ng O(N), ngunit sa loob ng for loop nagsasagawa kami ng binary search, na nagbibigay ng pangkalahatang pagiging kumplikado ng oras ng O(Nlog(N)). Ang solusyon na ito ay mas mahusay kaysa sa nauna, ngunit mayroon pa ring puwang para sa pagpapabuti.
Solusyon 3: Linear na oras
Pagiging kumplikado ng oras: O(N).
Pagiging kumplikado ng espasyo: O(1).
Ngayon ay malulutas namin ang problema, naaalala na ang array ay pinagsunod-sunod. Ang solusyon ay kumuha ng dalawang numero: isa sa simula at isa sa dulo. Kung ang resulta ay naiiba mula sa kinakailangang isa, pagkatapos ay baguhin ang panimulang at pagtatapos na mga punto.
Sa kalaunan ay makakatagpo tayo ng nais na halaga at magbabalik ng true, o ang mga punto ng simula at pagtatapos ay magtatagpo at magbabalik ng mali.
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;
};
Ngayon ang lahat ay maayos, ang solusyon ay tila pinakamainam. Ngunit sino ang makakagarantiya na ang array ay iniutos?
Ano ngayon?
Sa unang sulyap, maaari sana nating inutusan muna ang array at pagkatapos ay ginamit ang solusyon sa itaas. Ngunit paano ito makakaapekto sa oras ng pagpapatupad?
Ang pinakamahusay na algorithm ay quicksort na may time complexity O (Nlog (N)). Kung gagamitin natin ito sa ating pinakamainam na solusyon, babaguhin nito ang pagganap nito mula O(N) patungong O(Nlog(N)). Posible bang makahanap ng isang linear na solusyon na may isang hindi nakaayos na array?
Solusyon 4
Pagiging kumplikado ng oras: O(N).
Pagiging kumplikado ng espasyo: O(N).
Oo, mayroong isang linear na solusyon; para magawa ito, kailangan nating lumikha ng bagong array na naglalaman ng listahan ng mga tugma na hinahanap natin. Ang trade-off dito ay higit na paggamit ng memorya: ito ang tanging solusyon sa papel na may mas kumplikadong espasyo kaysa O(1).
Kung ang unang value ng isang array ay 1 at ang search value ay 8, maaari naming idagdag ang value 7 sa array na "search values".
Pagkatapos, habang pinoproseso namin ang bawat elemento ng array, maaari naming suriin ang hanay ng "mga halaga ng paghahanap" at tingnan kung ang isa sa mga ito ay katumbas ng aming halaga. Kung oo, ibalik ang totoo.
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 batayan ng solusyon ay para sa loop, na, tulad ng nakita natin sa itaas, ay may linear time complexity ng O(N).
Ang pangalawang umuulit na bahagi ng aming function ay Array.prototype.include(), isang JavaScript method na magbabalik ng true o false depende sa kung ang array ay naglalaman ng ibinigay na value.
Upang malaman ang pagiging kumplikado ng oras ng Array.prototype.includes(), maaari nating tingnan ang polyfill na ibinigay ng MDN (at nakasulat sa JavaScript) o gumamit ng paraan sa source code ng isang JavaScript engine gaya ng 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;
}
});
}Narito ang umuulit na bahagi ng Array.prototype.include() ay ang while loop sa hakbang 7 na (halos) bumabagtas sa buong haba ng ibinigay na array. Nangangahulugan ito na ang pagiging kumplikado ng oras nito ay linear din. Well, dahil ito ay palaging isang hakbang sa likod ng aming pangunahing hanay, ang pagiging kumplikado ng oras ay O (N + (N - 1)). Gamit ang Big O Notation, pinapasimple namin ito sa O(N) - dahil N ang may pinakamalaking epekto kapag pinapataas ang laki ng input.
Tungkol sa spatial complexity, kailangan ng karagdagang array na ang haba ay sumasalamin sa orihinal na array (minus one, oo, ngunit iyon ay maaaring balewalain), na nagreresulta sa O(N) spatial complexity. Kaya, ang pagtaas ng paggamit ng memorya ay nagsisiguro ng pinakamataas na kahusayan ng algorithm.
Umaasa ako na nakita mong kapaki-pakinabang ang artikulo bilang pandagdag sa iyong panayam sa video. Ipinapakita nito na ang isang simpleng problema ay maaaring malutas sa maraming iba't ibang paraan na may iba't ibang dami ng mga mapagkukunang ginamit (oras, memorya).
Inirerekomenda ng Skillbox ang:
- Nag-apply online na kurso .
- Online na kurso .
- Praktikal na kurso sa taon .
Pinagmulan: www.habr.com