"О" большое и временная сложность в JS
Что такое "О большое"?
Понятие нотации "О большое" и временная сложность являются фундаментальными понятиями в компьютерной науке.
O большое - это способ описать эффективность алгоритмов, не слишком углубляясь в детали. Он описывает, как время (или количество необходимых операций), затрачиваемое на выполнение, растет по мере увеличения размера входных данных.
- Нотация О большое помогает нам ответить на вопрос: "Как ведут себя, масштабируются наши функции или алгоритмы при значительном увеличении размера входных данных?".
Идея заключается в том, что нас волнуют вещи с разницей в размере. Например, при одинаковом количестве входных данных мне не так важно, работает ли мой алгоритм 100 мс против 105 мс, нам важно, работает ли он 100 мс против 10 секунд (большая, заметная разница).
При измерении О большого мы просто берем важные вещи. Например, O(4+2n) можно просто упростить до O(n), мы можем убрать "незначительные детали", такие как константа "+4" и даже коэффициент, которые не имеют большого значения при больших масштабах.
Мне нравится думать об О большом как об инструменте в глубине моего сознания, который помогает мне понять "большую картину", давая представление о том, насколько эффективен код или алгоритмы.
Временная сложность
Временная сложность - это способ показать, как время выполнения функции увеличивается с ростом размера входных данных. Она описывает количество компьютерного времени, которое требуется для выполнения функции.
Существует множество различных типов сложности времени, и вот некоторые из них.
- Постоянное время, O(1) - Если мы выполняем действия, требующие только одного шага, или когда нет циклов, то сложность равна O(1).
- Линейное время, O(n) - циклы, такие как циклы for и while, то есть то, что вызывает увеличение времени выполнения на величину, пропорциональную размеру входа. Например, массив из 100 элементов приводит к 100 циклам.
- Квадратичное время, O(n²) - Два вложенных цикла с одинаковым входом. Аналогично, если у нас три вложенных цикла, то временная сложность - кубическое время, O(n³).
- Примеры алгоритмов с квадратичным временем: Пузырьковая сортировка, сортировка вставкой - Логарифмическое время, O(log n) - Когда используется стратегия "разделяй и властвуй", говорят, что это O(log n). Логарифмическое время часто встречается в бинарном поиске, если ваша функция имеет О(log n) - значит вы все делаете правильно, это хороший показатель.
- Примеры алгоритмов с логарифмическим временем: Бинарный поиск - Факториальное время, O(n!) - Он самый сложный. Мы добавляем вложенный цикл для каждого элемента, пожалейте ваш компьютер.
Есть несколько основных правил, которые следует помнить, рассматривая "О большое" для алгоритма или кода.
Свод правил О большого
1. Наихудший случай
2. Удалить константы
3. Различные термины для входов
4. Отбросить недоминирующие значения
Правило 1: Наихудший случай
Всегда рассматривайте наихудший сценарий. Даже если цикл оборвется раньше, это не имеет значения, мы всегда берем большое O в худшем случае. Мы не можем просто предположить, что все всегда идет хорошо, даже если иногда наша функция может выполняться за O(1). Как показано в примере ниже, иногда нужный нам элемент находится по индексу 0, и мы завершаем работу раньше, но это все равно считается как O(n).
const carArr = ['Honda', 'BMW', 'Audi', 'Toyota', 'Proton', 'Nissan', 'Mazda'];
function findCar(array, car) {
for (let i = 0; i < array.length; i++) {
console.log('running');
if (array[i] === car) {
console.log(`Found ${car}`);
break;
}
}
}
findCar(carArr, 'Honda'); // По-прежнему O(n), даже несмотря на то, что потребовалась всего 1 итерация.Правило 2: Удалите константы
В этом примере мы создаем входной аргумент с длиной, которую мы определили (10), и передаем его в функцию. Внутри функции мы создаем массив под названием meaningLessArr с длиной, основанной на входном аргументе. У нас есть два console.log и цикл, чтобы выполнить цикл, длина которого в два раза больше длины входного аргумента.
В этом примере присвоение переменной meaningLessArr игнорируется, но это не имеет большого значения, поскольку в конечном итоге наша цель - удалить константы.
const removeConstantsExample = (arrInput) => {
const meaningLessArr = Array.from({
length: arrInput.length,
}).fill("😄"); // O(n)
console.log(meaningLessArr); // O(1)
console.log(meaningLessArr.length); // O(1)
// Проходимся по массиву циклом 2 раза
for (let i = 0; i < arrInput.length * 2; i++) {
console.log(`i is ${i}`); // O(2n)
}
};
const input = Array.from({ length: 10 });
removeConstantsExample(input); // O(n + 2 + 2n)- O(3n + 2) упрощается до O(3n + 1). Это происходит потому, что O(любая константа) упрощается до O(1). O(2) упрощается до O(1), O(100) → O(1), O(3333) → O(1) и так далее.
- O(3n + 1) затем упрощается до O(n + 1) путем удаления коэффициента. Ключевым здесь является то, что, будь то 3n, или 4n, или 5n, все они линейны, мы можем упростить их до простого n. Нас не особенно волнует, насколько крута линия, нас волнует, как она увеличивается, увеличивается ли она линейно, экспоненциально или как.
- И, наконец, это упрощается до O(n) после отбрасывания константы 1, так как 1 не имеет эффекта, когда входные данные велики.
Правило 3: Различные термины для входов
Когда у нас есть несколько входов или несколько аргументов, мы даем уникальный термин для каждого из них, поскольку они являются отдельными входами с разными размерами. Другими словами, сложность зависит от двух независимых факторов. В приведенном ниже примере n и m представляют собой размеры двух различных входов.
const logTwoArrays = (arr1, arr2) => {
arr1.forEach(item => {
console.log(item);
});
arr2.forEach(item => {
console.log(item);
});
};
// Большой O равен O(n + m)Давайте рассмотрим еще один пример с вложенными циклами. У нас есть две похожие функции, которые выполняют аналогичные действия. Разница в том, что makeTuples() принимает один аргумент, а makeTuplesTwo() принимает два аргумента. Таким образом, можно сказать, что makeTuples() зависит от одного независимого фактора, а makeTuplesTwo() - от двух.
const nums = [1,2,3];
const emojis = ['😄', '🚗'];
const makeTuples = (arr) => {
let tuples = [];
arr.forEach(firstItem => {
arr.forEach(secondItem => {
tuples.push([firstItem, secondItem]);
});
});
return tuples;
};
console.log(makeTuples(nums));
// [
// [1, 1], [1, 2], [1, 3],
// [2, 1], [2, 2], [2, 3],
// [3, 1], [3, 2], [3, 3],
// ]
// ^ Для данного примера это O(n^2) - Квадратичное время
const makeTuplesTwo = (arr1, arr2) => {
let answer = [];
arr1.forEach(firstItem => {
arr2.forEach(secondItem => {
answer.push([firstItem, secondItem]);
});
});
return answer;
};
console.log(makeTuplesTwo(nums, emojis));
// [
// [1, '😄'], [1, '🚗'],
// [2, '😄'], [2, '🚗'],
// [3, '😄'], [3, '🚗']
// ]
// Этот пример будет O(n * m)Давайте сделаем быструю практику! Каково «О большое» для приведенной ниже функции?
const nums = [1,2,3];
const emojis = ['😄', '🚗'];
const logFirstArrThenMakeTuples = (arr1, arr2) => {
arr1.forEach(item => {
console.log(item);
});
let answer = [];
arr1.forEach(firstItem => {
arr2.forEach(secondItem => {
answer.push([firstItem, secondItem]);
});
});
return answer;
};
console.log(logFirstArrThenMakeTuples(nums, emojis));
// 1 2 3
// [
// [1, '😄'], [1, '🚗'],
// [2, '😄'], [2, '🚗'],
// [3, '😄'], [3, '🚗']
// ]Ответ: O(n + n * m). Еще лучше, мы можем сказать, что это O(n * m). Это потому, что здесь мы можем упростить ситуацию. Выразив O(n + n * m) как O(n * (1 + m)), мы теперь можем увидеть 1 + m. 1 + m можно упростить до просто m. Поэтому после упрощения мы получаем O(n * m) или чаще просто записывают O(nm).
Правило 4: Отбросьте недоминирующие значения
На самом деле, если вы понимаете концепцию упрощения, например, упрощение O(n + nm) до O(nm) в задании выше, то вы, вероятно, уже понимаете это правило. По сути, это та же идея.
Опять же, если у нас есть что-то вроде O(n² + n), то его можно упростить до O(n²), отбросив + n.
Или мы можем представить, когда n велико, тогда +n, вероятно, не дает большого эффекта. В этом случае n² является доминирующим значением, большим и важным значением, а "+ n" - нет. Мы игнорируем маленькие части и пытаемся сосредоточиться на больших.
Для уравнения 2x² + x + 30 давайте попробуем подставить некоторые числа.
Подставляя 3, получаем 18 + 3 + 30.
Подставляя 10, получаем 200 + 10 + 30.
Подставляя 500, получаем 500000 + 500 + 30.
Подставьте 100000, получим 20 000 000 + 100000 + 30.
По сути, x² является тем, что вносит вклад в огромный разрыв, поэтому мы принимаем его за О большое.
Заключение
- Big O не имеет большого значения, когда входные данные недостаточно велики. Если функция написана для приема только фиксированного, небольшого количества данных, то в этом случае мы не особенно заботимся о сложности времени и пространства.
- За все приходится платить. Иногда написание эффективного кода приводит к тому, что код становится трудночитаемым, и наоборот. Цель программиста состоит в том, чтобы найти баланс между эффективностью и читабельностью кода, в зависимости от проблем и ситуаций.
Источник: https://dev.to/wnxn/introduction-to-big-o-notation-and-time-complexity-in-javascript-2m5j