Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algorithms and Data Structures - Coggle Diagram
Algorithms and Data Structures
Time complexity
Big O Notation
Арифметические операции - константа
Присваивание переменной - константа
Обращение к элементу в массиве по индексу или в объекте по ключу - константа
В цикле сложностью является то, что происходит внутри цикла, умноженное на количество.
Space complexity
Как улучшить навыки?
Определите план для решения задачи
Изучите общие паттерны в решении задач
Начните с простых примеров
Продолжайте с более сложными примерами
Изучите примеры с пустыми входными данными
Изучите примеры с невалидными входными данными
Паттерны
Divide and Conquer
- этот паттерн предполагает разделение набора данных на более мелкие наборы и затем повторение процесса с подмножествами данных. Может сильно снизить временную сложность.
Двоичный поиск
Frequency counters
- счетчик частоты
Создать объект, который в виде ключа / значения запишет искомые вхождения
Multiple Pointer
- множественный указатель
Sliding Window
- скользящее окно - этот паттерн предполагает создание окна, которое может быть либо массивом, либо расстоянием от одной позиции до другой. В зависимости от определенного условия окно либо увеличивается, либо закрывается и тогда создается новое окно. Очень полезно для поиска подмножества в массиве или строке.
findLongestSubstring
- возникли трудности со скользящим окном
Recursion
Helper Method Recursion
- основная функция, внутри которой вспомогательная рекурсивная функция.
Pure Recursion
- только рекурсивная функция без дополнительных структур данных.
Решить задачу 39, практиковать скользящее окно min_subarray_length
задача 52 - не смогла сделать фибоначу
решить усложненные задачи по рекурсии -
Тарас
отказался их решать
** Алгоритм Кнутта-Морриса-Пратта для поиска подстроки
Как работает гарбедж коллектор
написать разворот связного списка!
Рекурсия
Процесс, который вызывает сам себя
call stack (стек вызовов) - структура данных. Каждый раз, когда вызывается функция, она помещается на верх стека вызовов. Когда JavaScript видит слово return или функция заканчивается, компилятор убирает функцию из стека вызовов.
Следить за тем, чтоб всегда был базовый случай, иначе стек вызовов может переполниться
Поиск
Linear Search - просто последовательно перебираем значения. O(n)
Binary Search
Поиск подстроки:
Наивный поиск O(n*k)
КМП (Кнутт-Моррис-Пратт) алгоритм
Сортировка
Процесс перестановки элементов в коллекции, например, в массиве, так, чтоб элементы были в определенном порядке.
Встроенный
arr.sort()
Базовые
Bubble Sort
Optimized Bubble Sort - тоже самое, но есть счетчик, который хранит, были ли перестановки во внутреннем цикле.
Selection Sort - запоминаем индекс первого элемента Проходим двумя циклами, если значение меньше, то меняем местами.
Insertion Sort - проходим циклом, начиная со второго элемента. Создаем цикл внутри. Если текущее значение меньше, чем предыдущее, меняем предыдущее на текущее.
Продвинутый
Есть алгоритмы, которые могут улучшить сложность с n2 до n*log(n)
Merge Sort
Quick Sort
Radix Sort
Data Structure
Single Linked List - односвязный список
Структура, которая содержит head, tail и length свойства.
Односвязный список состоит из узлов (nodes) и каждый узел имеет value и указатель (pointer) на другой узел или null
Сравнение с массивом
Список
не имеет индексов
узлы связаны при помощи указателя на следующий узел
случайный доступ невозможен
Массив
упорядочены при помощи индексов
Вставка и удаление - дорогостоящие операции
Возможен быстрый доступ по индексу
Big O Single Linked List
push - O(1)
pop - O(1)
shift - O(1)
unshift - O(1)
insert - O(n)
remove - O(n)
set - O(n)
get - O(n)
reverse - O(n)
Big O Doubly Linked Linst
push - O(1)
pop - O(1)
shift - O(1)
unshift - O(1)
insert - O(n)
remove - O(n)
get - O(n)
set - O(n)
reverse - O(1)
Big O of Stack
insert O(1)
removal O(1)
search - O(n)
access - O(n)
Big O of Stack
insert O(1)
remove O(1)
search O(n)
access O(n)
Big O of Binary Tree
Insert - O(log n)
Search - O(log n)
Big O of Binary Heap
Insert - O(log n)
Remove- O(log n)
Search - O(n)
Big O of Hash Table
Insert - O(1)
Access - O(1)
Remove - O(1)
Big O Adjacency matrix
V - количество вершин
E - количество ребер
Add Vertex - O(1)
Add edge - O(1)
Remove Vertex - O(|V| + |E|)
Remove Edge - O( |E|)
Query - O(|V| + |E|)
Storage - O(|V| + |E|)
Big O List matrix
Add Vertex - O(|V^2|)
Add edge - O(1)
Remove Vertex - O(|V^2|)
Remove Edge - O(1)
Query - O(1)
Storage - O(V^2)
Doubly Linked List - двусвязный список
Структура, которая содержит head, tail и length свойства.
Односвязный список состоит из узлов (nodes) и каждый узел имеет value и указатель (pointer) на следующий и предыдущий узлы или null
Stack - стэк
Коллекция данных. Последний элемент, добавленный в стек, будет первым элементом, который удален из стека
Как используется стек:
управление вызовом функций
undo/redo
роутинг
Есть несколько способов имплементации
массив - самый простой
Queue
FIFO - Fisrt in - first out
Использование:
фоновые задачи
загрузка ресурсов
вывод / обработка задач
Tree
Root - top node of tree
child
parent
sibling
leaf - узел без дочерних узлов
edge - ребро - соединение между одним и другим узлом
Использование:
HTML DOM
Интернет роутинг
Абстрактное синтаксическое дерево
Искусственный интеллект
Файловая система
Виды
Деревья
Бинарное дерево
Дерево Бинарного поиска
Tree Traversal
- обход дерева
Breadth First Search - поиск в ширину
Depth First Search - поиск в глубину
In order
PreOrder
PostOrder
Binary Heap
Очень похоже на BinarySearchTree, но с несколькими отличными правилами!
в MaxBinaryHeap - родитель всегда больше чем ребенок
в MinBinaryHeap - родитель всегда меньше чем ребенок
Priority Queue
Структура данных, где каждый элемент имеет приоритет
Элементы с более высоким приоритетом обслуживаются раньше.
Hash Table
Используется, чтоб хранить ключ-значения.
Похожи на массив, но ключи не упорядочены
Вставка, удаления, быстрые
Graph
Структура данных, состоящая из конечного (и возможно мутабельного) набора вершин, узлов или точек, совместно с набором неупорядоченных пар этих вершин для ненаправленного графа или набор упорядоченных пар для направленного графа.
Vertex - вершина - узел
Edge (ребро) - соединение между вершинами.
Undirected Graph
Directed Graph
Weighted Graph
- ребра имеют вес
Алгоритм Дейкстры