《算法4》回顾（一）

　　题记：花了断断续续四个月的时间，终于将Coursera上Robert Sedgewick老师的普林斯顿两部分算法课学习完。上课时仅以满分完成作业为目标，每周都赶得紧紧张张，回想起来才发现这些基本数据结构有些已经遗忘到只剩下一个概念了，于是做个计划：温习一遍教材，并把这些基本数据结构手写一遍加深印象。

第一章基础

1. 算法课的正确打开方式

1.1. 研究一个新的应用领域时，如何将其转换为可计算问题：

1）定义API；

2）根据特定的应用场景开发用例代码；

3）定义类实例变量所需的数据结构（一组值集的表示），并通过它实现API所对应的抽象数据类型；

4）描述算法（实现一系列操作的方法），并根据它实现类中的实例方法；

5）分析算法的性能特点。

1.2. 在实验可以重复执行以及假定可以被证伪的前提下，如何通过科学方法得出正确的计算模型（算法）：

1）细致地观察应用场景的特点；

2）根据观察结果提出假设模型；

3）根据模型预测计算结果；

4）继续观察并核实预测的准确性；

5）如此反复直到预测和观察一致。

1.3. 书中研究各类问题的基本步骤（上文1&2）：

1）完整而详细地定义问题，找出解决问题所需的基本抽象操作并定义一份API；

2）简洁地实现一种初级算法，给出一个精心组织的开发用例并使用实际数据作为输入；

3）当实现所能解决的问题的最大规模达不到期望时决定改进还是放弃；

4）逐步改进实现，通过经验性分析或（和）数学分析验证改进后的效果；

5）用更高层次的抽象表示数据结构或算法来设计更高级的改进版本；

6）如果可能尽量为最坏情况下的性能提供保证，但在处理普通数据时也要有良好的性能；

7）在适当的时候讲更细致的深入研究留给有经验的研究者并继续解决下一个问题。

评：“九层之台，起于累土；千里之行，始于足下。”先要定义好问题，然后才能解决问题；解决问题的方法很多，最直接的莫过于蛮力求解；蛮力求解不行的情况下，回顾定义问题的模型是否可以优化，是否可以提炼更优秀的数据结构来抽象数据类型；如果一个子问题的性能不能更高了，是否可以旁敲侧击从其他地方提高整体算法性能。如果实在没有办法了，也不要气馁，还有百度、谷歌、StackOverflow，毕竟世上还有好多NP问题存在。

2. 数组（顺序表）以及链表

2.1 声明：

数组的声明：

private Item[] array;

链表的数据结构：

private class  Node 
{
   Item item;
   Node next; 
}

2.2 数组以及链表的比较

数据结构	优点	缺点
数组	通过索引可以直接访问任意元素	在初始化时就需要知道元素的数量
链表	使用的空间大小和元素数量成正比	需要通过参照物来访问一个元素

2.3. 背包、栈、队列

2.3.1 定义：

背包（Bag）：一种不支持从中删除元素的集合数据类型，它的目的是帮助用例收集元素并遍历所有收集到的元素；

队列（Queue）：一种基于FIFO（先进先出）策略的集合类型，数据操作集中在队头（删除）、队尾（添加）两端；

栈（Stack）：一种基于LIFO（后进先出）策略的集合类型，数据操作只发生在栈顶（添加、删除）；

2.3.2 API：

Bag
	public class	Bag<Item> implements	Iterable<Item>
		Bag()	创建一个空背包
	void	add(Item item)	添加一个元素
	boolean	isEmpty()	背包是否为空
	int	size()	背包中的元素数量
FIFO queue
	public class	Queue<Item> implements	Iterable<Item>
		Queue()	创建一个空队列
	void	enqueue(Item item)	添加一个元素
	Item	dequeue()	删除队列中最早添加的元素
	boolean	isEmpty()	队列是否为空
	int	size()	队列中的元素数量
Pushdown (LIFO) stack
	public class	Stack<Item> implements	Iterable<Item>
		Stack()	创建一个空栈
	void	push(Item item)	添加一个元素
	Item	pop()	删除最近添加的元素
	boolean	isEmpty()	栈中是否为空
	int	size()	栈中的元素数量

2.3.3 队列和栈的实现方式：

书中分别给出了通过数组以及链表两种不同数据结构实现栈数据类型的方式，需要留意的是如何通过数组的动态调整来实现栈的扩张、收缩：

2.3.3.1 resize()函数：

private void resize(int max) 
{ 
   Item[] temp = (Item[]) new Object[max];
   for (int i = 0; i < N; i++)
      temp[i] = a[i];
   a = temp; 
}

2.3.3.2 Stack用例：

   public void push(Item item)
   {  // Add item to top of stack.
      if (N == a.length) resize(2*a.length);
      a[N++] = item;
   }
   public Item pop()
   {  // Remove item from top of stack.
      Item item = a[--N];
      a[N] = null;  // Avoid loitering (see text).
      if (N > 0 && N == a.length/4) resize(a.length/2);
      return item;
   }

评：resize调整的方式，使得数组也可以支持很深的栈，并在栈变浅时回收内存，不至于浪费资源。缺陷在于栈很深时，复制栈内容需要一定的开销，在单位时间并发度很高的系统中可能存在响应时间问题。