mirror of
https://github.com/krahets/hello-algo.git
synced 2026-07-04 11:44:21 +00:00
krahets
133 lines
14 KiB
Markdown
133 lines
14 KiB
Markdown
# Глоссарий
|
|
|
|
В табл. 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 | обозначение «О» большое |
|
|
| 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 | узел дерева |
|
|
| root node | корневой узел |
|
|
| leaf node | листовой узел |
|
|
| parent node | родительский узел |
|
|
| left-child node | левый дочерний узел |
|
|
| right-child node | правый дочерний узел |
|
|
| left subtree | левое поддерево |
|
|
| right subtree | правое поддерево |
|
|
| level | уровень |
|
|
| degree | степень |
|
|
| height | высота |
|
|
| depth | глубина |
|
|
| perfect binary tree | идеальное двоичное дерево |
|
|
| complete binary tree | совершенное двоичное дерево |
|
|
| full binary tree | полное двоичное дерево |
|
|
| balanced binary tree | сбалансированное двоичное дерево |
|
|
| binary search tree | двоичное дерево поиска |
|
|
| balanced binary search tree | сбалансированное двоичное дерево поиска |
|
|
| AVL tree | АВЛ-дерево |
|
|
| red-black tree | красно-черное дерево |
|
|
| level-order traversal | обход по уровням |
|
|
| breadth-first traversal | обход в ширину |
|
|
| depth-first traversal | обход в глубину |
|
|
| 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 | жадный алгоритм |
|
|
| graph | граф |
|
|
| vertex | вершина |
|
|
| edge | ребро |
|
|
| adjacency | смежность |
|
|
| path | путь |
|
|
| in-degree | входящая степень |
|
|
| out-degree | исходящая степень |
|
|
| undirected graph | неориентированный граф |
|
|
| directed graph | ориентированный граф |
|
|
| connected graph | связный граф |
|
|
| disconnected graph | несвязный граф |
|
|
| weighted graph | взвешенный граф |
|
|
| adjacency matrix | матрица смежности |
|
|
| adjacency list | список смежности |
|
|
| breadth-first search | поиск в ширину |
|
|
| depth-first search | поиск в глубину |
|
|
| heap | куча |
|
|
| min heap | минимальная куча |
|
|
| max heap | максимальная куча |
|
|
| priority queue | приоритетная очередь |
|
|
| heapify | упорядочивание кучи |
|
|
| top-k problem | поиск k наибольших элементов |
|
|
| balance factor | фактор баланса | |