16.3 Глоссарий¶
В таблице 16-1 перечислены важные термины, встречающиеся в книге. Обратите внимание на следующие моменты.
- Рекомендуем запомнить английские названия терминов, чтобы легче читать англоязычную литературу.
- В русской версии приводится единый рекомендуемый перевод каждого термина.
Таблица 16-1 Важные термины по структурам данных и алгоритмам
| English | Русский |
|---|---|
| algorithm | алгоритм |
| data structure | структура данных |
| code | код |
| file | файл |
| function | функция |
| method | метод |
| variable | переменная |
| asymptotic complexity analysis | асимптотический анализ сложности |
| time complexity | временная сложность |
| space complexity | пространственная сложность |
| loop | цикл |
| iteration | итерация |
| recursion | рекурсия |
| tail recursion | хвостовая рекурсия |
| recursion tree | дерево рекурсии |
| big-\(O\) notation | нотация big-\(O\) |
| asymptotic upper bound | асимптотическая верхняя граница |
| sign-magnitude | прямой код |
| 1’s complement | обратный код |
| 2’s complement | дополнительный код |
| array | массив |
| index | индекс |
| linked list | связный список |
| linked list node, list node | узел связного списка |
| head node | головной узел |
| tail node | хвостовой узел |
| list | список |
| dynamic array | динамический массив |
| hard disk | жесткий диск |
| random-access memory (RAM) | оперативная память |
| cache memory | кеш-память |
| cache miss | промах кеша |
| cache hit rate | коэффициент попадания в кеш |
| stack | стек |
| top of the stack | вершина стека |
| bottom of the stack | основание стека |
| queue | очередь |
| double-ended queue | двусторонняя очередь |
| front of the queue | голова очереди |
| rear of the queue | хвост очереди |
| hash table | хеш-таблица |
| hash set | хеш-набор |
| bucket | корзина |
| hash function | хеш-функция |
| hash collision | хеш-коллизия |
| load factor | коэффициент заполнения |
| separate chaining | цепная адресация |
| open addressing | открытая адресация |
| linear probing | линейное зондирование |
| lazy deletion | ленивое удаление |
| binary tree | двоичное дерево |
| tree node | узел дерева |
| left-child node | левый дочерний узел |
| right-child node | правый дочерний узел |
| parent node | родительский узел |
| left subtree | левое поддерево |
| right subtree | правое поддерево |
| root node | корневой узел |
| leaf node | листовой узел |
| edge | ребро |
| level | уровень |
| degree | степень |
| height | высота |
| depth | глубина |
| perfect binary tree | идеальное двоичное дерево |
| complete binary tree | совершенное двоичное дерево |
| full binary tree | полное двоичное дерево |
| balanced binary tree | сбалансированное двоичное дерево |
| binary search tree | двоичное дерево поиска |
| AVL tree | АВЛ-дерево |
| red-black tree | красно-черное дерево |
| level-order traversal | обход по уровням |
| breadth-first traversal | обход в ширину |
| depth-first traversal | обход в глубину |
| binary search tree | двоичное дерево поиска |
| balanced binary search tree | сбалансированное двоичное дерево поиска |
| balance factor | фактор баланса |
| heap | куча |
| max heap | максимальная куча |
| min heap | минимальная куча |
| priority queue | приоритетная очередь |
| heapify | упорядочивание кучи |
| top-\(k\) problem | поиск \(k\) наибольших элементов |
| graph | граф |
| vertex | вершина |
| undirected graph | неориентированный граф |
| directed graph | ориентированный граф |
| connected graph | связный граф |
| disconnected graph | несвязный граф |
| weighted graph | взвешенный граф |
| adjacency | смежность |
| path | путь |
| in-degree | входящая степень |
| out-degree | исходящая степень |
| adjacency matrix | матрица смежности |
| adjacency list | список смежности |
| breadth-first search | поиск в ширину |
| depth-first search | поиск в глубину |
| binary search | двоичный поиск |
| searching algorithm | алгоритм поиска |
| sorting algorithm | алгоритм сортировки |
| selection sort | сортировка выбором |
| bubble sort | сортировка пузырьком |
| insertion sort | сортировка вставкой |
| quick sort | быстрая сортировка |
| merge sort | сортировка слиянием |
| heap sort | пирамидальная сортировка |
| bucket sort | блочная сортировка |
| counting sort | сортировка подсчетом |
| radix sort | поразрядная сортировка |
| divide and conquer | разделяй и властвуй |
| hanota problem | задача о Ханойской башне |
| backtracking algorithm | алгоритм поиска с возвратом |
| constraint | ограничение |
| solution | решение |
| state | состояние |
| pruning | отсечение |
| permutations problem | задача о перестановках |
| subset-sum problem | задача о сумме подмножеств |
| \(n\)-queens problem | задача о \(n\) ферзях |
| dynamic programming | динамическое программирование |
| initial state | начальное состояние |
| state-transition equation | уравнение перехода состояния |
| knapsack problem | задача о рюкзаке |
| edit distance problem | задача о расстоянии редактирования |
| greedy algorithm | жадный алгоритм |