Algorithm第四版笔记-基础
Table of Contents
1 第一章-基础
- 编写递归代码的三条原则
- 递归总由一个最简单的情况
- 递归调用总是去尝试解决一个规模更小的子问题,这样递归才能收敛到最简单的情况
- 递归调用的父问题和尝试解决的子问题之间不应该有交集
- 抽象数据类型(ADT)是一种能够使用对使用者隐藏的数据表示的数据类型.
- 对象是能够承载数据类型的值的实体
- 所有对象都有三大重要特性
- 状态:数据类型中的值
- 标识:在内存中的位置,即地址
- 行为:数据类型的操作
- Java函数参数是按值传递的,无法改变该对象的引用,但能够改变该对象的值.
- 每个Java类都至少含有一个构造函数以创建一个对象的标识
- Java约定equals()必须是一种等价性关系,它必须具有
- 自反性: x.equals(x)为true
- 对称性: 当且仅当y.equals(x)为true时,x.equals(y)返回true
- 传递性: x.equals(y)和y.equals(x)为true,x.equals(z)也将为true
- 它必须接受一个Object为参数并满足一下性质
- 一致性: 当两个对象均未被修改时,反复调用x.equals(y)总是会返回相同的只
- 非空性: x.equals(null)总是返回false
- 异常: 一般用于处理不受我们控制的不可预见的错误
- 断言: 验证我们在代码中做出的一些假设,如果表达式为false,程序将会终止并报告一条出错信息
- 默认设置没有启用断言,可以在命令行使用`-enableassertions(-ea)`启用断言`
2 背包,队列和栈
- 自动将一个原始数据类型转换为一个封装类型被称为自动装箱
- 自动将一个封装类型转换为一个原始数据类型被称为自动拆箱
2.1 背包
- 背包是一种不支持从中删除元素的集合数据类型
- 它的目的就是帮助用例收集元素并迭代便利所有收集到的元素(用例也可以检查背包是否为空或者背包中的元素的数量)
- 使用Bag说明元素的处理顺序不重要
2.2 先进先出队列
- 先进先出(FIFO)队列是一种基于先进先出(FIFO)策略的集合类型.
2.3 下压栈
- 下压栈是一种基于后进先出(LIFO)策略的集合类型
2.4 链表
- 定义: 链表是一种递归的数据结构,它或者为空(null),或者指向一个节点(node)的引用,该节点包含有一个泛型的元素和一个指向另一条链表的引用.
3 算法分析
- 一个程序运行的总时间主要和两点有关
- 执行每条语句的耗时
- 执行每条语句的频率
- 从这里我们观察到的一个关键现象是最频繁的指令决定了程序执行的总时间,我们将这些指令称为程序的内循环.
- 对于大多数程序,得到其运行时间的数学模型所需的步骤如下
- 确定输入模型,定义问题的规模
- 识别内循环
- 根据内循环中的操作确定成本模型
- 对于给定的输入,判断这些操作的执行频率.这可能需要进行数学分析
- 增长数量级的分类
- 常数级别: 1 ,如普通语句
- 对数级别: \(\log{N}\) ,如二分策略
- 线性级别: \(N\) ,如一层循环
- 线性对数级别: \(N\log{N}\) ,如分治算法,归并排序
- 平方级别: \(N^2\) ,双层循环
- 立方级别: \(N^3\) ,三层循环
- 指数级别: \(2^N\) ,穷举查找
3.1 注意事项
- 大常数
- 如 \(2N^2+cN\) 近似为 \(2N^2\) ,其中c有可能很大(c可能是 \(10^3\) 或者是 \(10^6\) )
- 非决定性的内循环
- 指令时间
- 系统因素
- 不分伯仲
- 对输入的强烈依赖
- 多个问题参量
4 内存
- 原始数据类型的常见内存,需求
- boolean: 1字节
- byte: 1字节
- char: 2字节
- int: 4字节
- float: 4字节
- long: 8字节
- double: 8字节
4.1 对象
- 对象的内存量等于所有实例变量使用的内存+对象本身的开销
- 对象本身的开销(一般是16字节)
- 对象的类的引用
- 垃圾收集信息
- 同步信息
- 一个Integer对象使用24字节
- 16字节对象开销
- 4字节用来保存它的int值
- 4字节为填充字节
- 一个Date对象使用32字节
- 16字节对象开销
- 3个int变量各需4字节
- 4字节为填充字节
4.2 链表
- 一个Node对象需要使用40字节
- 16字节对象开销
- 指向Item对象的引用需要8字节
- 指向Node对象的引用需要8字节
- 8字节的额外开销(指向其外部类的引用,因为Node被设计为内部类)
- 一个包含N个整数的基于链表的栈Stack需要(32+64N)字节
- Stack对象的16字节的开销
- 引用类型实例变量8字节
- int型实例变量4字节
- 4字节为填充字节
- Node对象40字节
- Integer对象24字节
4.3 数组
- 一个原始类型的数组一般需要24字节的头信息
- 16字节的对象开销
- 4字节用于保存长度
- 4字节为填充字节
- 一个对象数组就是一个对象的引用的数组, 对象所需的内存+引用所需的内存(8M)
- 二维数组就是一个数组的数组(每一个数组都是一个对象),以M \(X\) N的double类型的二维数组为例
- 24字节为数组的数组的开销
- 8M字节(所有元素数组的引用)
- 24M字节(所有元素数组的开销)
- 8MN字节(M个长度为N的double类型数组)
- 总和为 \((8MN+32M+24)\) 字节
4.4 字符串对象
- String的标准实现含有4个实例变量(40字节)
- 一个指向字符数组的引用(8字节)
- 16字节对象开销(16字节)
- 填充字节(4字节)
- 三个int值(各4字节,共12字节)
- 第一个int值描述的是字符数组中偏移量
- 第二个int值是一个计数器(字符串的长度)
- 第三个int值是一个散列值
4.4.1 字符串的值和子字符串
- 一个长度为N的String对象一般需要40字节 + (24+2N)字节
- String对象本身(40字节)
- 字符数组(24+2N)字节
- 总共 (64 + 2N)字节
- 当调用了substring方法,就创建一个新的String对象(40字节),但是仍重用了相同的value[]数组
- 因此substring子字符串只会使用40字节的内存
- 一个子字符串所需的额外内存是一个常数,构造一个子字符串所需的时间也是常数
5 案例研究:union-find算法
5.1 动态连通性
- 一对整数p,q可以被理解为"p和q是相连的",我们假设"相连"是一种对等的关系,它们具有
- 自反性:p和q是相连的
- 对称性:如果p和q是相连的,那么q和p也是相连的
- 传递性:如果p和q是相连的且q和r是相连的,那么p和r也是相连的
- 目的
- 如果已知的所有整数对都不能说明p和q是相连的,那么则将一对整数写入到输出中.
- 如果已知的数据可以说明p和q是相连的,那么程序应该忽略p,q这对整数并继续处理输入中的下一对整数.
- 应用场景
- 网络连通的计算机
- 社交网络
- 电路的触点
- union-find算法的API
| public class UF | 描述 |
|---|---|
| UF(int N) | 以整数标识(0到N-1)初始化N个触点 |
| void union(int p, int q) | 在p和q之间添加一条连接 |
| int find(int p) | p所在的分量的标识符(0到N-1) |
| boolean connect(int p,int q) | 如果p和q存在于同一个分量中则返回true |
| int count() | 连续分量的数量 |