Когато се занимавах с изследване на производителността на алгоритми, попаднах на това . То не само че дава представа как протичат интервютата в големи технологични корпорации, но и позволява да се разбере как се решават алгоритмични задачи, и то по максимално ефективен начин.
Тази статия е своеобразно придружително съдържание към видеото. В нея давам коментари на всички показани решения плюс собствена версия на решението на 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;
};Това решение не може да се нарече ефективно, тъй като проверява всяка възможна сума на два елемента в масива и сравнява всяка двойка индекси два пъти. (Например, когато i = 1 и j = 2 — това всъщност е същото като да се сравни с i = 2 и j = 1, но в това решение пробваме и двата варианта).
Тъй като нашето решение използва двойка вложени цикли for, то е квадратно с времева сложност O (N²).
Решение 2. Двоичен (бинарен) търсене
Времева сложност: O(Nlog(N)).
Пространствена сложност: O(1).
Тъй като масивите са подредени, можем да потърсим решение с помощта на бинарно търсене. Това е най-ефективният алгоритъм за подредени масиви. Самото бинарно търсене има време за изпълнение O (log (N)). Въпреки това все още трябва да използваме цикъл for, за да проверим всеки елемент спрямо всички останали стойности.
Ето как може да изглежда решението. За да е всичко ясно, използваме отделна функция за управлението на бинарно търсене. Също така, функцията removeIndex(), която връща версия на масива, без зададения индекс.
const findSum = (arr, val) => {
for (let i = 0; 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]) {
start = pivot + 1;
};
pivot = Math.floor((start + end) / 2);
if (arr[pivot] === val) {
return true;
}
};
return false;
};Алгоритъмът стартира от индекс [0]. След това той създава версия на масива, без първия индекс, и използва бинарно търсене, за да провери дали може да добави някое от останалите стойности, за да получи желаната сума. Тази операция се изпълнява веднъж за всеки елемент в масива.
Сам по себе си цикълът for ще има линейна времева сложност O(N), но вътре в цикъла for извършваме бинарно търсене, което дава обща времева сложност O(N log(N)). Това решение е по-добро от предишното, но все още има какво да се подобрява.
Решение 3. Линейно време
Времева сложност: O(N).
Пространствена сложност: O(1).
Сега ще решаваме задачата, имайки предвид, че масивът е сортиран. Решението е да вземем две числа: едно в началото и едно в края. Ако резултатът не е равен на изискваното, тогава сменяме началната и крайната точка.
В крайна сметка ще срещнем желаната стойност и ще върнем true, или началната и крайната точки ще се срещнат и ще върне false.
const findSum = (arr, val) => {
let start = 0;
let end = arr.length - 1;
while (start val) {
end -= 1;
} else if (sum < val) {
start += 1;
} else {
return true;
};
};
return false;
};Сега всичко е наред, решението изглежда оптимално. Но кой може да гарантира, че масивът е бил подреден?
Какво ще стане тогава?
На пръв поглед, можем първо просто да подредим масива и след това да използваме горното решение. Но как това ще повлияе на времето за изпълнение?
Най-добрият алгоритъм е бързото сортиране с времева сложност O(N log(N)). Ако го използваме в нашето оптимално решение, то ще промени производителността си от O(N) на O(N log(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
