计算机领域常见英语名词总结
需积分: 0 181 浏览量
2023-09-24
19:59:57
上传
评论
收藏 267KB PDF 举报
1. 二叉查找树 (Binary search tree)[logn]: 左子树上的所有结点小于根节点小于右子树，插入的结点一定是叶
结点。
2. 红黑树 (Red-black tree)[logn]: 特殊的二叉查找树，接近平衡二叉树，2倍，1.红黑2.根节点黑色3.叶子结点
黑色4. 结点红色，则子节点必须黑色5.路径上的黑结点数相同。
3. 平衡二叉查找树(Balanced binary search tree)[logn]: AVL, degeneration(有序), 结点的左右子树高度高度差不
超过1. 左旋，右旋以平衡。(特殊: 先左旋后右旋，或者反之)
4. B 树 (Btree)[mlog_m^n]: 平衡多路查找树 balanced multi-way search tree,2-3和2-3-4是特例。m阶表示最多
m个子节点。更矮为内外存数据交互，减少访存次数。B树是将各种信息保存在所有节点中的。B+树是将
各种信息保存在叶子中的。所有叶子结点都位于同一层。m/2-1~m-1个key。以结点中间的key分裂并上移。
5. B+树[O(logN)]: 关键字数=子结点数, 添加子结点之间的连接。m/2*log(m)n=log(m^1/m)n=logn, 对于n来说，
m是常数。层级更低，因为只存储最大值,IO次数更少; 每次都会查到叶子结点，更稳定; 叶子结点形成有
序链表，范围查询更方便，减少内存跳跃。
6. 2-3树，
2-3-4树[O(log_3/4^n)~O(logn)]: 每个中间结点都有2-3或者2-3-4个子结点。插入需要升级父结点。
7. 堆 (heap)[建堆O(n), 调整O(logn)]: 节点不大于或者不小于父结点的值。使用向上调整策略创建堆（只需将
子结点中较大的那个和父结点比较）。
8. 冒泡排序(bubble sort)[O(n^2)]: 比较相邻元素，交换位置, 类似选择排序, 后者不需要额外的交换位置
9. 插入排序(insertion sort)[O(n^2)]: 不断比较未排序部分的第一个与排序部分的内容，插入到合适位置，费
时在交换位置。与冒泡排序不同于不需要找到最大值，只需要找到合适位置即可。
10. 希尔排序(shell sort)[O(n^1.3)]: 一种插入排序，不过是进行了分组，利用分治思想，将数据按照gap分组
11. 选择排序(selection sort)[O(n^2)]: 从未排序部分选择最大的，放到排序部分的顺次的位置上。
12. 快速排序(quick sort)[O(nlogn)]: 选择一个pivot，以它为标准划分list，将小的放左边，大的放右边, 递归
地完成pivot两边的sublist（选择new pivot）
13. 归并排序(merge sort)[O(nlogn)]: 递归地将list分解到最小, merge and sort adjacent elements
14. 堆排序(heap sort)[O(nlogn)+O(n)]:
构建大顶堆，删除堆顶(heap top)，更新堆，进行迭代
15. 计数排序(counting sort)[O(n+k)]: 有确定范围的整数，设置一个counting list，以出现的数字为index的
elements进行计数
16. 基数排序(radix sort)[O(d(n+k))]: 按照位数places of the integer，完成计数排序，注意按照FIFO恢复数据
17. 桶排序(bucket sort)[O(n)+O(m*n/n*log(n/m))]: 使用function将数据map到k个桶中，每个桶按照comparison
method 排序
18. K路归并败者树(K-way merge loser tree)[O(N*logK)]: 应用于external sorting，只有叶子结点是数据，内部
节点是比赛的败者，使用胜者与下个进行比赛。根结点记录败者，额外的空间记录最终胜者。每个叶子结
点连接一个外部数据sequence (已经排序好的)，每个sequence最后数据是较大的。
19. 二分查找(binary search)[O(logn)]: 分治法，就是完全二叉查找树，需要有序的列表, 查中间点。
20. 大整数乘法(large integer multiplication)[O(n^log3)]: 分治法，二分两个integer，使用三个小规模乘法代替
原本的乘法
21. Strassen 矩阵乘法(Strassen matrix product)[O(n^log7)]: 分治法，四分两个matrix，使用七个小规模矩阵乘
法代替原本的乘法
22. 最接近点对(the planar closest pair)[
O(nlogn)]: 分治法，划分plane为两个部分，考虑左边、右边以及横跨
(cross)两个部分这三种情况
23. 最长公共子序列(the longest common subsequence)[O(mn)+O(m+n)]: 考虑两个小子段，两个的最后一个元
素相同则计数+1，否则考虑两个子段分别减1之后的common subsequence中的最长的那个，使用二维表完成
记录。动态规划需要找到1.目标: 价值、和等，2. 自变量: 容量、长度等，1随着2的变化而变化
24. 最大子段和(maximum interval sum)[O(n)]: Enumerate all intervals, 分治法包含三种情况(第三种的左部分以
中间节点结尾，右部分以中间节点开始)，动态规划生长interval，只是需要判断当前sum是否小于0，如果真
的话舍弃，从下一个重新sum，否则继续。dp[i] = max(dp[i−1] + num[i], num[i])
25. 背包问题(knapsack problem)[O(nC)]: 递归，放置后一个object会减少前一个物体的可行的容量，选择两者
中最大的那个作为当前的值(memory search)。动态规划，对于中间的任意一个物体状态转移方程(state
transition equation)与递归相同，自底向上直到容量为C
26. 计数问题(counting problem): 解决这个问题有多少种方法
27. 斐波那契数列(Fibonacci sequence)[O(n)]: f(N)=f(n-1)+f(n-2)，直接按照状态转移方程计算下一个数值
28. 凑零钱(Collect change)[O(n)]: f(x)=min{f(x-coin[1]), f(x-coin[2])…}+1，按照状态方程计算下一个目标钱
数
29.
爬楼梯(climb stairs)[O(n)]: f(x)=f(x-1)+f(x-2)，直接按照状态转移方程计算下一个阶梯数的可行方式
资源评论
