Когато изучавах производителността на алгоритмите, попаднах на . То не само предоставя представа как се провеждат интервютата в големите технологични компании, но и позволява да се разбере как се решават алгоритмични задачи, по най-ефективния начин.
Тази статия е своеобразно допълнение към видеото. В нея давам коментари по всички показани решения, плюс моя версия на решението на JavaScript. Също така се обсъждат нюансите на всеки алгоритъм.
Напомняме: за всички читатели на «Хабра» — отстъпка от 10 000 рубли при записване на всеки курс Skillbox с промокод «Хабр».
Skillbox препоръчва: Практически курс .
Формулиране на задачата
Дават ни подреден масив и определена стойност. След това ни питат да създадем функция, която връща true или false в зависимост от това, може ли сумата на две числа от масива да бъде равна на зададената стойност.
Или казано по друг начин, има ли в масива две цели числа x и y, които при събиране дават указаната стойност?
Пример А
Ако ни е given масив [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), но в него изпълняваме двоично търсене, което дава обща времева сложност O(Nlog(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(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
