Data structures Flashcards
Типы структур
- Массив Array
- Список Linked list
- Стек Stack
- Очередь Queue
- Хеш-таблица Hash table
- Коллекция значений Set
- Бинарное дерево Binary search tree (BST)
- Нагруженное (префиксное) дерево
- Граф (график) Graph
Выбор структуры данных зависит от конкретной задачи: от вида данных и алгоритма их обработки. Разнообразные структуры данных создавались под определенные типы алгоритмов.
Массив Array
Упорядоченный набор элементов, к каждому можно обратиться по индексу.
Оптимален для получения элемента по его индексу.
Плох для поиска, вставки, удаления, если не в конце.
Эффективность:
Индексирование: О(1)
Поиск: О(n)
Двоичный поиск: О(log n)
Вставка: недопустимо
Список (связный список) Linked list
Данные хранятся в узлах, указывающих на другие узлы. Выглядит как вложенные друг в друга объекты. У каждого узла есть value (значение этого элемента) и nextNode (ссылка на следующий элемент связанного списка).
Оптимален для вставки и удаления.
Плох для индексирования и поиска (из-за вложенности).
Двусвязный список также имеет previousNode.
Эффективность:
Индексирование: О(n)
Поиск: О(n)
Двоичный поиск: О(n)
Вставка: О(1)
Стек (вызовов) Stack
LIFO - last in, first out
Аналог - колода карт.
Голова - единственное место вставки и удаления элементов.
Может быть реализован с помощью связного списка или массива.
Эффективность:
Индексирование: О(n)
Поиск: О(n)
Двоичный поиск: О(n)
Вставка: О(1)
function Stack() {
this.count = 0
this.storage = {}
this.push = function(value) {
this.storage[this.count] = value
this.count++
}
this.pop = function() {
if (this.count === 0) return undefined
this.count--
let result = this.storage[this.count]
delete this.storage[this.count]
return result
}
this.peek = function() {
return this.storage[this.count - 1]
}
this.size = function() {
return this.count
} }
Очередь Queue
FIFO - first in, first out
Аналог - очередь в магазине.
Элементы удаляются из головы, добавляются в хвост.
Также может быть реализована связным списком или массивом.
Эффективность:
Индексирование: О(n)
Поиск: О(n)
Двоичный поиск: О(n)
Вставка: О(1)
Хеш-таблица Hash table
Это структура данных, которая строится по принципу ключ-значение. Из-за высокой скорости поиска значений по ключам, она используется в таких структурах, как Map, Dictionary и Object.
Одинаковые ключи должны возвращать одинаковые значения — в этом суть функции хэширования.
Эффективность:
Индексирование: О(1)
Поиск: О(1)
Вставка: О(1)
Коллекция значений Set
Коллекция (множество) — одна из основных концепций математики: набор хорошо определенных и обособленных объектов. ES6 представил коллекцию, которая имеет некоторое сходство с массивом. Тем не менее, коллекция не допускает включения повторяющихся элементов и не содержит индексов.
Бинарное дерево
Binary search tree (BST)
Структура, в которой каждый узел имеет максимум 2 дочерних элемента. Дочерние элементы могут быть правыми (ключ больше, чем у родителя) и левыми (ключ меньше, чем у родителя).
Оптимально для сортировки и поиска.
Эффективность:
Индексирование: О(log n)
Поиск: О(log n)
Вставка: О(log n)
Дерево может быть и не двоичным, тогда у узлов потомков больше, чем 2.
- root: корневой элемент, не имеет «родителя»
- parent node: прямой узел верхнего слоя (уровня), может быть только одним
- child node: прямой узел (узлы) нижнего уровня, может быть несколько
- siblings: дочерние элементы одного родительского узла
- leaf: узел без «детей»
- Edge: ветка или ссылка (связь) между узлами
- Path: путь (совокупность ссылок) от начального узла до целевого элемента
- Height of Tree (высота дерева): количество ссылок самого длинного пути от определенного элемента до узла, не имеющего потомков
- Depth of Node (глубина узла): количество ссылок от корневого узла до определенного элемента
- Degree of Node: количество потомков
Нагруженное (префиксное) дерево
Префиксное дерево — это разновидность поискового дерева. Данные в нем сохраняются последовательно (шаг за шагом) — каждый узел дерева представляет собой один шаг. Префиксное дерево используется в словарях, поскольку существенно ускоряет поиск.
Каждый узел дерева — буква алфавита, следование по ветке приводит к формированию слова. Оно также содержит «булевый индикатор» для определения того, что текущий узел является последней буквой.
Граф (график) Graph
Граф, также известный как сеть (Network), представляет собой коллекцию связанных между собой узлов. Бывает два вида графов — ориентированный и неориентированный, в зависимости от того, имеют ли ссылки направление.
Графы используются повсеместно, например, для расчета наилучшего маршрута в навигационных приложениях или для формирования списка рекомендаций в социальных сетях.
Графы могут быть представлены в виде списка или матрицы.
Список
В данном случае все родительские узлы располагаются слева, а их дочерние элементы справа.
Матрица
В данном случае узлы распределяются по строкам и столбцам, пересечение строки и столбца показывает отношение между узлами: 0 означает, что узлы не связаны между собой, 1 — узлы связаны.
Big O
Big O нотация нужна для описания сложности алгоритмов. Это мера эффективности «в худшем случае», верхняя граница того, сколько времени потребуется для выполнения задачи, или сколько памяти для этого необходимо.
В Big O нотации фактическое кол-во шагов не важно, важно что алгоритм выполняется за константное время.
Алгоритмы с константным временем это всегда O(1)
O(1) - нужна 1 операция для всех возможных вводных данных в выбранном типе структуры.
О(1) можно прочитать как «сложность порядка 1» (order 1), или «алгоритм выполняется за постоянное/константное время» (constant time).
Это самые эффективные алгоритмы.
O(n) - нужно n операций, где n это количество элементов в структуре данных.
O(n), или «сложность порядка n (order n)». Так же такой тип алгоритмов называют «линейными» или что алгоритм «линейно масштабируется».
O(n^2) - алгоритмы с двойной итерацией (вложенные циклы). «Сложность порядка n квадрат» - не самое лучшее решение.
O(log n) - алгоритмы «разделяй и влавствуй» Divide and Conquer, пример - бинарный поиск. Такие алгоритмы основаны на логарифмах. В худшем случае делаем столько операций, сколько раз можем разделить массив на две части.
O(n log n) - например, при замене вложенного цикла на бинарный поиск у нас меняется второе n на log n. Т.е. у нас остается перебор всех элементов O(n), внутри делаем O(log n). Получается O(n log n).
Мышление в терминах Big O
- Получение элемента коллекции это O(1). Будь то получение по индексу в массиве, или по ключу в словаре в нотации Big O это будет O(1)
- Перебор коллекции это O(n)
- Вложенные циклы по той же коллекции это O(n^2)
- Разделяй и властвуй (Divide and Conquer) всегда O(log n)
- Итерации которые используют Divide and Conquer это O(n log n)
