Когда я занимался изучением производительности алгоритмов, мне попалось вот это видео с мок-интервью Google. Оно не только дает представление, как проходят собеседования в крупных технологических корпорациях, но и позволяет понять, как решаются алгоритмические задачи, причем максимально эффективно.
Эта статья — своеобразное сопровождение к видео. В ней я даю комментарии ко всем показанным решениям плюс собственную версию решения на JavaScript. Также обсуждаются нюансы каждого алгоритма.
Напоминаем: для всех читателей «Хабра» — скидка 10 000 рублей при записи на любой курс Skillbox по промокоду «Хабр».Skillbox рекомендует: Практический курс «Мобильный разработчик PRO».
Постановка задачи
Нам дают упорядоченный массив и определенное значение. Затем просят создать функцию, которая возвращает 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;
};
Теперь все хорошо, решение вроде бы оптимальное. Но кто даст гарантию, что массив был упорядоченным?
Что тогда?
На первый взгляд, мы могли сначала просто упорядочить массив, а затем использовать решение выше. Но как это повлияет на время выполнения?
Лучший алгоритм — быстрая сортировка 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 рекомендует:
Комментариев нет:
Отправить комментарий