Обозначение Big O помогает нам анализировать и сравнивать производительность алгоритмов. В мире алгоритмов «наилучший сценарий» представляет собой наиболее идеальные условия, при которых алгоритм работает с максимальной эффективностью, а «наихудший сценарий» представляет собой наиболее сложные условия, когда алгоритму требуется больше всего времени для выполнения задачи.
Для анализа алгоритмов мы проверяем две сложности: временную и пространственную.
Временная сложность
Временная сложность — это мера того, как время работы алгоритма масштабируется в зависимости от размера входных данных. Это помогает нам сравнивать и анализировать эффективность алгоритмов с точки зрения их производительности в наихудшем случае.
Космическая сложность
Пространственная сложность — это мера того, сколько дополнительной памяти или памяти требуется алгоритму при увеличении размера входных данных.
Содержание
- O(1) — постоянное время
- O(logn) — логарифмическое время
- O(n) — линейное время
- O(n²) — квадратичное время
- O(2^n) — Экспоненциальная временная сложность
O(1) — постоянное время
Независимо от размера входных данных, введенных в алгоритм, время, затрачиваемое алгоритмом, фиксировано.
Мы можем привести примеры, как показано ниже;
- Математические проблемы
- Поиск значения с индексом в массиве
- Достичь хеша с помощью ключа
Пример:
В приведенном ниже примере значения timeOfSmallArray и timeOfHugeArray будут рассчитаны одновременно. Следовательно, его сложность равна O(1).
const smallArray = [1, 2, 3, 4, 5]
const hugeArray = [1, 2, 3, ... 100000000]
fucntion getFirstValueFromArray(array){
const firstValue = n[0]
return firstValue
}
let timeOfSmallArray = getFirstValueFromArray(smallArray)
let timeOfHugeArray = getFirstValueFromArray(hugeArray)
O(log n) — логарифмическое время
Это алгоритмы, в которых время алгоритма увеличивается логарифмически при увеличении входных данных алгоритма. Чаще всего он используется в задачах «разделяй и властвуй».
Пример:
В качестве примера из реальной жизни у нас есть массив, содержащий несколько букв, отсортированных в алфавитном порядке, и мы хотим найти данную букву. Сначала он проверит середину букв, находится ли данная буква дальше средней буквы. он проверит правые буквы средней буквы, и так будет до тех пор, пока не будет найдена данная буква.
function findIndexOfLetter(array, letter) {
let left = 0;
let right = array.length;
while (left < right) {
let middle = Math.ceil((left + right) / 2);
if (array[middle] > letter) {
right = middle;
} else if (array[middle] < letter) {
left = middle;
} else {
return middle;
}
}
}
findLetter(["a", "b", "c", "k", "l", "y", "z"], "c");
// output: 2
O(N) — линейное время
По мере увеличения входных данных алгоритма затраченное время увеличивается с той же скоростью.
В качестве примера из реальной жизни: если кран наполняет литр за одну минуту, он наполняет десять литров за десять минут и тысячу литров за тысячу минут. Поскольку количество литров приближается к тысячам и миллионам, для меня это становится худшим вариантом (наихудшим вариантом).
В программировании это обычно происходит с такими методами, как forEach, for, Map и Reduc.
Пример:
В приведенном ниже примере функция getFirstValueFromArray(smallArray) будет рассчитана раньше, чем функция getFirstValueFromArray(hugeArray), поскольку количество значений HugeArray больше, чем количество SmallArray.
const smallArray = [1, 2, 3, 4, 5]
const hugeArray = [1, 2, 3, ... 100000000]
function showEveryItemFromArray(array){
for(let i=0; i < array.length; i++){
console.log(array[i])
}
}
let timeOfSmallArray = showEveryItemFromArray(smallArray)
let timeOfHugeArray = showEveryItemFromArray(hugeArray)
O(n²) — квадратичное время
Когда входные данные алгоритма увеличиваются, продолжительность алгоритма увеличивается на квадрат приращения входных данных.
Ситуации большинства базовых алгоритмов сортировки - это O(n²), и для них это наихудший случай алгоритма, как показано в примерах ниже;
- Алгоритм пузырьковой сортировки
- Алгоритм сортировки вставками
- Алгоритм сортировки выбором
Пример:
У нас есть пример наихудшего случая пузырьковой сортировки. Его сложность O(n²). Если входные данные включают 5 элементов и занимают 25 секунд, а если входные данные включают 10 элементов, это займет 100 секунд.
const array = [5, 4, 3, 2, 1];
for (let i = 0; i < array.length; i++) {
for (let j = 0; j < array.length - i - 1; j++) {
if (array[j] > array[j + 1]) {
[array[j], array[j + 1]] = [array[j + 1], array[j]];
}
}
}
console.log(array); // Output: [1, 2, 3, 4, 5]
O(2^n) — Экспоненциальная временная сложность
Когда введенный ввод увеличивается на единицу, количество выполняемых операций удваивается. В качестве очень хорошего примера можно привести последовательность Фибоначчи.
Пример:
Число Фибоначчи представляет собой математическую последовательность, в которой сумма двух предыдущих чисел становится третьим числом и так далее. Первые две цифры — 0 и 1, далее так: 1, 2, 3, 5, 8, 13…
Если заданное число для функции ниже является огромным, выходные данные достигнут очень высокого значения.
const recursiveFibonacci = (n) => {
if (n < 2) {
return n;
}
return recursiveFibonacci(n - 1) + recursiveFibonacci(n - 2);
};
recursiveFibonacci(6);
// Output: 8
Вывод:
Обозначение Big O помогает разработчикам анализировать производительность алгоритмов. Это позволяет нам оптимизировать и создавать больше алгоритмов производительности.
Ресурсы:
Что такое нотация Big O — FreeCodeCamp
Большая О-нотация — ХанАкадемия
