Калі я займаўся вывучэннем прадукцыйнасці алгарытмаў, мне трапілася вось . Яно не толькі дае ўяўленне, як праходзяць сумоўі ў буйных тэхналагічных карпарацыях, але і дазваляе зразумець, як вырашаюцца алгарытмічныя задачы, прычым максімальна эфектыўна.
Гэты артыкул - своеасаблівае суправаджэнне да відэа. У ёй я даю каментары да ўсіх паказаных рашэнняў плюс уласную версію рашэння на JavaScript. Таксама абмяркоўваюцца нюансы кожнага алгарытму.
Нагадваем: для ўсіх чытачоў "Хабра" - зніжка 10 000 рублёў пры запісе на любы курс Skillbox па промакодзе "Хабр".
Skillbox рэкамендуе: Практычны курс .
Пастаноўка задачы
Нам даюць спарадкаваны масіў і вызначанае значэнне. Затым просяць стварыць функцыю, якая вяртае true ці false, у залежнасці ад таго, ці можа сума любых двух лікаў з масіва быць роўнай зададзенаму значэнню.
Іншымі словамі, ці ёсць у масіве два цэлыя лікі x і y, якія пры складанні роўныя паказанаму значэнню?
Прыклад А
Калі нам далі масіў [1, 2, 4, 9] і значэнне 8, функцыя верне false, таму што ніякія два лікі з масіва не могуць даць 8 у суме.
Прыклад Б
Але калі гэта масіў [1, 2, 4, 4] і значэнне 8, функцыя павінна вярнуць true, таму што 4 + 4 = 8.
Рашэнне 1. Брутфорс
Часавая складанасць: O(N²).
Прасторавая складанасць: O(1).
Найбольш відавочнае значэнне - выкарыстанне пары ўкладзеных цыклаў.
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;
};Гэтае рашэнне нельга назваць эфектыўным, бо яно правярае кожную магчымую суму двух элементаў у масіве, а таксама параўноўвае кожную пару індэксаў двойчы.
Паколькі нашае рашэнне выкарыстоўвае пару ўкладзеных цыклаў for, яно з'яўляецца квадратычным з часовай складанасцю O (N²).
Рашэнне 2. Двайковы (бінарны) пошук
Часавая складанасць: O(Nlog(N)).
Прасторавая складанасць: O(1).
Паколькі масівы ўпарадкаваны, мы можам пашукаць рашэнне з выкарыстаннем бінарнага пошуку. Гэта найболей эфектыўны алгарытм для спарадкаваных масіваў. Сам па сабе бінарны пошук мае час выканання O (log(N)). Аднак усё роўна трэба выкарыстоўваць цыкл for, каб праверыць кожны элемент па ўсіх іншых значэннях.
Вось як можа выглядаць рашэнне. Каб усё было зразумела, мы выкарыстоўваем асобную функцыю для кантролю бінарнага пошуку. А таксама функцыю removeIndex (), якая вяртае версію масіва за вылікам зададзенага азначніка.
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;
};Алгарытм стартуе з азначніка [0]. Затым ён стварае версію масіва, выключаючы першы азначнік, і выкарыстае бінарны пошук, каб праверыць, ці можна дадаць да масіва якое-небудзь з пакінутых значэнняў для атрымання жаданай сумы. Гэтае дзеянне выконваецца адзін раз для кожнага элемента ў масіве.
Сам па сабе цыкл for будзе мець лінейную часавую складанасць O(N), але ўсярэдзіне цыкла for мы выконваем двайковы пошук, што дае агульную часавую складанасць O(Nlog(N)).
Рашэнне 3. Лінейны час
Часавая складанасць: O(N).
Прасторавая складанасць: O(1).
Цяпер мы будзем вырашаць задачу, падушачы, што масіў адсартаваны. Рашэнне складаецца ў тым, каб узяць два лікі: адно ў пачатку і адно ў канцы. Калі вынік адрозніваецца ад патрабаванага, то мяняем пачатковую і канчатковую кропку.
У рэшце рэшт мы або сустрэнем жаданае значэнне і вернем true, або пачатковая і канчатковая кропкі сыдуцца і вернецца false.
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;
};Цяпер усё добра, рашэнне быццам бы аптымальнае. Але хто дасць гарантыю, што масіў быў спарадкаваны?
Што тады?
На першы погляд, мы маглі спачатку проста ўпарадкаваць масіў, а затым выкарыстоўваць рашэнне вышэй. Але як гэта паўплывае на час выкананьня?
Лепшы алгарытм - хуткая сартаванне c часовай складанасцю O (Nlog (N)). Калі скарыстаемся ім у нашым аптымальным рашэнні, яно зменіць сваю прадукцыйнасць з O(N) на O(Nlog(N)). Ці можна знайсці лінейнае рашэнне з неўпарадкаванай масівам?
Рашэнне 4
Часавая складанасць: O(N).
Прасторавая складанасць: O(N).
Так, лінейнае рашэнне існуе, для гэтага трэба стварыць новы масіў, які змяшчае спіс супадзенняў, якія мы шукаем. Кампраміс тут у больш актыўным выкарыстанні памяці: гэта адзінае рашэнне ў артыкуле з прасторавай складанасцю, якая перавышае O(1).
Калі першае значэнне дадзенага масіва роўна 1, а шуканае значэнне роўна 8, мы можам дадаць значэнне 7 у масіў "значэнняў пошуку".
Затым, апрацоўваючы кожны элемент масіва, можам праверыць масіў "значэнняў пошуку" і паглядзець, ці роўна адно з іх нашаму значэнню Калі так, вяртаем true.
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;
};Аснова рашэння - цыкл for, які, як мы бачылі вышэй, мае лінейную часовую складанасць O (N).
Другая ітэрацыйная частка нашай функцыі - Array.prototype.include (), метад JavaScript, які будзе вяртаць true або false у залежнасці ад таго, ці ўтрымоўвае масіў зададзенае значэнне.
Каб высветліць часовую складанасць Array.prototype.includes (), мы можам разгледзець polyfill, які прадстаўляецца MDN (і напісаны на JavaScript), або скарыстацца метадам у зыходным кодзе рухавічка JavaScript, такога як 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;
}
});
}Тут ітэрацыйная частка Array.prototype.include () з'яўляецца цыклам while на кроку 7, які (амаль) перасякае ўсю даўжыню дадзенага масіва. Гэта азначае, што яго часавая складанасць таксама лінейная. Ну а паколькі яна заўсёды знаходзіцца на адзін крок ззаду нашага асноўнага масіва, то часавая складанасць роўная O (N + (N - 1)). Скарыстаўшыся Big O Notation, спрашчаем яе да O (N) таму што менавіта N мае найвялікі ўплыў пры павелічэнні ўваходнага памеру.
Што да прасторавай складанасці, неабходны дадатковы масіў, даўжыня якога адлюстроўвае зыходны масіў (мінус адзін, так, але гэта можна ігнараваць), што прыводзіць да прасторавай складанасці O (N). Ну а павялічанае выкарыстанне памяці забяспечвае максімальную эфектыўнасць алгарытму.
Спадзяюся, артыкул апынецца для вас карыснай у якасці дадатку да відэаінтэрв'ю. Яна паказвае, што простая задача можа быць вырашана некалькімі рознымі спосабамі з рознай колькасцю выкарыстоўваных рэсурсаў (час, памяць).
Skillbox рэкамендуе:
- Прыкладны анлайн-курс .
- Анлайн-курс .
- Практычны гадавы курс .
Крыніца: habr.com
