Алгоритм - это последовательность действий, которые решают какую-нибудь задачу. Любой код можно назвать алгоритмом.
- O - о большое, по сути аннотация сложности или скорости алгоритма, на оси это t- время. n - количество операций(всегда указывается максимальное кол-во итерации, то есть наихудший сценарий)
- Некоторые алгоритмы являются эффективнее чем другие.
- Эффективность не всегда равна скорости алгоритма. Некоторые алгоритмы могут быть медленее но более эффективны.
Быстрый пример: Сравнения линейного алгоритма и бинарного на примере обычного массива [0,1,2,3,4,5,6,7,8,9]. Ищем число 7:
В линейном мы идем по каждому элементу - это долго, кол-во операций 10. В бинарном делим алгоритм на 2 берем последнее число(5) и спрашиваем больше ли оно 7 или нет, итд. Таким образом бинарный алгоритм в разы быстрее и эффективнее.
const array = [1, 4, 5, 8, 5, 1, 2, 7, 5, 2, 11];
let count = 0;
function linearSearch(array, item) {
for (let i = 0; i < array.length; i++) {
// count - количество итераций
count += 1;
if (array[i] === item) {
// Возвращаем индекс элемента при нахождении
return i;
}
}
// Возвращаем null если элемент не найден
return null;
}const array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15];
let count = 0;
// Реализация с помощью цикла.
// Суть: Находим средний элемент массива, если он равен искомогу, то возращаем его индекс.
// Если больше, то орезаем правую часть, а если меньше, то левую.
function binarySearch(array, item) {
// Позиция первого элемента
let start = 0;
// Позиция последнего элемента
let end = array.length;
// Позиция среднего элемента в массиве
let middle;
// Флаг, который показывает найден ли элемент в массиве
let found = false;
// Позиция найденого элемента. Если элемент не найден, то возвращаем -1
let position = -1;
// Цикл работатет до тех пор либо пока не найден элемент, либо пока стартовая и конечная позиция не поровнялись.
while (found === false && start <= end) {
// Кол-во итераций
count += 1;
// Внутри цикла высчитываем позицию центрального элемента
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;
}// Реализация с помощью рукурсии.
// item - сам элемент, который ищем
// стартовую и конечную позицию передаем через параметры
function recursiveBinarySearch(array, item, start, end) {
let middle = Math.floor((start + end) / 2);
count += 1;
if (item === array[middle]) {
return middle;
}
if (item < array[middle]) {
// отсеиваем всю правую часть
return recursiveBinarySearch(array, item, start, middle - 1);
} else {
// отсеиваем всю левую часть
return recursiveBinarySearch(array, item, middle + 1, end);
}
}// Сортировка выбором(Selection Sort)
const arr = [
0, 3, 2, 5, 6, 8, 1, 9, 4, 2, 1, 2, 9, 6, 4, 1, 7, -1, -5, 23, 6, 2, 35, 6, 3,
32,
];
let count = 0;
// Суть: Есть массив неупорядоченных элементов. Находим в цикле МИНИМАЛЬНЫЙ элемент,
// затем меняем местами с первым элементом, затем опять пробегаемся по массиву и находим минимальное значение,
// но меняем его уже со вторым элементом, затем с 3,4 итд пока не будет отсортирован весь массив.
function selectionSort(array) {
// Этот цикл просто идет по всем элементам
for (let i = 0; i < array.length; i++) {
let indexMin = i;
// Во вложенном цикле ищется МИНИМАЛЬНЫЙ элемент на данную итерацию
for (let j = i + 1; j < array.length; j++) {
if (array[j] < array[indexMin]) {
indexMin = j;
}
count += 1;
}
// Меняем местами минимальный элемент с current элементом (i)
let tmp = array[i];
array[i] = array[indexMin];
array[indexMin] = tmp;
}
// Возвращаем отсортированный массив
return array;
}
// Кол-во итераций 325. Длина массива 26. Таким образом O(1/2*n*n),
// но коэффициенты в оценке сложности алгоритма не учавствуют. Поэтому будет O(n*n)
console.log(selectionSort(arr));
console.log(arr.length);
console.log("count = ", count);const arr = [
0, 3, 2, 5, 6, 8, 23, 9, 4, 2, 1, 2, 9, 6, 4, 1, 7, -1, -5, 23, 6, 2, 35, 6,
3, 32, 9, 4, 2, 1, 2, 9, 6, 4, 1, 7, -1, -5, 23, 9, 4, 2, 1, 2, 9, 6, 4, 1, 7,
-1, -5, 23,
];
let count = 0;
// Суть: в двойном цикле пробегаемся по всему массиву и сравниваем попарно лежащие элементы.
// Если следующий элемент массива меньше чем предыдуший, то мы меняем их местами.
// Получается "всплытие" самый большой элемент с каждой итерацией потихоньку всплывает наверх.
function bubbleSort(array) {
for (let i = 0; i < array.length; i++) {
for (let j = 0; j < array.length; j++) {
if (array[j + 1] < array[j]) {
let tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
}
count += 1;
}
}
return array;
}
console.log("length", arr.length);
console.log(bubbleSort(arr)); // O(n*n)
console.log("count = ", count);// Рекурсия - это функция, которая вызывает сама себя.
// Рекурсия должна всегда иметь условие, при котором вызов функции прекращается,
// иначе будет переполнение стека вызова.
// Факториал - это n * (n-1) * (n-2) * (n-3) ...
const factorial = (n) => {
if (n === 1) {
return 1;
}
return n * factorial(n - 1);
};
// Числа фибоначчи - 1,1,2,3,5,8,13,21
const fibonachi = (n) => {
if (n === 1 || n === 2) {
return 1;
}
return fibonachi(n - 1) + fibonachi(n - 2);
};
// Быстрая сортировка(Quick Sort)
const arr = [
0, 3, 2, 5, 6, 8, 23, 9, 4, 2, 1, 2, 9, 6, 4, 1, 7, -1, -5, 23, 6, 2, 35, 6,
3, 32, 9, 4, 2, 1, 2, 9, 6, 4, 1, 7, -1, -5, 23, 9, 4, 2, 1, 2, 9, 6, 4, 1, 7,
-1, -5, 23,
];
let count = 0;
// Суть: Работает по принципу "Разделяй и властвуй". Мы делим массив на подмассивы и каждый раз рекурсивно.
// Выбираем опорный элемент у каждого массива(его можно выбрать случайно, но чаще всего берут центральный).
// Пробегаемся по массиву и все элементы, которые по значению меньше опорного - добавляем в один массив,
// а все которые больше - в другой. И для каждого из этих массивов выполняется такая же операция.
// Так делается до тех пор, пока длина массива не станет равна 1.
function quickSort(array) {
if (array.length <= 1) {
return array;
}
// pivotIndex - опорный индекс элемента, в нашем случае берем центральный (array.length / 2)
let pivotIndex = Math.floor(array.length / 2);
// pivot - сам опорный элемент, в нашем случае берем центральный
let pivot = array[pivotIndex];
// массив с числами, которые меньше чем опорные
let less = [];
// массив с числами, которые больше чем опорные
let greater = [];
// Проходимся по всему массиву и наполняем массивы less и greater
for (let i = 0; i < array.length; i++) {
count += 1;
if (i === pivotIndex) continue;
if (array[i] < pivot) {
less.push(array[i]);
} else {
greater.push(array[i]);
}
}
// Проделывем ту же самую операцию с двумя след. массивами
return [...quickSort(less), pivot, ...quickSort(greater)];
}
// Граф - это некая абстрактная структура данных, предствляющая собой множество
// вершин и набор ребер(т.е соединений между парами вершин).
// Ребра бывают однонаправленными и двунаправленными, то есть если из "A" можно попасть только в "B" - это однонаправленность.
// А если можно из "A" в "B" и из "B" в "A" - - это двунаправленность.
const graph = {};
graph.a = ["b", "c"];
graph.b = ["f"];
graph.c = ["d", "e"];
graph.d = ["f"];
graph.e = ["f"];
graph.f = ["g"];
// Задача: Найти существует ли путь из точки "A" в точку "G" за минималльное кол-во шагов.
// Этот алгоритм:
// 1) Решает задачу поиска пути в графу, существует ли такой путь
// 2) Находит путь за минимальное кол-во шагов
function breadthSearch(graph, start, end) {
// Очередь(queue) - структура данных состоящая из каких-то элементов.
// Основной принцип заключается в том, что элементы всегда добавляются в конец структуры, а
// извлекаются из ее начала. Принцип как в очереди в жизни: кто первым пришел на кассу, тот из
// нее первый и уходит. Такой принцип называется FIFO - first in first out.
let queue = [];
// В очередь сразу добавляем стартовую вершину(start, в данном случае "a")
queue.push(start);
// Крутим цикл while пока в очереди есть хотя бы один элемент
while (queue.length > 0) {
// Из начала очереди достаем текущую вершину
const current = queue.shift();
// Если по текущей вершине в графе ничего не находится, то присваиваем этой вершине пустой массив
if (!graph[current]) {
graph[current] = [];
}
// Если в графе по текущей вершине массив содержит конечную точку, то мы завершаем выполнение
// программы и возвращаем true. То есть на данном этапе мы обошли весь граф и пришли
// к пункту назначения.
if (graph[current].includes(end)) {
return true;
} else {
// Если это условие не отработало, то мы должны добавить в очередь новые вершины.
// Поэтому разворачиваем то, что уже находится в очереди в массив и в конец разворачиваем массив
// который лежит в графе по текущей вершине.
queue = [...queue, ...graph[current]];
}
}
return false;
}
// Алгоритм дейкстры для поиска кратчайшего пути в графе (Dijkstra's algorithm)
// Если в поиске в ширину мы находим кратчайший путь передвигаясь по вершинам графа,
// и не важно длительный этот путь или нет, самое главное это количество пройденных участков,
// то в алгоритме дейкстры учитывается и длина пройеднного ребра, так называемый вес.
// Суть: За стартовую точку принимаем A, за конечную G. Состовляется табличка, в которую на первом этапе
// записываются значения тех вершин, в которые мы можем попасть из стартовой точки. Все остальные
// вершины являются не достижимыми и мы их помечаем знаком бесконечности. На втором этапе мы помечаем эти вершины
// как уже рассмотренные. На третьем этапе мы рассматриваем вершины, в которые мы можем попасть из точек B и C
// и в таблицу записываем значение от точки A, до точек, которые мы достигаем из вершин B и C. Потом опять помечаем эти точки
// как уже рассмотренные. На следующем этапе мы достигаем точки G, но у нас происходит перерасчет, мы находим путь до точки F,
// которая оказывается короче и перезаписываем значение в таблице и на следующем этапе мы проделаем все тоже самое и находим
// самый оптимальный путь и узнаем, что из точки A в точку G мы можем добраться за 5 условных единиц.
const graph = {};
// Цифры это веса ребер (или длина)
graph.a = { b: 2, c: 1 };
graph.b = { f: 7 };
graph.c = { d: 5, e: 2 };
graph.d = { f: 2 };
graph.e = { f: 1 };
graph.f = { g: 1 };
graph.g = {};
function shortPath(graph, start, end) {
// 1) --------------------------------------------------
// costs - объект где мы будем хранить кратчайшие пути
const costs = {};
// массив, в который мы будем добавлять те узлы, которые мы уже проверили
const processed = [];
// neighbors - тут храним соседние вершины рассматриваемого узла
let neighbors = {};
// Мы должны заполнить таблицу, заполнить те вершины в которые мы можем добраться из
// стартовой точки значениями, а все остальные мы должны заполнить бесконечно каким-то большим
// числом.
// Поэтому у нашего графа получаем список ключей(это будут все вершины) и итерируемся по ним.
Object.keys(graph).forEach((node) => {
// Если текущий элемент итерации, то есть вершина не равна стартовой, то
// мы будем заполнять значения. То есть стартовая вершина в эту табличку не добавляется.
if (node !== start) {
// Получаем значение (вес) вершины либо B либо C
let value = graph[start][node];
// Затем это значение добавляем в табличку, в которой будут храниться значения кратчайших путей
costs[node] = value || 100000000;
}
});
// 3) --------------------------------------------------
// Получаем объект с минимальной стоимостью
let node = findNodeLowestCost(costs, processed);
// Делаем цикл while, в котором будем крутиться до тех пор, пока эта нода не пустая.
//
while (node) {
// На кажой итерации получаем стоимость текущей вершины
const cost = costs[node];
// Те узлы в которые мы можем попасть из этой вершины мы присваиваем в neighbors
neighbors = graph[node];
Object.keys(neighbors).forEach((neighbor) => {
// Высчитываем новую стоимость
let newCost = cost + neighbors[neighbor];
//Перезаписываем в таблице значение если новая стоимость меньше
if (newCost < costs[neighbor]) {
costs[neighbor] = newCost;
}
});
// Добавляем вершину в массив уже обработанных вершин, после чего при поиске вершин с минимальной
// стоимостью эта вершина уже учитываться не будет.
processed.push(node);
// И ищем новую вершину.
node = findNodeLowestCost(costs, processed);
}
// Возврашаем объект, который хранит самые кратчайшие пути.
return costs;
}
// 2) --------------------------------------------------
// На этом этапе необходимо найти вершину, в которую мы можем попасть из точки A
// и путь в которую самый короткий. Название ф-ии "Найти узел с минимальной стоимостью"
function findNodeLowestCost(costs, processed) {
// lowestCost - будет хранить минимальное значение, по умолчанию 100000000
let lowestCost = 100000000;
// lowestNode - нода, которую мы будем возвращать с минимальным значением
let lowestNode;
// Теперь необходимо проитерироваться по ключам объекта в котором мы храним стоимость путей.
Object.keys(costs).forEach((node) => {
// Получим стоимость текущей ноды
let cost = costs[node];
// Если стоимость, которую мы получили меньше чем минимальная стоимость, которую мы определили в самом начале
// и вершина которую мы рассматриваем на текущей итерации не находится в массиве обработанных вершин.
// То есть мы сравниваем стоимость - если она меншьше и если узел еще не обработан, то мы обновляем переменные.
if (cost < lowestCost && !processed.includes(node)) {
// Если условие выполнилось, то мы нашли объект у которого путь короче.
// Соотвественно мы перезаписываем минимальную стоимость на ту, которую мы сейчас нашли на этой итерации
// и заменяем ноду.
lowestCost = cost;
lowestNode = node;
}
});
// Возврашаем вершину с минимальной стоимостью.
return lowestNode;
}
console.log(shortPath(graph, "a", "g"));
// Задача посчитать сумму значений всех узлов
// v - значение, с - потомки
// Если у узла нету потомков, то его называют "листом"
const tree = [
{
v: 5,
c: [
{
v: 5,
},
{
v: 10,
c: [
{
v: 11,
},
],
},
{
v: 11,
c: [
{
v: 12,
c: [
{
v: 5,
},
],
},
],
},
],
},
{
v: 5,
c: [
{
v: 7,
},
{
v: 12,
c: [
{
v: 11,
},
],
},
{
v: 14,
},
],
},
];
// Суть: для реализации с помощью итерации нужна структура данных - СТЕК.
// Стек похож на очередь, но работает по другому. Элементы всегда добавляются в конец структуры и извлекаются
// также из конца. В очереди добавляем в конец, а извлекаем из начала, то в стеке мы добавляем и извлекаем с конца.
function treeSum(tree) {
if (!tree.length) {
return 0;
}
let sum = 0;
// Создаем структуру данных стек, в которую будем записывать узлы.
let stack = [];
// Добавляем вершины дерева в стек
tree.forEach((node) => stack.push(node));
while (stack.length) {
let node = stack.pop();
sum += node.v;
if (node.c) {
node.c.forEach((n) => stack.push(n));
}
}
return sum;
}
console.log(treeSum(tree));
// Рекурсивный вариант
function recursiveTreeSum(tree) {
let sum = 0;
tree.forEach((node) => {
sum += node.v;
if (!node.c) {
return node.v;
}
sum += recursiveTreeSum(node.c);
});
return sum;
}
console.log(recursiveTreeSum(tree));// Алгоритм кеширования данных во избижании повторных вычеслений
// cashFunction - ф-ия которая кеширует внутри себя результат вычесления другой ф-ии fn
function cashFunction(fn) {
// Объект, который хранит по ключу результат кеширования, ключем будет параметр n который мы передаем в fn
const cash = {};
return (n) => {
if (cash[n]) {
console.log("Выведено из кеша: ", cash[n]);
return cash[n];
}
let result = fn(n);
cash[n] = result;
console.log("Выведено не из кеша: ", cash[n]);
return result;
};
}
// Допустим ф-ия факториала очень тяжелая, а мы не хотим трать лишние ресурсы, поэтому кешируем вычесления и выдаем их.
function factorial(n) {
let result = 1;
while (n != 1) {
result *= n;
n -= 1;
}
return result;
}
const cashFactorial = cashFunction(factorial);
cashFactorial(5);
cashFactorial(4);
cashFactorial(3);
cashFactorial(4);
cashFactorial(5);
cashFactorial(1);
// Структура данных: Связанный список (Linked List)
// Связанный список - каждый отдельно взятый элемент списка занимает отдельное место в памяти.
// Связанность списка происходит за счет того, что каждый пердыдущий элемент хранит ссылку на следующий элемент,
// который лежит в списке. Плюс такого подхода в том, что мы можем мгновенно добавлять элементы в конец или в начало
// списка. А минус в том, что чтобы получить какой-то элемент - нам с самого начала списка надо итерироваться и сравнивать.
// Таким образом список больше подходит в том случае если мы редко обращаемся к каким-то данным и часто его дополняем.
// Суть: каждый предыдущий элемент ссылается на последующий
class LinkedList {
constructor() {
// Размер самого списка
this.size = 0;
//Корневой элемент
this.root = null;
}
add(value) {
if (this.size === 0) {
// Если размер равен 0 тогда создаем корневой элемент
this.root = new Node(value);
this.size += 1;
// Прекращаем выполнение ф-ии
return true;
}
let node = this.root;
// Крутимся в цикле до тех пор пока в ноде есть следующий жоемент
while (node.next) {
// Присваеваем следующий элемент переменной node
node = node.next;
}
// После того как дошли до последнего элемента в списке, создаем новую ноду
let newNode = new Node(value);
// Указываем ссылку на новую ноду последнему элементу
node.next = newNode;
this.size += 1;
}
getSize() {
return this.size;
}
print() {
let result = [];
let node = this.root;
while (node) {
result.push(node.value);
node = node.next;
}
console.log(result);
}
}
// Класс для отдельного узла
class Node {
constructor(value) {
this.value = value;
// Будет хранить ссылку на следующий элемент в списке
this.next = null;
}
}
const list = new LinkedList();
list.add(5);
list.add(3);
list.add(2);
list.add(5);
list.add(7);
list.print();
// Структура данных: Бинарное дерево (Binary Tree)
// Бинарное дерево - это структура данных, где каждый узел также является деревом, то есть структура рекурсивная,
// и основная суть в том, что у каждого узла может быть 2 потомка.
// Добавляются эти узлы тоже особым способом: если добавляемое в дерево значение меньше по значению чем текущий угол,
// то значение уходит в левое поддерево, если больше, то уходит в правое. И так получается, что правая часть поддерева выстраивается с большими
// значениями, а левая с меньшими. И это дерево называется бинарным деревом поиска, поскольку аналогично бинарному алгоритму поиска
// здесь можно находить данные за логарифмическое время.
class BinaryTree {
constructor() {
this.root = null;
}
add(value) {
// Если корневой элемент не существует, тогда необходимо его проинициализировать.
if (!this.root) {
this.root = new TreeNode(value);
} else {
let node = this.root;
let newNode = new TreeNode(value);
// Крутимся пока node не равен пустому значанию
while (node) {
// Если значение больше чем значение ноды, то мы уйдем в правое поддерево, в обратном случае уйдем в левое поддерево
if (value > node.value) {
// Если правого поддерева нет, то остановим цикл
if (!node.right) {
break;
}
node = node.right;
} else {
if (!node.left) {
break;
}
node = node.left;
}
}
// Таким образом после цикла мы имеем ноду которая находится в самом низу цикла
// Опять делаем проверку значения
if (value > node.value) {
node.right = newNode;
} else {
node.left = newNode;
}
}
}
// Рекурсивная ф-ия print
print(root = this.root) {
// Любая рекурсивная ф-ия должна иметь условия выхода из этой рекурсии
if (!root) {
return true;
}
console.log(root.value);
this.print(root.left);
this.print(root.right);
}
}
// Создаем узела
class TreeNode {
constructor(value) {
this.value = value;
// Создаем ссылку на элемент кторый находится в левой части дерева
this.left = null;
// Создаем ссылку на элемент кторый находится в правой части дерева
this.right = null;
}
}
const tree = new BinaryTree();
tree.add(5);
tree.add(2);
tree.add(6);
tree.add(2);
tree.add(1);
tree.print();
// Структура данных: Map. Cловарь, карта или map, называют по разному. Хранит в себе пары ключ-значение. По сути обычный объект в js
// уже является map.Основное преимущество структуры в том, что мы можем за константное(мгновенное) время добавлять объекты в структуру
// и извлекать.
// Структура данных: Set. Set - это некое множество, своего рода массив, который хранит в себе только уникальные значения.