Осваиваем нотацию Big O и примеры в JavaScript
Что такое временная сложность?
При написании кода мы хотим убедиться, что наши программы эффективны и работают быстро. Однако по мере того, как программы становятся более сложными и обрабатывают большие объемы данных, время их выполнения может резко увеличиться. Вот тут-то и возникает временная сложность.
Временная сложность — это важное понятие в информатике, которое измеряет эффективность алгоритма с точки зрения времени, необходимого для его выполнения, в зависимости от размера его входных данных. В частности, временная сложность описывает, как время работы алгоритма растет по мере увеличения размера входных данных.
Обозначение Big O обычно используется для выражения временной сложности, обеспечивая верхнюю границу скорости роста алгоритма по мере увеличения размера входных данных. Другими словами, нотация большого O описывает, как время выполнения алгоритма масштабируется по отношению к размеру входных данных.
В этой статье мы рассмотрим основы временной сложности, включая общие обозначения и некоторые примеры в JavaScript.
Почему временная сложность важна?
Важно понимать временную сложность алгоритма, поскольку это может помочь определить его практичность для решения задач различного масштаба. Например, если у нас есть два алгоритма, решающих одну и ту же задачу, мы можем использовать анализ временной сложности, чтобы определить, какой из них быстрее и эффективнее. Алгоритм с низкой временной сложностью будет более эффективным и действенным при решении задач, чем алгоритм с более высокой временной сложностью, особенно для больших объемов входных данных.
Поэтому крайне важно проанализировать временную сложность алгоритма, чтобы оптимизировать его производительность и повысить эффективность.
Кроме того, анализ временной сложности может помочь нам оптимизировать наш код и повысить производительность наших программ. Анализируя временную сложность различных частей нашего кода, мы можем выявить узкие места и области, требующие оптимизации.
Как анализировать временную сложность?
Чтобы проанализировать временную сложность алгоритма, нам нужно подсчитать количество операций, которые он выполняет, в зависимости от размера входных данных. Размер ввода обычно обозначается «n» и представляет собой количество элементов во входных данных.
Существует несколько распространенных типов операций, которые учитываются при анализе временной сложности, в том числе:
- Арифметические операции (например, сложение, вычитание, умножение, деление)
- Вызовы функций
- Рекурсивные вызовы
- Итерации цикла
- Сравнения (например, меньше, больше, равно)
- Присваивания (например, x = y)
Как только мы подсчитали количество операций, мы можем выразить временную сложность алгоритма, используя нотацию большого O.
Обозначение большого O
Нотация Big O — это математическая нотация, описывающая предельное поведение функции, когда аргумент стремится к определенному значению или бесконечности. В контексте временной сложности он используется для описания верхней границы скорости роста алгоритма по мере увеличения размера входных данных.
Например, если алгоритм имеет временную сложность O(n), это означает, что количество выполняемых им операций растет линейно с размером входных данных. Если размер ввода удвоится, количество операций также удвоится.
Вот некоторые распространенные классы временной сложности и соответствующие им нотации большого O:
- O(1) — постоянная временная сложность
- O(log n) — логарифмическая временная сложность
- O(n) — линейная временная сложность
- O(n log n) — линейно-временная сложность
- O(n²) — квадратичная временная сложность
- O(n³) — кубическая временная сложность
- O(2^n) — экспоненциальная временная сложность
Давайте рассмотрим каждый из этих классов временной сложности более подробно.
O(1) — постоянная временная сложность
Алгоритм имеет временную сложность O(1), если количество выполняемых им операций не зависит от размера входных данных. Другими словами, алгоритму требуется одинаковое количество времени для работы независимо от входных данных.
Вот пример алгоритма с временной сложностью O(1):
function printFirstElement(arr) {
console.log(arr[0]);
}
Эта функция принимает массив в качестве входных данных и печатает первый элемент. Количество выполняемых им операций всегда равно единице, независимо от размера массива.
O(log n) — логарифмическая временная сложность
Алгоритм имеет временную сложность O(log n), если количество выполняемых им операций растет логарифмически с размером входных данных. Логарифмический рост означает, что количество операций увеличивается медленно по мере увеличения размера входных данных.
Вот пример алгоритма с временной сложностью O(log n):
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
Эта функция выполняет двоичный поиск в отсортированном массиве, чтобы найти индекс целевого значения. Количество выполняемых им операций пропорционально логарифму входного размера (т. е. длины массива).
Вот еще один пример, демонстрирующий временную сложность O(log n):
function findPower(base, exponent) {
let result = 1;
for (let i = 1; i <= exponent; i *= 2) {
if (i & exponent) {
result *= base;
}
base *= base;
}
return result;
}
Эта функция принимает базовое число base и показатель степени exponent и возвращает результат base, возведенный в степень exponent.
Функция инициализирует переменную result значением 1 и входит в цикл for, который продолжается, пока переменная цикла i меньше или равна exponent, и обновляет i до i, умноженного на 2 на каждой итерации.
Внутри цикла функция проверяет, установлен ли ith бит exponent в 1, используя побитовую операцию AND. Если это так, функция умножает result на base.
Затем функция возводит в квадрат значение base на каждой итерации цикла.
Поскольку переменная цикла i растет логарифмически с размером exponent, цикл выполняется O(log n) раз, где n — размер exponent.
Следовательно, временная сложность этой функции равна O(log n).
O(n) — линейная временная сложность
Алгоритм имеет временную сложность O(n), если количество выполняемых им операций растет линейно с размером входных данных. Линейный рост означает, что количество операций увеличивается с той же скоростью, что и размер входных данных.
Вот пример алгоритма с временной сложностью O(n):
function sumArray(arr) {
let sum = 0;
for (let i = 0; i < arr.length; i++) {
sum += arr[i];
}
return sum;
}
Временная сложность функции sumArray равна O(n), где n — длина входного массива arr.
Функция использует цикл for для перебора каждого элемента в массиве и добавления его к текущей сумме. Поскольку цикл выполняет итерацию по каждому элементу массива ровно один раз, время, необходимое для выполнения цикла, пропорционально длине массива, что дает линейную временную сложность O (n).
Другими словами, по мере увеличения размера входного массива время, необходимое для вычисления суммы его элементов, увеличивается линейно. Это означает, что если входной массив очень большой, выполнение функции займет пропорционально больше времени, чем если бы входной массив был очень маленьким. Количество операций, которые он выполняет, пропорционально длине массива.
O(n log n) — линейно-временная сложность
Алгоритм имеет временную сложность O(n log n), если количество выполняемых им операций увеличивается пропорционально n-кратному логарифму n. Линейный рост означает, что количество операций увеличивается быстрее, чем линейный рост, но медленнее, чем квадратичный рост.
Вот пример алгоритма с временной сложностью O(n log n):
function mergeSort(arr) {
if (arr.length <= 1) {
return arr;
}
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}
function merge(left, right) {
const result = [];
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
return result.concat(left, right);
}
Эта функция выполняет сортировку слиянием массива, чтобы отсортировать его элементы в порядке возрастания. Количество операций, которые он выполняет, пропорционально логарифму n, умноженному на n.
Вот еще один пример алгоритма с временной сложностью O(n log n):
for (let i = 1; i <= n; i++) {
for (let j = 1; j < n; j = j * 2) {
console.log("Hey - I'm busy looking at: " + i + " and " + j);
}
}
Этот код имеет временную сложность O(n log n).
Внешний цикл for выполняется n раз, а внутренний цикл for выполняется log n раз для каждой итерации внешнего цикла. Это связано с тем, что значение j удваивается на каждой итерации внутреннего цикла, а это означает, что цикл завершится после логарифмической базы 2 из n итераций. Следовательно, общее количество итераций равно n * log n, что приводит к временной сложности O (n log n).
С точки зрения того, что делает код, он просто печатает сообщение для каждой комбинации i и j, которую он проверяет. Внутренний цикл выполняется меньше раз, чем внешний цикл, поэтому он оптимизирует процесс перебора всех возможных пар i и j.
O(n²) — квадратичная временная сложность
Алгоритм имеет временную сложность O(n²), если количество выполняемых им операций растет квадратично с размером входных данных. Квадратичный рост означает, что количество операций увеличивается гораздо быстрее, чем размер входных данных.
Вот пример алгоритма с временной сложностью O(n²):
function bubbleSort(arr) {
for (let i = 0; i < arr.length - 1; i++) {
for (let j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
Эта функция выполняет пузырьковую сортировку массива, чтобы отсортировать его элементы в порядке возрастания. Количество выполняемых им операций пропорционально квадрату входного размера.
Вот еще один пример алгоритма с временной сложностью O(n²):
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
console.log(i + ", " + j);
}
}
Этот код выводит все возможные комбинации i и j, где i находится в диапазоне от 0 до n-1, а j находится в диапазоне от 0 до n-1. Внешний цикл for повторяется n раз, а внутренний цикл for повторяется n раз для каждой итерации внешнего цикла, в результате чего получается n² итераций.
Временная сложность этого кода равна O(n²), потому что количество итераций растет квадратично с увеличением n. Этот тип алгоритма часто называют «вложенным циклом for» или «двойным циклом» и обычно используется для таких задач, как алгоритмы поиска и сортировки, умножение матриц и других задач, связанных с перебором всех возможных пар элементов.
O(2^n) — экспоненциальная временная сложность
Алгоритм имеет временную сложность O(2^n), если количество операций, которые он выполняет, удваивается с каждым дополнительным входным элементом. Экспоненциальный рост означает, что количество операций экспоненциально увеличивается с размером входных данных.
Вот пример алгоритма с временной сложностью O(2^n):
function fibonacci(n) {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
Эта функция рекурсивно вычисляет n-е число в последовательности Фибоначчи. Количество выполняемых им операций пропорционально 2^n.
Заключение
Таким образом, временная сложность — это мера того, как время работы алгоритма растет по мере увеличения размера входных данных. Это обычно выражается с использованием нотации большого O, которая описывает верхнюю границу количества операций, выполняемых алгоритмом. Существует несколько общих временных сложностей, включая O(1), O(log n), O(n), O(n log n), O(n²) и O(2^n). Понимание временной сложности важно для разработки эффективных алгоритмов и анализа их производительности.
Я надеюсь, что это объяснение было полезным и легким для понимания. Если у вас есть дополнительные вопросы, не стесняйтесь спрашивать!
