算法(第四版)读书笔记 第一章
y7## Java基础
数组
创建数组
- 声明数组的类型和名字
- 创建数组
- 初始化数组
double[] a; //声明数组
a= new double[N];//创建数组
for(int i =0;i<N;i++){
a[i] = 0.0
}//初始化数组
double[] a = new double[N];//简写
二维数组
静态方法
调用
- 方法的参数按值传递
参数变量的初始值是由调用方提供的，方法处理的是参数的值而非参数本身 - 方法名可以被重载
重写是子类的方法覆盖父类的方法，要求方法名和参数都相同
重载是在同一个类中的两个或两个以上的方法，拥有相同的方法名，但是参数却不相同，方法体也不相同，最常见的重载的例子就是类的构造函数，可以参考API帮助文档看看类的构造方法 - 方法只能返回一个值
返回被执行的第一条语句的返回值 - 返回值可以是void
递归
API
Math的参数都是double类型，返回值也是double，因此可以将它们看做是double的扩展
字符串
- "+"可以拼接字符串
- 类型转换
paseInt() toString() parseDouble()
i/o
标准输出(StdOut)
printin（）附加一个换行符
printf()格式化输出
命令行语句
javac .java 编译java文件
java .class 运行Java程序
格式化输出
printf()有两个参数
- 格式化字符
%跟着字符的转换代码(d(十进制)，f(浮点型)，s(字符串))，在%和代码之间可以添加一个整数表示输出字符串的长度，还可以插入一个小数点表示转换后double保留的位数或是string字符串截取的长度。\n为换行 - 要输出的变量
标准输入(StdIn)
Api
- isEmpty 没有剩余值就返回true，有就返回false
- readInt
- readDouble
...
基于文件的输入输出(In/Out)
public calss In
- readInts()
- readDoubles()
- readString()
public class Out - write(int[])
- write(double[])
- write(String[])
标准绘图库(StdDrw)
注意
- for()头部的代码和主体代码是一个作用域，while不是
- 声明数组 int[] a ,int a[]
- ptintIn(in[] a)输出的是他的地址
- 静态方法不能将另一个静态方法做参数
Week 1 union-find并查集问题
知识点
- 贪心算法 greedy algorithm
- connected component 连通组件(图论)
快速排序的Java实现
package com.algs4;
public class QuickFind {
private int [] id;
//set id of each object to itself
public QuickFind(int N){
id = new int[N];
for (int i = 0; i < N; i++) {
id[i] = i;
}
}
//check weather p and q in same component
public boolean connect(int p,int q){
return id[p] == id [q];
}
//change all entries with id[p] to id[q]
public void union(int p, int q){
int pid = id[p];
int qid = id[q];
for (int i = 0; i < id.length; i++) {
if (id[i] == pid) {
id[i] = qid;
}
}
}
}
//o(n^2)
但是quickfind对于数据量很大的数据来说就太慢了
优化1: 快速合并的替代替代算法 ‘Lazy approach’
把上面的数据结构中的一组数看做“树”
public class Quickunion {
private int[] id;
//set object to item
public Quickunion(int N){
for (int i = 0; i < N; i++) {
id = new int[N];
id[i] = i;
}
}
//通过回朔，寻找根节点，id[i] = i;就是根节点,如果不是，就把i在树上上移一层，把i设为i的id
private int root(int i){
while(i != id[i]) id[i] = i;
return i;
}
//判断根节点是否相等
public boolean connect(int p,int q){
return root(p) == root (q);
}
public void union(int p,int q){
int i = root(p);
int j = root(q);
id[i] = i;
}
}
quickunion有时候快，但有时候太慢了，因为树太高了。查找操作代价太大了，可能要回朔一颗瘦长的树，每个对象只是指向下一个节点，对子节点进行一次查找，就要回朔整个树，操作次数多了就满了
上面两种都不支持巨大的连通性问题
新的:quickunionimprovement
这时引入了一种新的方法，叫带权(weighting),在执行快速合并算法的时候执行一些操作避免很深的树，如果将大树和小树合并的时候，要避免把大树放在下面，避免得到更高的树。
实现:跟踪每棵树中对象的个数，然后我们会使小树的根节点作为大树的子节点。这样树的深度最多也只有四层
维护一个sz数组，在union操作中比较sz的大小，然后合并，时间复杂度为 lg(n)
public class QuickunionIm {
private int[] id;
private int[] sz; //维护一个sz数组，在union操作中比较sz的大小，然后合并
//set object to item
public QuickunionIm(int N){
for (int i = 0; i < N; i++) {
id = new int[N];
id[i] = i;
}
}
//通过回朔，寻找根节点，id[i] = i;就是根节点,如果不是，就把i在树上上移一层，把i设为i的id
private int root(int i){
while(i != id[i]) id[i] = i;
return i;
}
//判断根节点是否相等
public boolean connect(int p,int q){
return root(p) == root (q);
}
public void union(int p,int q){
int i = root(p);
int j = root(q);
if (i == j) return ;
if (sz[i] < sz[j]){
id[i] = j;sz[j] += sz[i];
}
else{
id[j] = i; sz[i] += sz[j];
}
}
}
improve2
cath compression 路径压缩
回溯一次路径找到根节点，然后再回溯将树展平,时间复杂度是接近线性的，那是否有时间复杂度为线性的呢？但最后有人证明合并算法没有线性的
//add second loop to root() to set the id[] of each examined node to root
public class Quickunionim2 {
private int[] id;
private int root(int i){
while( i != id[i]){
id[i] = id[id[i]];
i = id[i];
}
return i;
}
}
并查集算法的应用
渗滤（percolation） 上下是存在开放位，且联通的,系统是否渗透的p的阙值十分陡峭，要求那个值必须用计算机仿真，蒙特卡洛仿真。
算法分析
FFT 快速傅里叶变换算法，将算法信号的N个采样波形分为若干周期分量。DVD和JPEG的基础，将复杂度从N^2将为N*logN
3sum问题
简单的n^3
public class three_SUM {
public static int count(int[] a){
int N = a.length;
int count = 0;
for (int i = 0; i < a.length; i++) {
for (int j = i+1; j < a.length; j++) {
for (int j2 = j+1; j2 < a.length; j2++) {
if (a[i] + a[j] +a[j2] == 0) {
count ++;
}
}
}
}
return count;
}
public void main(String[] args){
int[] a = In.readInts(args[0]);
StdOut.println(count(a));
}
}
n^3 -> n^2longn
Java标准库里面有一个秒表类，可以计算用掉的时间
Stopwatch stopwatch = new Stopwatch();
double time = stopwatch.elapseTime();
log-log坐标系的的斜率为B，则正比于 N^b
一般的时间复杂度
- 常数 没有循环
- logN 被分成两半(二叉树查找) 时间增长也是常数
- N 遍历了所有元素 1SUM
- NlogN 分治法 ——>并归排序
- N^2 两次遍历
- 2^n
type of analyses
- 总考虑最坏的case
- 总考虑最好的case
~ 表示近似模型
- Θ记号就是表示增长阶数的方法 Θ(N2)就是某个常数乘以N2的简写。它的上下界都是常数乘以N^2。这就是我们实际用来对算法分类的记号
- 接下来是O记号，它是算法性能的上界比如O(N2)就表示当N增长时，运行时间小于某个常数乘以N2
- Ω用来表示下界，Ω(N2)表示当N增长时运行时间比某个常数乘以N2大。
内存
8个比特是一个字节。一百万比特是2的20次方个，十亿比特是2的30次方我们通常使用2^20表示兆字节MB。现在老的计算机我们用了很多年的32位系统，里面的指针是4个字节的。近几年我们基本都迁移到了新的计算模型，机器是64位的 指针是8个字节。
- bollan只占一个比特
- 字符占两个字节，16位的字符也就是16比特
- 普通int整型是四个字节或者32位。
- 单精度浮点型也是4个字节。
- 长整型和双精度浮点型是8个字节 大多数应用中，我们使用双精度浮点型表示浮点数，普通整型表示整数
- 对于数组，需要一定量的额外空间加上，如果有N个元素，基本类型的空间开支乘以N 所以长度为N的双精度浮点型数组需要的空间是8N+24。
- 二维数组需要的空间近似于8MN，额外空间还有一项但是对于大M和N这个式子就很准确了。
- 引用的开销还有典型实现中内置的用来对齐的空间使得每个对象占据的空间是8字节的倍数 例如，如果有一个日期对象，它有三个整型实例变量这个对象总共占据32字节。每个整型占据4个字节对象额外空间占16个字节，为了对齐需要4个字节，所以总共占32个字节
数据抽象
java编程主要是通过class构建被称为引用类型的数据类型，也被称为oop，也就是面向对象编程，即保持了某个数据类型的实体。
数据抽象(ADT)是一种能对使用者隐藏数据表示的数据类型。他的特点在于将数据和函数实现了关联，我们在使用数据类型时更加注重API操作；在实现数据类型时，我们专注于数据本身以及对数据的操作。
在这门课中我们要学会在不修改用例代码的情况下，用另一种算法替换并对实现性能提升
基本数据类型的算法和数据结构
stack and queues and bag(栈和队列和背包)
stack(栈)
后入先出 （FIFO）
public class stack<item>
stack() 创建一个新栈
void push （入栈 ） 插入元素
item pop （出栈）除去元素
boolean isEmpty() 栈是否为空
int size() 栈中元素的数量
queue（队列）
先入先出 下压（LIFO）
public class queue<item>
Queue() 创建一个新队列
enqueue()（入队）加入元素
dequeue() (出队)除去元素
boolean isEmpty() 是否为空
int size() 元素的数量
bag (背包)
public class Bag<item>
Bag() 创建一个新背包
void add(Item item) 添加一个元素
boolean isEmpty() 是否为空
int size() 元素
泛型和迭代
泛型
集合类数据抽象的一个关键特性就是我们可以用它储存任意类型的数据。java里面有一种特殊的机制能完成这项工作，我们称之为泛型,也叫做参数化类型。
上面的API当中类名后的<item>将item定义为一个类型参数，他是一个占位符，表示将使用某个数据类型。可以将Stack<item>理解为某个元素的栈。
Stack<String> stack = new Stack<String>();
stack .push('Test');
Stack next = stack.pop();
自动装箱
类型参数都必须实例化为引用类型，因此JAVA有一种特殊的机制（类型转换）使泛型代码处理原始数据类型。在处理 赋值语句，方法的参数和算数逻辑表达式时候，java会在引用类型和原始类型之间进行转换。