Сложность алгоритмов и нотация Big O
Что такое (О большое)
О-большое (Big O) – это специальная нотация, используемая для описания асимптотической сложности; то есть, скорости роста времени выполнения алгоритма с увеличением размера входных данных. Это нужно, чтобы понимать, насколько быстро или медленно работают алгоритмы. В О-большом нет коэффициентов, минут, секунд и так далее. Об этом будет наглядно показано в примере про логарифмическую сложность O(log n).
O(1) - Константная сложность
Такая сложность у нас будет, если у нас лёгкий алгоритм, который никак не взаимодействует с итерируемыми входными данными, например, такой лёгкой функцией:
function sum (x,y) {
return x + y;
}
sum(10,10);
Такая сложность означает, что время выполнения не зависит от входных данных, то есть константная, что значит, темп роста это постоянная константа.
Или вот такой пример:
let arr = [1,2,3,4,5];
console.log(arr[2]) // 3
Мы просто получаем элемент по индексу в массиве. Если у нас массив будет из 1000 элементов, то скорость получения одного элемента по индексу не изменится, поэтому сложность такого алгоритма также будет O(1).
O(N) - Линейная сложность
Линейная сложность O(N) - это когда время выполнения алгоритма пропорционально размеру входных данных. Если есть какая-то последовательность действий, будь то перебор списка или последовательность циклов, то у всего этого будет сложность O(N).
Линейный поиск:
const arr = [1,2,3,4,5];
function linearSearch(value, list) {
let found = false;
let position = -1;
let index = 0;
while(!found && index < list.length) {
if(list[index] == value) {
found = true;
position = index;
} else {
index += 1;
}
}
// если тут еще будут какие то не вложенные друг в друга цилкы, то сложность все равно будет O(N)
return position;
}
console.log(linearSearch(8,arr)); // -1
console.log(linearSearch(3,arr)); // индекс 2
Например, если нам нужно найти имя из массива, где есть 20 имён, и для того, чтобы его найти, мы используем линейный поиск, то в худшем случае нам потребуется 20 операций, это и есть линейная сложность. Еще раз подчерку, что если у нас внутри такого поиска будет хоть 10 не вложенных циклов, сложность все равно будет линейная.
O(n * n) или O(n2) - Квадратичная сложность
O(n2) или O(n * n) - это квадратичная сложность, такие алгоритмы имеют в себе два вложенных цикла: Один нужен для того чтобы проходить по всему массиву, а второй, чтобы находить место очередному элементу в уже отсортированной части.
const arr = [9,2,3,5,9,1,10,58,-10];
function selectionSort(arr) {
for(let i = 0; i < arr.length; i++) { // внешний цикл
let indexMin = i;
for(let j = i+1; j < arr.length; j++) { // внутрений цикл, который каждую итерацию внешнего цикла будет проходить все элементы в массиве
if(arr[j] < arr[indexMin]) {
indexMin = j;
}
}
let tmp = arr[i];
arr[i] = arr[indexMin];
arr[indexMin] = tmp;
}
return arr;
}
console.log(selectionSort(arr));
Увидели такой алгоритм с двумя циклами, значит это О(n2). Но что если будет подобный алгоритм, но внутри будет еще один вложенный цикл?
// просто псевод пример
function sort(arr) {
for () { // внешний цикл
for () { // внутрений цикл,
if (true) {
for () { // еще внутрений цикл,
if (true) {
// и тд
}
}
}
}
}
return arr;
}
В таком случае, сложность будет, как можно было догадаться, O(n3) - кубическая сложность и так далее. Если цикл будет не вложенный, то сложность не изменится. В общем, если с квадратичной сложностью размер данных увеличится в 2 раза, то время выполнения алгоритма увеличится в 4 раза, с кубической сложностью - в 8 раз, со сложностью четвертой степени - в 16 и так далее. Думаю, смысл понятен. Вложенные циклы могут значительно увеличивать сложность алгоритма, делая его менее эффективным (но не во всех случаях, конечно). Поэтому нужно учитывать эту особенность и стремиться к минимизации вложенных циклов, если это возможно.
O(2^n) Экспоненциальная сложность
Алгоритмы с этой сложностью выполняются очень медленно, в зависимости от количества входных данных.
Рекурсивный расчет чисел Фибоначчи:
function fibonacci(n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
fibonacci(4); // 3
fibonacci(5); // 5
fibonacci(6); // 8
fibonacci(80); // попробуете что то такое и браузер у вас скорее всего зависнет.
Это называется экспоненциальная сложность, потому что общее число операций в результате увеличивается в геометрической прогрессии. В том же рекурсивном расчете чисел Фибоначчи мы, вызывая функцию, вызываем ее еще два раза. В каждом из этих вызовов мы еще по два раза ее вызываем и так далее. Количество операций каждый раз удваивается.
O(log n) - Логарифмическое время
Логарифмическое время - это сложность, у которой количество операций уменьшается в два раза с каждой итерацией. Это обычно возможно при работе с более сложными структурами данных, например, при применении алгоритмов на деревьях или графах. Логарифмическое время может соответствовать принципу "разделяй и властвуй" (divide and conquer) - это метод проектирования алгоритмов, который заключается в разбиении задачи на более мелкие подзадачи и решении их независимо друг от друга, а затем объединении полученных результатов в общее решение исходной задачи.
- Логарифм - это обратная операция возведению в степень. Допустим, у нас есть 10 * 10 = 100 - это 102 степени. В свою очередь, логарифм будет обратно этому: log10100 = 2. То есть, если в степени мы ищем, то сколько будет, если 10 перемножить 2 раза, то в логарифме мы ищем, сколько раз нужно перемножить 10, чтобы получить 100.
В бинарном поиске, когда мы ищем элемент, мы ищем середину и, если позиция искомого элемента допустим больше, чем все то, что ниже середины, то эту часть мы отбрасываем. Далее повторяем с оставшейся частью, пока не найдем искомый элемент.
const array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
function binarySearch(array, item) {
let start = 0;
let end = array.length;
let middle;
let found = false;
let position = -1;
while (found === false && start <= end) {
middle = Math.floor((start + end) / 2);
if (array[middle] === item) {
found = true;
position = middle;
return position;
}
if (item < array[middle]) { // если искомый элемент меньше середины
end = middle - 1; // оставляем правую часть
}
else {
start = middle + 1; // иначе оставляем левую часть
}
}
return position;
}
console.log(binarySearch(array, 4)); // 3
Это важно!
Почему логарифм?-
Еще раз, при каждом шаге бинарного поиска или бинарного дерева множество делится на два подмножества, одно из которых выбрасывается, а второе остается. Это позволяет сокращать количество возможных вариантов в два раза на каждом шаге. Вспоминаем, что логарифм позволяет узнать нам сколько раз мы должны разделить массив на части(кол операций), что бы найти элемент. В случае с массивом из
10элементов в худшем случае нам понадобится4операции. log210 = 3.32, что округляется до 4. Двойка после log это основание дерева, если бы мы работали с тернарным деревом, там была бы тройка. Но! Мы сейчас не работаем с деревом. Просто бинарный поиск и бинарное дерево используют похожий алгоритм для поиска элементов в отсортированном множестве. Так вот в основании у нас2, массив из10элементов. Мы знаем, что в худшем случае нам понадобится4операции. Но как еще можно это определить? Мы можем поделить массив на основание пока не упремся в ноль или единицу10/2 = 5, 5/2 = 2.5, 2.5/2 = 1.25, 1.25/2 = 0,625= Мы сделали это за 4 раза. Значит, на массив из 10 имён потребовалось 4 операции. -
Так, почему же логарифм? Так вот, все потому что данные делятся на мелкие части, которые обрабатываются за одинаковое время. Таким образом, при увеличении размера входных данных вдвое, алгоритм будет выполняться на одну итерацию больше, а не удваивать время выполнения. Представим, что массив у нас теперь из 20 элементов, log220 = 4.322, округляется до 5. У нас массив стал в два раза больше, но количество операций увеличилось всего лишь на одну операцию. Вот это и есть алгоритм с логарифмическим временем, будь то работа с деревом или бинарный поиск по массиву.
-
Теперь самое интересное. Вы могли заметить, что работали мы сейчас с логарифмом, но не с нотацией O больше. В O большом нет никаких коэффициентов и количества операций или секунд, минут или чего угодно. В O большом для бинарного поиска на массиве из 10 элементов сложность будет O(log n), а для массива из 20 элементов или из 1000 - сложность будет та же самая - O(log n). Нам важен темп роста количества операций с увеличением размера входных данных. И, сравнивая алгоритм со сложностью O(log n) и алгоритм со сложностью O(n), мы будем знать, что первый алгоритм будет намного быстрее второго, а с увеличением входных данных он будет намного намного быстрее. Вот и вся суть.
О(n * log n) - Логарифмически линейная сложность
О (n * log n) - это сложность алгоритма, которая увеличивается с ростом размера входных данных (n), но растет в логарифмическом масштабе. Это означает, что при увеличении размера входных данных в n раз, время работы алгоритма увеличится примерно в log n раз.
Алгоритм быстрая сортировка:const values = [2, 27, 14, 52, 31, 96, 73, 47, 22, 6];
function QuickSort(List) {
if (List.length <= 1) {
return List;
}
const pivot = List[List.length - 1];
const leftList = [];
const rightList = [];
for (let i = 0; i < List.length - 1; i++) {
if (List[i] < pivot) {
leftList.push(List[i]);
}
else {
rightList.push(List[i]);
}
}
return [...QuickSort(leftList), pivot, ...QuickSort(rightList)]; // вот тут мы снова проходимся по каждому подмассиву
}
console.log(QuickSort(values));
У нас есть внутри рекурсивная операция, которая разделяет массив на меньшие части, и каждая часть сортируется по отдельности. Это ведет к сложности, равной произведению числа элементов в массиве (n) на количество разбиений (log n), что вместе дают нам сложность O(n * log n). То есть у нас есть две операции: разделение массива на части O(log n), цикл с итерациями по этим частям O(N), и общая сложность будет О(n * log n).
Итог.
- Получение элемента массива или какой либо коллекции – это O(1) или простая функция без итерируемых входных данных, это все будет O(1).
- Перебор массива или коллекции – это O(n). Даже если у нас будет несколько циклов, сложность будет та же, главное, чтобы они были не вложены друг в друга.
- Вложенные циклы по той же коллекции(массиву) – это O(n^2). Если есть три вложенных цикла, будет уже O(n^3) и так далее.
- Разделяй и властвуй (Divide and Conquer) – всегда O(log n). То есть, где мы делим структуру на подчасти.
- Итерации, которые используют “Разделяй и властвуй” (Divide and Conquer) – это O(n log n). Если мы используем деление на части O(log n) и при этом это все происходит в неких итерациях, то это O(n log n).
- O(2^n) – экспоненциальная сложность. Это когда количество операций удваивается при добавлении каждого нового элемента в набор данных.
И под конец давайте посмотрим на все сложности, от быстрого к медленному алгоритму, что бы знать, что в общем быстрее, а что нет в сравнении: быстро:[ O(1), O(log n), O(N), O(n * log n), O(n2) ]:медленно.
Ну и в конце я скажу, что следует помнить, это всё общая оценка и фактическая сложность алгоритма может зависеть от множества факторов, таких как объем данных, способ их обработки, используемые структуры данных и т.д.
Всем спасибо за внимание. Кому всем? ты тут один.
22.03.2023