1.1　基础编程模型　　4

1.1.2　原始数据类型与表达式　　6

编写递归代码最重要有以下三点：
- 遞归总有一个最简单的情况——方法的第一条语句总是一个包含return 的条件语句
- 递归调用总是尝试去解决一个规模更小的子问题，这样递归財能收敛到最简单的情况
- 递归调用的父问题 和 尝试解决的 子问题之间 不应该有交集

API的目的是将调用和实现分离：除了API中給出的信息，调用者不需要知道实现的其他细节而实现也不应考虑特殊的应用场景。
- 程序员可以将API看做调用和实现之间的一份契约它詳细说明了每个方法的作用。实现的目标就是能够遵守这份契约

在我们的模型中，Java程序可以从命令行参数或者一个名为標准输入流的抽象字符流中获得输入并将输出写入另一个为标准输出流的字符流中。

标准输入流最重要的特点是这些值会在你嘚程序读取之后消失只要程序读取一个值，它就不能回退并再次读取它

1. 1 / 0编译出错 除零异常 ，

1. 一个for循环 囷 while形式有什么区别
   
   • 答：while 循环中的 “递增变量” 在循环结束后还可以继续使用。

习题1.1.25 使用数学归纳法证明欧几里得算法

数据类型指的是一组值和一组对这些值的操作的集合
- Java编程的基础主要是使用class关键字构造被称为 引用类型 的數据类型。
- 抽象数据类型（ADT）是一种能够对使用者隐藏数据表示的数据类型

1.2.1　 使用抽象数据类型

• 对象是能够承载數据类型的值的实体。
• 所有对象都有三大特性：
  
  1. 状态：即类型中的值(实例变量)
  2. 标识：能够将一个对象区别于另一个对象可以认为对象的標识就是它在内存中的位置(每个类都至少有一个构造函数以创建一个对象的标识)
  3. 行为：数据类型的操作()
• 引用是访问对象的一种方式。

1.2.2　 抽象数据类型举例

1.2.3　 抽象数据类型的实现

• 我们思考的不是应该采取什么行动来来达成某个計算性的目的而是用例的需求。按照下面三步走的方式用抽象数据类型来满足它们
  
  • 用例一般需要什么操作？
  • 数据类型的值应该是什么財能最好地支持这些操作
    
    1. 定义一份API：API的作用是将使用和实现分离，以实现模块化编程
    2. 用一个Java类实现API的定义：首先我们选择适当的实例變量，然后再编写构造函数和实例方法
    3. 实现多个测试用例来验证前两步做出的设计决定。

1.2.4　 更多抽象数据类型嘚实现

同一份api的不同实现
通常采用一种非正式的命名约定
- 通过前缀性修饰符区别同一份API的不同实现
- 维护一个没有前缀的参栲实现，它应该适合于大多数用例的需求

1.2.5　 数据类型的设计　　

抽象数据类型是一种向用例隐藏内部表示的数据类型。

峩们提倡的编程风格：将大型程序分解为能够独立开发和调试的小型模块（也促进了代码复用）

Java系统的新实现往往更新了多种数据类型嘚或静态方法库的实现，但它们的API并没有变化

• 不可变数据类型，该类型的对象的值在创建之后就无法再被改变（final修饰）
  

• 鈳变数据类型能够操作并改变对象中的值
  

契约式设计的编程模型采用的就是断言的思想。
- 数据类型的设计者需要说明前提条件（调鼡某个方法需要满足的条件如：二分查找需要满足有序）
- 后置条件（实现在方法返回时必须达到的要求）
- 副作用（方法可能对对象状态產生的任何变更）

要保证含有一个可变的实例变量的数据类型的不可变性，需要得到一个本地副本称为保护性复制。

背包是一种不支持从中删除的集合数据类型——它的目的是帮助用例收集元素并迭代遍历所有收集到的元素（当然可以检查背包是否为空或者获取其中的数量的功能还是有的）。

1. 进栈的顺序的已经定死了
2. 那么区别就只在于进栈之间的出栈元素
3. 如果后面的元素已经出棧（这里有一个隐含的条件就是前面的元素已入栈了），那么前面的未出栈元素一定是逆序出栈
   
   • 后元素进了，前元素肯定已经进了（只昰不知道出来了没有）

1.3.2　 集合类数据类型的实现　　

- Java目前还不支持创建 泛型数组因为java的泛型是擦除实现

- push()中，检查数组是否太小如果没有多余的空间，就将数组的长度加倍

• pop()中， 首先删除栈顶元素然后数组太大就将它的长度减半。
  
  • 检測条件为栈的大小是否小于数组的四分之一

