Када сам проучавао перформансе алгоритама, наишао сам на ово . Не само да даје идеју о томе како се интервјуи спроводе у великим технолошким корпорацијама, већ вам такође омогућава да разумете како се алгоритамски проблеми решавају што ефикасније.
Овај чланак је својеврсна пратња видеу. У њему дајем коментаре на сва приказана решења, плус своју верзију решења у ЈаваСцрипт-у. Такође се разматрају нијансе сваког алгоритма.
Подсећамо: за све читаоце „Хабра“ – попуст од 10 рубаља при упису на било који курс Скиллбок користећи промотивни код „Хабр“.
Скиллбок препоручује: Практични курс .
Проблем статемент
Дат нам је уређен низ и одређена вредност. Затим се тражи да креира функцију која враћа тачно или нетачно у зависности од тога да ли збир било која два броја у низу може бити једнак датој вредности.
Другим речима, да ли у низу постоје два цела броја, к и и, који када се саберу представљају наведену вредност?
Пример А
Ако нам је дат низ [1, 2, 4, 9] и вредност је 8, функција ће вратити нетачно јер два броја у низу не могу сабирати 8.
Пример Б
Али ако је то низ [1, 2, 4, 4] и вредност је 8, функција би требало да врати труе јер је 4 + 4 = 8.
Решење 1: Груба сила
Временска сложеност: О(Н²).
Сложеност простора: О(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;
};Ово решење није ефикасно јер проверава сваки могући збир два елемента у низу и такође два пута упоређује сваки пар индекса. (На пример, када је и = 1 и ј = 2 је заправо исто као поређење са и = 2 и ј = 1, али у овом решењу покушавамо обе опције).
Пошто наше решење користи пар угнежђених фор петљи, оно је квадратно са О(Н²) временском сложеношћу.
Решење 2: Бинарно претраживање
Временска сложеност: О(Нлог(Н)).
Сложеност простора: О(1).
Пошто су низови уређени, решење можемо тражити коришћењем бинарне претраге. Ово је најефикаснији алгоритам за уређене низове. Сама бинарна претрага има време рада О(лог(Н)). Међутим, и даље морате да користите фор петљу да проверите сваки елемент у односу на све друге вредности.
Ево како би решење могло да изгледа. Да би ствари биле јасне, користимо посебну функцију за контролу бинарне претраге. И такође функција ремовеИндек(), која враћа верзију низа минус дати индекс.
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]. Затим креира верзију низа искључујући први индекс и користи бинарну претрагу да види да ли се нека од преосталих вредности може додати низу да би се произвео жељени збир. Ова радња се изводи једном за сваки елемент у низу.
Сама фор петља ће имати линеарну временску сложеност од О(Н), али унутар фор петље вршимо бинарну претрагу, што даје укупну временску сложеност од О(Нлог(Н)). Ово решење је боље од претходног, али још увек има простора за побољшање.
Решење 3: Линеарно време
Временска сложеност: О(Н).
Сложеност простора: О(1).
Сада ћемо решити проблем, сећајући се да је низ сортиран. Решење је да узмете два броја: један на почетку и један на крају. Ако се резултат разликује од траженог, промените почетну и завршну тачку.
На крају ћемо или наићи на жељену вредност и вратити тачно, или ће се почетна и крајња тачка конвергирати и вратити нетачно.
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;
};
Сада је све у реду, решење је изгледа оптимално. Али ко може да гарантује да је низ наручен?
Шта онда?
На први поглед, могли смо једноставно прво да наручимо низ, а затим да користимо решење изнад. Али како ће то утицати на време извршења?
Најбољи алгоритам је брзо сортирање са временском сложеношћу О (Нлог (Н)). Ако га користимо у нашем оптималном решењу, промениће свој учинак са О(Н) на О(Нлог(Н)). Да ли је могуће пронаћи линеарно решење са неуређеним низом?
Решење 4
Временска сложеност: О(Н).
Сложеност простора: О(Н).
Да, постоји линеарно решење; да бисмо то урадили, морамо да креирамо нови низ који садржи листу подударања које тражимо. Овде је компромис већа употреба меморије: то је једино решење у раду са комплексношћу простора већом од О(1).
Ако је прва вредност датог низа 1, а вредност претраге 8, можемо додати вредност 7 низу „вредности претраге“.
Затим, док обрађујемо сваки елемент низа, можемо проверити низ „вредности претраге“ и видети да ли је један од њих једнак нашој вредности. Ако јесте, вратите труе.
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;
};Основа решења је фор петља, која, као што смо видели горе, има линеарну временску сложеност од О(Н).
Други итеративни део наше функције је Арраи.прототипе.инцлуде(), ЈаваСцрипт метода која ће вратити тачно или нетачно у зависности од тога да ли низ садржи дату вредност.
Да бисмо схватили временску сложеност Арраи.прототипе.инцлудес(), можемо погледати полифил који обезбеђује МДН (и написан у ЈаваСцрипт-у) или да користимо метод у изворном коду ЈаваСцрипт мотора као што је Гоогле В8 (Ц++).
// 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;
}
});
}Овде је итеративни део Арраи.прототипе.инцлуде() вхиле петља у кораку 7 која (скоро) прелази целу дужину датог низа. То значи да је и његова временска сложеност линеарна. Па, пошто је увек један корак иза нашег главног низа, временска сложеност је О (Н + (Н - 1)). Користећи Биг О нотацију, поједностављујемо је на О(Н) - јер управо Н има највећи утицај када повећавамо величину улаза.
Што се тиче просторне сложености, потребан је додатни низ чија дужина одражава оригинални низ (минус један, да, али то се може занемарити), што резултира О(Н) просторном сложеношћу. Па, повећана употреба меморије осигурава максималну ефикасност алгоритма.
Надам се да ће вам чланак бити користан као додатак вашем видео интервјуу. Показује да се једноставан проблем може решити на неколико различитих начина са различитим количинама коришћених ресурса (време, меморија).
Скиллбок препоручује:
- Примењени онлајн курс .
- Онлајн курс .
- Практична година курса .
Извор: ввв.хабр.цом