时间复杂度分析

MaxSubsequenceSum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int
MaxSubsequenceSum( const int A[], int N)
{
	int ThisSum, MaxSum, j;

	ThisSum = MaxSum = 0;
	for( j = 0; j<N;j++)
	{
		ThisSum += A[j];
	
		if (ThisSum>MaxSum)
		{
			MaxSum = ThisSum;
		}else{
			ThisSum = 0;
		}
	}
	return MaxSum;
	
}

表、栈和队列

  • 线性表的数组与链表实现
  • 基数排序与桶式排序

Radix Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def radix_sort(List):
bucket1=[[],[],[],[],[],[],[],[],[],[]]#不可以用[[]]*10
bucket2=[[],[],[],[],[],[],[],[],[],[]]
for i in List:
bucket1[i%10].append(i)
List1 = []
for num in bucket1:
	List1.extend(num)
for i in List1:
	bucket2[i//10].append(i)
List2=[]
for num in bucket2:
	List2.extend(num)
return List2
 
if__name__=='__main__':
List=[17,4,56,3,8,9,91,12,83,41,62]
print radix_sort(List)

Stack

Reverse Polish

  • 队列
    ##树
  • 树的表示
    • 父子兄弟树

  • 二叉树，树的遍历，决策树

    1
    2
    3
    4
    5
    6
    typedef struct binTreeNode
    {
    	ElementType element;
    	struct binTreeNode *left;
    	struct binTreeNode *right;
    }
    • Pre-order/Post-order/In-order
    • 通过遍历结果构造树
    • 数组表示二叉树 A[current] A[21] A[2\i+1]
    • 表达式树

  • 二叉查找树

    • Data Struct with fast search, slow insert/delete
      • Sorted array, with bounded size
    • Data Structure with fast insert/delete, slow search
      • Linked List
    • Balance BST : fast search fast insert fast delete
      • No bounded size
      • All operations log(n) ,if balanced
    • find（迭代形式）
    • findMin/findMax
    • insert
    • delete
    • BST的平均复杂度
  • 平衡二叉树：AVL树（红黑树没讲）
    • 旋转
    • $h \approx \sqrt{2}\log N_h$
  • B-树 B+树（没讲）

Hash

  • 冲突的解决
    • 分离链路法
      • 装填因子$\lambda$为元素个数与散列表大小的比值 最好 $\lambda \approx 1$
    • 开放地址法
      • $\lambda < 0.5$
      • 线性探测法 $F(i) = i$
      • 平方探测法 $F(i) = i^2$
  • 再散列 运行时间$O(N)$
  • 随机数算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
unsigned char Rand8[256];   //This array contains a random permutation 
							//form 0..255

int Hash(char *x) //*x is the first character
{
	int h;
	if (*x == 0) return 0;
	h1 = *x; h2 = *x +1;
	x++;
	while (*x)
	{
		h1 = Rand8[h1^ *x];
		h2 = Rand8[h2^ *x];
		x++;
	}
	h = ((int)(h1)<<8) |
			(int) h2;
	return h;
}
``` 

## Priority queue (Heap)
### binary heap
- percolate up(上滤)

```C++
void Insert( ElementType X, PriorityQueue H )
{
	int i;
	if (IsFull( H ))
	{
		Error();
		return;
	}
	for (i = ++H->size; H->Elements[ i/2 ] >X; i/=2)
	{
		H->Elements[i] = H->Elements[ i/2 ];
	}
	H->Elements[ i ] = X;
}

通常在Element[0]处，放一个绝对的最小值
时间复杂度$O(1)$， actually 2.607 comparisons and 1.607 moves

  • percolate down()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int DeleteMin( PriorityQueue H)
{
	int i, Child;
	int MinElement,LastElement;

	if( IsEmpty(H))
	{
		Error();
		return H->Elements[0];
	}

	for( i =1 ; i*2<=H->Size ;i = Child)
	{
		Child = i*2;
		if (Child != H->Size &&H->Elements[ Child + 1 ]
							 < H->Elements[Child])
		 {
			 Child++;
		 }
		
		/* percolate one level */
		if (LastElement >H->Elements[Child])
			H->Elements[i] = H->Elements[Child];
		else
			break;
	}
	
	h->Elements[ i ] = LastElement;
	return MinElement;
}

最坏情形$O(\log N)$
平均运行时间为$O(\log N)$

  • 建堆 (Build a Heap)
    从第一个非叶节点，不断下滤
    $O(N)$
  • 堆排序
    • Complexity = build a heap + deleteMax n times, $O(n\log n)$

Sort

InsertionSort

ShellSort

heapsort

mergesort

quicksort

Median-of-Three Partitioning(三数m中值分割法)

ExternalMergeSort

图论

图的表示

Adjacency List (临接链表)

Adjacency Matrix (邻接矩阵)

图的节点访问

最小生成树

Prim

Kruskal

最短路

unweighted path length

breadth-first-search(广度优先搜索)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void Unweighted( Table T)
{
	Queue Q;
	Vertex V,W;
	Q = CreateQueue(NumVertex);MakeEmpty(Q);
	Enqueue(S,Q);
	while( !IsEmpty(Q))
	{
		V = Dequeue(Q);
		T[V].Known = True;

		for each W adjacent to V
			if( T[W].Dist == Infinity )
			{
				T[W].Dist = T[V].Dist+1;
				t[W].Path = V;
				Enqueue(W,Q);
			}
	}
	DisposeQueue( Q );
}
depth-first-search(深度优先 )
1
2
3
4
5
6
7
void dfs(vert v)
{
	visited[v] = True;
	for each w adjacent to V:
		if (!visited[W])
			dfs(w);
}

weighted path length

Dijkstra
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void Dijkstra( Table T )
{
	Vertex V, W;
	
	for(;;)
	{
		V = smallest unknown distance vertex;
		if ( V == NotAVertex )
			break;
		T[ V ].Known = True;
		for each W adjacent to V
			if( !T[ W ].Known )
			{
				Decrease(T[W].Dist to 
						 T[W].Dist + Cvw);
				T[W].Path = V;
			}
	}
}

算法设计技巧

Greedy Algorithm

Huffman Encoding

Divide and Conquer

Median of medians

Dynamic Programming

Back Tracking