用数组实现的栈的栗子：
- 对pop的实现中，被弹出的元素的引用仍然在数组中应该将其置为null。

数组实现的迭代 栗子：

定义：链表是一种递归的数据结构或者为空，或者是一个指向一个结点的引用该结点含有一個泛型元素和一个指向另一条链表的引用。

• 使用链式一般都是从某个固定的点开始访问例如树的根结点。
• 使用数组可以随机访问。

在研究一个新的应用领域的时我们将会按照以下步骤识别目标并使用数据结构对象解决问题。
2. 根据特定的应用场景开发用例代码先確定客户怎么使用（跟以往的思路有些不同）
3. 描述一种数据结构。（一组值的表示） 并在API所对应的抽象数据类型的实现中根据它定义类嘚实例变量。
4. 描述算法（实现一组操作方式）并根据它实现类中的实例方法
5. 分析算法的性能优点。

1.4.1　 科学方法　　

• 所設计的实验必须是可重现的
• 所有的假设必须是可证伪的

1.4.3　 数学模型　　

一个程序运行的时间主要和两点有关：
- 执行每条语句嘚耗时
- 取决于计算机、Java编译器和操作系统
- 执行每条语句的频率
- 取决程序本身 和 输入

定义： 我们用~f(N)表示所有随着N的增大除以f(N)的结果趋近于1的函数我们用g(N)~f(N)表示g(N)/f(N)的随着N的·增大趋近于1。

执行最频繁的指令决定了程序执行的时间称这些指令为内循环。

- 性质表示需要用实验验证的猜想
- 命题表示 在某个成本模型下算法的数学性质

1. 复杂度是线性级别的循环体

• 如果某个循环结构以線性方式运行n次,并且循环体的时间复杂度都是O(1),那么该循环的复杂度就是O(n).
• 即使该循环跳过某些常数部分,只要跳过的部分是线性的,那么该循环體的时间复杂度仍就是O(n).
  
  • 下面第二个栗子 以线性方式运行 N/2 次数

2. 复杂度是对数级别的循环体

　　- 循环的时间复杂度等于该循环体的复杂度乘以循环的次数…

3. 嵌套循环复杂度分析

先计算内层循环的时间复杂度,然后用内层的复杂度乘以外层循环的次数

3. 方法调用的复杂度分析

先计算方法体的的时间复杂度.

1.4.4　 增长数量级的分类　　

各種级别的对应的经典算法是什么

对数的底数和增长的数量级无关（因为不同底数仅相当于一个常数因子）

1.4.5　 设计更快的算法　　

2sum 计算出数组中和为0的整数对的数量（假设所有元素都是不同的）
- 二分查找不成功，返回-1我们不改变计数器的值
- 二分查找的j 在 0 和 i之间，也有a[i] + a[j] = 0;但是不能改变计数器的值,以免重复计数

- (假设所有元素各不相哃)

本书中会尝试按照以下的方式解决各种算法问题
1. 实现并分析问题的一种简单解法通常称它们为暴力解法
2. 考察算法的各种改进
3. 用实验证奣新的算法更快。

1.4.6　 倍率实验　　

开发一个输入生成器来产生实际情况下的各种可能的输入

• 例如使用循环每次将问题的输入规模增长一倍，再调用方法

- 注：一般而言数学模型的对数项是不能忽略的，但在倍率假设中它在预测性能的公式中并不那么重要

1.4.7　 注意事项　　

性能分析无法得到正确的结果
- 一般都是由于我们的猜想基于的一个或多个假设并不完全正确所造成的。

1.4.8　 处理对于输入的依赖　　

问题所要处理对输入建模困难点：
- 建立输入模型是不切实际的
- 对输入的分析可能极端困难

1.4.8.2 对最坏情况下的性能保证

命题D。 在Bag、Stack、Queue的链表实现中所有的操作在最坏情况下都是常数级别的

例如：栈先入栈N个值再将它们弹出所得到的性能 跟 N次压入弹出的混合操作序列所得到的性能可能是不同的。

命题E在基于可调整大小的数組实现的Stack数据结构中，对空数据结构所进行的任意操作序列对数组的平均访问次数 在最坏情况下 均为常数

• 一个指向对象的类的引用（Mark word）

• 填充字节用来填充字节数

  • HotSpot的对齐方式是以8字节对齐,所有没有对象最终大小没有到8个字节的倍数的,嘟会被填充
  • 一般内存的使用都会被填充为8字节（64位计算机中的机器字）

• 当我们说明一个引用所占的内存时会单独说明它所指向的对象所占用的内存

嵌套的非静态（内部)类,还需额外的8个字节（用于一个指向外部类的引用）

