【算法1】基础+贪心
Big-O
算法复杂度。用来度量算法。
数据结构
Vector & Array
查找很快,但增删很难。
List & Linked List
增删很简单,但查找不方便。
Stack
push, pop.
Queue
enqueue, dequeue.
(Binary) Tree
树。二叉树。
Graph as Matrix
无向图(undigraph)、有向图(digraph)、有权重的图(network)。
Graph as Vector
好处:空间上节省。
坏处:查找有时间损耗。
排序
Gnome sort
for( int i = 1; i <= n; ; ){
if ( i < 1 || S[i-1] <= S[i] ) {
++i;
}else{
swap(S[i-1], S[i]);
--i;
}
}
条件判断中 i < 1
是为了确保反向时候的停止, 比如 S[i]
应当是在最前面的情况。同样条件放在前面,是因为防止i = 0 时,后面条件的数组越界。
时间效率:$O(n^2)$
Bubblesort
改进:
- 提前终止。
- 省略无效气泡。
Matrix Sorting
先列排序后行排序,最后列还是符合排序的。
Huffman : PFC Coding
霍夫曼编码。(贪心)
- Unweighted?
- Weighted?
从叶子开始构造。一直找两个最低的进行插叶子合并。