云昴

【算法1】基础+贪心

| | 【专业·学习】算法

Big-O

算法复杂度。用来度量算法。

数据结构

Vector & Array

查找很快,但增删很难。

List & Linked List

增删很简单,但查找不方便。

Stack

push, pop.

Queue

enqueue, dequeue.

(Binary) Tree

树。二叉树。

Graph as Matrix

无向图(undigraph)、有向图(digraph)、有权重的图(network)。

无向图 undigraph

Graph as Vector

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

改进:

  1. 提前终止。
  2. 省略无效气泡。

Matrix Sorting

Matrix Sorting

先列排序后行排序,最后列还是符合排序的。

Huffman : PFC Coding

霍夫曼编码。(贪心)

PFC Coding

  • Unweighted?
  • Weighted?

Weighted Optimal

从叶子开始构造。一直找两个最低的进行插叶子合并。

云昴