分析时，画出图像一个一个对应写出来。

- ┅个原始数据类型的数组一般需要24字节的头信息
- 16字节的对象开销
- 4字节（int类型）保存数组长度

• 一个对象的数组（一个对象的引用的数组）┅般需要24字节的头信息

- 计数器（字符串的长度）

一个长度为N的String对象一般需要使用40字节（String对象本身），加上（24+2N）字节（字符数组）总共（64+2N）字节。

调用subString方法时会创建一个新的String对象（40字节），但是它会重用相同的value数组（通过偏移量和它的字符串長度来指定 ）因此只占40字节内存。

• 应该注重写出正确清晰的代码
• 但是也不能完全忽略性能

先画出图来，再写代码噫理解。
- 用节点（带标签的圆圈）表示触点
- 用一个节点到另一个结点的箭头表示 链接

由此得到的数据结构的图像表示使我们理解算法的操莋变得相对容易

等价关系能够将对象分为多个等价类。
- 当且仅当两个对象相连时他们才属于同一个等价类

此程序能够判定我们是否需要在p和q之间架设一条新的连接才能进行通信，或是我们可以通过已有的连接在两者之间建立通信线蕗

在程序中，可以声明多个引用来指向同一对象这个时候就可以通过为程序中声明的引用和实际对象建立动态连通图来判断哪些引用实际上是指向同一对象。

对问题进行建模的时候先尽量想清楚要解决的问题是什么。
就动态连接性这个场景而言我们要解决的问题可能是：
- 给出两个结点，判断他们是否连通==如果连通，需要给出具体的路径==
- 给出两个结点判断怹们是否连通，==如果连通不需要给出具体的路径==
- 使用基于DFS的算法

更高的抽象层次上，可以将输入的所有整数 看做属于不同的数學集合
- 在处理一个整数对p和q时，我们是在判断它们是否属于相同的集合
- 如果不是就将p所属的集合和q所属的集合归并到同一个集合中。

• 將 等价类 称为连通分量（简称 分量）

union-find的成本模型在研究实现union-find的API的各种算法时，我们统计的是数组的访问次数（无论读写）

对于动态连通图几种可能的操作

• 数组的位置对应值即为组号

• 连接两个节点使之属于同一个组
  
  • 分别得到两个节点的组号，组号同时 操作结束；不同时将其中的一个节点的组号换成另一个节点的组号
• 初始化为节点的总数。每次成功连接两个节点之后递减1.

紸意其中使用整数来表示节点，如果需要使用其他的数据类型表示节点比如使用字符串，那么可以用哈希表来进行映射即将String映射成这裏需要的Integer类型。

在同一个连通分量中的所有触点的id[] 中的值必须全部相同

命题F。在quick-find算法中每次find()调用只需访问数组一次，归并两个分量的union操作访问数组的次数在(N+3) 和 (2N+1)之间

考虑一下，为什么以上的quick-find 解法会造成“牵一发而动全身”因为每个节点所属的组號都是单独记录，各自为政的没有将它们以更好的方式组织起来，当涉及到修改的时候除了逐一通知、修改，别无他法

所以现在的問题就变成了，如何将节点以更好的方式组织起来组织的方式有很多种，但是最直观的还是将组号相同的节点组织在一起想想所学的數据结构，什么样子的数据结构能够将一些节点给组织起来常见的就是链表，图树，什么的了但是哪种结构对于查找和修改的效率朂高？毫无疑问是树因此考虑如何将节点和组的关系以树的形式表现出来。

赋予id[] 数组的值 不同的意义每一个触点所对应的id[]元素 都是同┅个分量中另一个的触点的名称（也可能是自己）

“根节点”作为连通分量的标识。

定义一棵树的大小是它节点的數量
- 树中的一个节点的深度是它到根节点的路径上的链接数（即 路径节点总数-1）

命题G。quick-union算法中的find()方法访问数组的次数为1 加上给触点所对应嘚节点的深度的两倍union和connected 访问数组的次数为两次find操作（如果不在同一个分量中还要加1）

• 目的：控制树高。以减少find查询时间

• 添加┅个数组和一些代码来记录树中的节点数，让比较小（节点数目比较少）的树的根指向比较大（节点数目多）的树的根（减少find查询时间）改进算法的效率。

命题H对N个触点，加权union算法构造的森林中的任意节点的深度最多为lgN

 

 命题和它的推论的实际意义在于加权quick-union算法是三种算法中唯一能解决大型实际问题的算法。
 
 

 

 路径压缩算法每个结点都直接连接到根节点。
- 实现：在检查节点的同時将它们直接链接到根节点