思维之海

——在云端,寻找我的星匙。

数据结构复习

数据结构。决定将这个博文写作复习之用。本文章更针对912复习之用。

这个文章将逐步更新邓公在课堂上并未详述或者912考试中容易出现的重难点知识。

References

数据结构1 , 数据结构2 可在课程中获取教材习题集

DSACPP

算法1 , 算法2, 算法可视化

Preface

有哪些常用的数据结构?

  • 向量,列表
  • 栈,队列
  • 二叉树,BBST
  • 散列表
  • ……

如何学习数据结构?

第一步 看邓俊辉老师的MOOC

第二步 做习题集

第三步 历年真题 & 深入思考

第四步 复习笔记

旧笔记

绪论

计算机科学(Computer Science)不妨称作计算科学(Computing Science)。

计算机

只要有一个具有规则的系统,就存在一个计算机。

绳索计算机

利用勾股三角形来计算直角。

尺规计算机

利用欧式几何原理来计算三等分。

起泡排序 bubblesort $O(n^2)\longrightarrow O(n)$

有序覆盖定理局部有序覆盖整体有序等价。

特殊情况,所有元素相邻有序构成有序覆盖,推出序列整体也有序。(根据此定理可提前退出)

1
2
3
4
5
6
7
8
9
10
11
void bubblesort(vector<int> &A, int n){
bool sorted = false;
while( !sorted ){
sorted = true; //assertion to break quickly
for(int i = 1; i < n; ++i){
if( A[i - 1] > A[i]) //greater
swap(A[i - 1], A[i]), sorted = false;
}
n--; // reduce elements
}
}

算法

输入、输出:算法的起点和终点。

基本操作:算法的最小操作单元。

确定性:算法的序列对于同样的输入输出是稳定的。

有穷性:从起点到终点只需有限步。

正确性:起点和终点基于现实构成因果。

不变性:算法执行过程中某类中间事件必然发生。

单调性:问题的有效规模不断递减。

鲁棒性:对边界问题的处理。(退化,degeneracy)

重用性:算法的泛化能力。

可计算性;computability,就大量应用问题而言,根本不可能设计出必然终止的算法。

难解性:intractability,计算时间成本过高。

计算效率:控制算法的时空消耗。

数据结构要做到根据实际应用需求自如设计、实现和选用适当的数据结构,必须先对算法设计和数据结构了然于心

复杂度

输入规模:用以描述输入所需的空间规模。

递归

线性递归:减而治之。

递归分析

  • 递归跟踪(计算图)
  • 递推方程(代数法)