Коли я займався вивченням продуктивності алгоритмів, мені трапилося ось . Воно не лише дає уявлення, як відбуваються співбесіди у великих технологічних корпораціях, а й дозволяє зрозуміти, як вирішуються алгоритмічні завдання, причому максимально ефективно.
Ця стаття – своєрідний супровід до відео. У ній я даю коментарі всім показаним рішенням плюс власну версію рішення на 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 < 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;
};
Тепер все добре, рішення начебто оптимальне. Але хто гарантує, що масив був упорядкованим?
Що тоді?
На перший погляд, ми могли спочатку просто впорядкувати масив, а потім використати рішення вище. Але як це вплине на час виконання?
Найкращий алгоритм – швидке сортування з тимчасовою складністю 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