跳轉至

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 \(O\) 记号 \(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 哈希表 雜湊表
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 AVL 树 AVL 樹
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 Top-\(k\) 问题 Top-\(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\) 皇后问题 \(n\) 皇后問題
dynamic programming 动态规划 動態規劃
initial state 初始状态 初始狀態
state-transition equation 状态转移方程 狀態轉移方程
knapsack problem 背包问题 背包問題
edit distance problem 编辑距离问题 編輯距離問題
greedy algorithm 贪心算法 貪婪演算法