Java数据结构之基础知识

基础知识复习

数学知识复习

这里给出一些需要记忆或者能够推导出的基本公式。

指数

XAXB=XA+BX^{A} X^{B}=X^{A+B}

XAXB=XA−B\frac{X^{A}}{X^{B}}=X^{A-B}

(XA)B=XAB\left(X^{A}\right)^{B}=X^{A B}

XN+XN=2XN≠X2NX^{N}+X^{N}=2 X^{N} \neq X^{2 N}

2N+2N=2N+12^{N}+2^{N}=2^{N+1}

（没啥多说的）

对数

在计算机科学中，除非有特别说明，一般所有的对数都是以2为底的。

定义1.1：

XA=B，当且仅当logXB=AX^{A}=B，当且仅当log _{X} B=A

定理1.1：log⁡AB=log⁡CBlog⁡CA;A,B,C>0,A≠1\log _{A} B=\frac{\log _{C} B}{\log _{C} A} ; A, B, C>0, A \neq 1

定理1.2：log⁡AB=log⁡A+log⁡B;A,B>0\log A B=\log A+\log B ; A, B>0

证明如下：

级数

最容易记的公式是

∑i=0N2i=2N+1−1\sum_{i=0}^{N} 2^{i}=2^{N+1}-1

和

∑i=0NAi=AN+1−1A−1\sum_{i=0}^{N} A^{i}=\frac{A^{N+1}-1}{A-1}

（等比数列之和：$$
\begin{array}{l}
S_{n}=\frac{a_{1}-a_{n} q}{1-q} =\frac{a_{1}\left(1-q^{n}\right)}{1-q}(q \neq 1)
\end{array}

） 在第二个公式中, 如果 $0\sum_{i=0}^{N} A^{i} \leqslant \frac{1}{1-A}

当 $N$ 趋于 $\infty$ 时该和趋向于 $1 /(1-A)$, 这些公式是 “几何级数” 公式。 ![](https://img-qingbo.oss-cn-beijing.aliyuncs.com/img/20220503142552.png) 以下两个公式只不过是一般的代数运算：

\begin{array}{c}
\sum_{i=1}^{N} f(N)=N f(N) \
\sum_{i=n_{0}}^{N} f(i)=\sum_{i=1}^{N} f(i)-\sum_{i=1}^{n_{0}-1} f(i)
\end{array}

### 模运算 如果 $N$ 整除 $A-B$, 那么就说 $A$ 与 $B$ 模 $N$ 同余, 记为 $A \equiv B(\bmod N)$ 。直观地看, 这意味着无 论是 $A$ 还是 $B$ 被 $N$ 去除, 所得余数都是相同的。于是, $81 \equiv 61 \equiv 1(\bmod 10)$ 。如同等号的情形 一样, 若 $A \equiv B(\bmod N)$, 则 $A+C \equiv B+C(\bmod N)$ 以及 $A D \equiv B D(\bmod N)$ 。 有许多定理适用模运算，其中有些特别需要用到数论来证明。我们将尽量少使用模运算， 这样，前面的一些定理也就足够了。 ### 递归简论 ![](https://img-qingbo.oss-cn-beijing.aliyuncs.com/img/20220503142604.png) ## Java知识复习 [有道云笔记：Java泛型](http://note.youdao.com/noteshare?id=5efc4f58ed85a8367bbddda9cc58cd0d&sub=13C6B6E53CF0414AAF673DF5F9C391C2) **面向对象的一个重要目标是对代码重用的支持**。支持这个目标的一个重要机制就是**泛型机制(genericmechanism)**：如果除去对象的基本类型外，实现方法是相同的，那么我们就可以用**泛型实现( generic implementation)**来描述这种基本的功能。例如，可以编写一个方法，将由一些项组成的数组排序；方法的逻辑关系与被排序的对象的类型无关，此时可以使用泛型方法。与许多新的语言(例如C ++，它使用模板来实现泛型编程)不同，在1.5版以前，Java并不直接支持泛型实现，泛型编程的实现是通过使用继承的一些基本概念来完成的。本节描述在Java中如何使用继承的基本原则来实现一些泛型方法和类。 Sun公司在2001年是把对泛型方法和类的直接支持作为未来的语言增强剂来宣布的。后来，终于在2004年末发表了Java5并提供了对泛型方法和类的支持。然而，使用泛型类需要理解pre-Java5对泛型编程的语言特性。因此，**对继承如何用来实现泛型程序的理解是根本的关键**。甚至在Java5中任然如此。 ### 使用Object表示泛型 Java中可以通过**使用像Object这样适当的父类来实现泛型**。例如： 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * 存储单元
 */
public class MemoryCell{
    // 存储的内容，因为我们不确定是int还是String，所以我们就用适当的父类（Object）来实现泛型
    private Object storedValue;

    /**
     * 下面这两个public方法，一个读一个写，就类似于Getter和Setter方法
     */
    
    public Object read() {
        return storedValue;
    }
    public void write(Object x){
        storedValue = x;
    }
}
当使用Object来表示泛型时，需要注意两个点： 1. **强制类型转换**。为了访问这种对象的一个特定方法，必须要强制转换成正确的类型。 例如： 
1
2
3
4
5
public static void main(String[] args) {
    MemoryCell memoryCell = new MemoryCell();
    memoryCell.write(666);
    String value = (String) memoryCell.read();  // 如若具体的类型为String，我们需要强制转换成String
}
2. **不能使用基本类型**，只有**引用类型**才能与Object相容。 **[有道云笔记：Java包装类](http://note.youdao.com/noteshare?id=acf5300b9833d3d2ff035afe2f551436&sub=4DDD429EC3A144A28F891065393262E6)** 例如：使用MemoryCell类来存储整数（Integer） 
1
2
3
4
5
public static void main(String[] args) {
    MemoryCell memoryCell = new MemoryCell();
    memoryCell.write(666);
    Integer value = (Integer) memoryCell.read();  // 具体的类型为Integer，我们需要强制转换成Integer
}
### ==利用Java5泛型特性实现泛型构件== 从Java5开始就已经支持泛型类了，这些类很容易使用。这里我们稍微提一下**编写泛型类和泛型方法**的基础，**==贯穿该系列笔记的语法和习语==**。 - [**有道云笔记：Java泛型，泛型通配符**](http://note.youdao.com/noteshare?id=5efc4f58ed85a8367bbddda9cc58cd0d&sub=13C6B6E53CF0414AAF673DF5F9C391C2) - **[有道云笔记：Java包装类，自动装箱和自动拆箱](http://note.youdao.com/noteshare?id=acf5300b9833d3d2ff035afe2f551436&sub=4DDD429EC3A144A28F891065393262E6)** Java7之后，菱形运算符，如：`ArrayList arrayList = new ArrayList<>();` # 算法分析 [知乎：算法的时间与空间复杂度（一看就懂）](https://zhuanlan.zhihu.com/p/50479555) ## 数学基础 一般来说，估算算法资源所需的分析是一个理论问题，因此需要一套正式的系统架构。 **四个定义：** 1. 如果存在正常数 $c$ 和 $n_{0}$ 使得当 $N \geqslant n_{0}$ 时 $T(N) \leqslant c f(N)$, 则记为 $T(N)=O(f(N))$ 2. 如果存在正常数 $c$ 和 $n_{0}$ 使得当 $N \geqslant n_{0}$ 时 $T(N) \geqslant c g(N)$, 则记为 $T(N)=\Omega(g(N))$ 3. $T(N)=\Theta(h(N))$ 当且仅当 $T(N)=O(h(N))$ 和 $T(N)=\Omega(h(N))$ 4. 如果对每一正常数 $c$ 都存在常数 $n_{0}$ 使得当 $N>n_{0}$ 时 $T(N) **常用的时间复杂度所耗费的时间从小到大依次是：** >

\mathrm{O}(1)<\mathrm{O}(\log n)<\mathrm{O}(n)<\mathrm{O}(n \log n)<\mathrm{O}\left(n{2}\right)<\mathrm{O}\left(n{3}\right)<\mathrm{O}\left(2^{n}\right)<\mathrm{O}(n !)<\mathrm{O}\left(n^{n}\right)

在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T(n) = O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度。

这样用大写O()来体现算法时间复杂度的记法，我们称之为大O记法。

一般情况下，随着n的增大，T(n)增长最慢的算法为最优算法。

推导大O阶的方法

推导大O阶：

  1. 用常数1取代运行时间中所有加法常数
  2. 在修改后的运行次数函数中，只保留最高阶项
  3. 如果最高阶项存在且不是1，则去除与这个项相乘的常数。得到的结果就是大O阶

接下来我们具体看几个例子，就差不多能理解了。

O(1)

顺序结构的时间复杂度，为O(1)，如：

1
2
3
int sum = 0,n=100;      /* 执行一次 */
sum = (1+n)*n/2;        /* 执行一次 */
System.out.println(sum);    /* 执行一次 */

同样，对于分支结构（如if-else）而言，无论是真还是假，执行的次数都是恒定的，不会随着n的变大二发生变化，所以单纯的分支结构（不包含循环结构），其时间复杂度也是O(1)。

O(logn)

例子：

1
2
3
4
5
6
7
8
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int count = 1;
while (count<n){
    /* 时间复杂度为O(1)的程序步骤序列 */
    /*例如：*/
    count = count * 2;
}

由于每次count*2之后，就更接近n了。也就是说，有多少个2相乘后大于n，就会退出循环。由2x=n2^{x}=n 得到 x=log⁡2nx=\log _{2} n。所以这个循环的时间复杂度为O(logn)。

O(n)

线性阶的循环结构会复杂很多。要确定某个算法的阶次，我们常常需要确定某个特定语句或特定语句集的次数。因此，我们要分析算法的复杂度，关键就是要分析循环结构的运行情况。

例子：

1
2
3
4
5
6
7
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
for (int i = 0; i < n; i++) {
    /* 时间复杂度为O(1)的程序步骤序列 */
    /*例如：*/
    System.out.println(i);
}

循环的时间复杂度为O(n)，因为循环体中的代码需要执行n次。

O(nlog⁡n)\mathrm{O}(n \log n)

线性对数O(nlog⁡n)\mathrm{O}(n \log n)其实非常容易理解，将时间复杂度为O(logn)的代码循环n遍的话，那么它的时间复杂度就是 n * O(logN)，也就是了O(nlogN)。

例子：

1
2
3
4
5
6
7
8
for(int i=1; i<n; i++)
{
    int count = 1;
    while(count<n)
    {
        count = count * 2;
    }
}

这个嵌套循环的时间复杂度为：O(nlog⁡n)\mathrm{O}(n \log n)

O(n2)\mathrm{O}\left(n^{2}\right)

嵌套循环例子：其中它的内循环在我们上面的分析中已经得出，时间复杂度为O(n)

1
2
3
4
5
6
7
8
9
10
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            /* 时间复杂度为O(1)的程序步骤序列 */
            /*例如：*/
            System.out.println(i+j);
        }
    }
}

对于外层的循环，不过是内部这个时间复杂度为O(n)的语句，再循环n次。所以这段代码的时间复杂度为O(n2)\mathrm{O}\left(n^{2}\right)。

如果外循环的次数改为了m，时间复杂度就变为O(m*n)：

1
2
3
4
5
6
7
8
9
10
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        /* 时间复杂度为O(1)的程序步骤序列 */
        /*例如：*/
        System.out.println(i*j);
    }
}

接下来我们看一下下面这个嵌套循环，看一下它的时间复杂度为多少：

1
2
3
4
5
6
7
8
9
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {   /* 注意是j = i而不是j = 0 */
        /* 时间复杂度为O(1)的程序步骤序列 */
        /*例如：*/
        System.out.println(i*j);
    }
}

分析：当i = 0时，内循环执行了n次，当i = 1时，执行了n-1次，……当i = n - 1时，执行了1次。所以总的执行次数为：$$
n+(n-1)+(n-2)+\cdots+1=\frac{n(n+1)}{2}=\frac{n^{2}}{2}+\frac{n}{2}$$

根据我们上面给出的推导大O阶方法：第一条，没有加法常数不予考虑；第二条，只保留高阶项，因此保留n22\frac{n^{2}}{2}； 第三条，去除这个项相乘的常数，也就是去除1/2,，最终这最段代码的时间复杂度为O(n2)\mathrm{O}\left(n^{2}\right)。

从这个例子中我们可以得到一些经验：其实理解大O推导不算难，难的是对数列的一些相关运算，这更多的是需要我们的数学知识和能力。

对于方法调用的时间复杂度

对于方法调用的时间复杂度如何分析，我们继续来看例子：

1
2
3
4
5
6
7
8
9
10
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    for (int i = 0; i < n; i++) {
        function(i);
    }
}

private static void function(int i) {
    System.out.println(i);
}

function函数的时间复杂度为O(1)，所以整体的时间复杂度为O(n)。

现在改变一下function函数，例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void main(String[] args) {    
	Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    for (int i = 0; i < n; i++) {
        function(i);
    }
}

private static void function(int i) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    for (int j = 0; j < n; j++) {
        /* 时间复杂度为O(1)的程序步骤序列 */
    }
}

这个例子其实和上面一样的，时间复杂度为O(n2)\mathrm{O}\left(n^{2}\right)。

最后来看一段相对复杂的程序，应该就能理解时间复杂度怎么求了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    n++;            /* 执行次数为1 */
    function(n);    /* 执行次数为n */
    for (int i = 0; i < n; i++) {   /* 执行次数为n^2 */
        function(i);
    }
    for (int i = 0; i < n; i++) {   /* 执行次数为n(n+1)/2 */
        for (int j = i; j < n; j++) {
            /* 时间复杂度为O(1)的程序步骤序列 */
        }
    }
}

private static void function(int i) {
    for (int j = 0; j < i; j++) {
        /* 时间复杂度为O(1)的程序步骤序列 */
    }
}

它的执行次数 f(n)=1+n+n2+n(n+1)2=32n2+32n+1f(n)=1+n+n^{2}+\frac{n(n+1)}{2}=\frac{3}{2} n^{2}+\frac{3}{2} n+1, 根据推导大O阶的方法，最终这段代码的时间复杂度也是 O(n2)O\left(n^{2}\right) 。

常见的时间复杂度

常见的时间复杂度如下表：

常用的时间复杂度所耗费的时间从小到大依次是：

 执行次数函数  阶  非正式术语 12O(1) 常数阶 2n+3O(n) 线性阶 3n2+2n+1O(n2) 平方阶 5log⁡2n+20O(log⁡n) 对数阶 2n+3nlog2n+19O(nlog⁡n) nlogn 阶 6n3+2n2+3n+4O(n3) 立方阶 2nO(2n) 指数阶 \begin{array}{l} \begin{array}{l|l|l} \hline {\text { 执行次数函数 }} & {\text { 阶 }} & \text { 非正式术语 } \\ \hline 12 & \mathrm{O}(1) & \text { 常数阶 } \\ \hline 2 \mathrm{n}+3 & \mathrm{O}(n) & \text { 线性阶 } \\ \hline 3 \mathrm{n}^{2}+2 \mathrm{n}+1 & \mathrm{O}\left(n^{2}\right) & \text { 平方阶 } \\ \hline 5 \log _{2} \mathrm{n}+20 & \mathrm{O}(\log n) & \text { 对数阶 } \\ \hline 2 \mathrm{n}+3 \mathrm{nlog}_{2} \mathrm{n}+19 & \mathrm{O}(n \log n) & \text { nlogn 阶 } \\ \hline 6 \mathrm{n}^{3}+2 \mathrm{n}^{2}+3 \mathrm{n}+4 & \mathrm{O}\left(n^{3}\right) & \text { 立方阶 } \\ \hline 2^{\mathrm{n}} & \mathrm{O}\left(2^{n}\right) & \text { 指数阶 } \\ \hline \end{array} \end{array}

O(1)<O(log⁡n)<O(n)<O(nlog⁡n)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)\mathrm{O}(1)<\mathrm{O}(\log n)<\mathrm{O}(n)<\mathrm{O}(n \log n)<\mathrm{O}\left(n^{2}\right)<\mathrm{O}\left(n^{3}\right)<\mathrm{O}\left(2^{n}\right)<\mathrm{O}(n !)<\mathrm{O}\left(n^{n}\right)

上面我们已经介绍了O(1)，O(logn)，O(n)，O(nlog⁡n)\mathrm{O}(n \log n)，O(n2)\mathrm{O}\left(n^{2}\right)等。而像O(n3)\mathrm{O}\left(n^{3}\right)，O(2n)\mathrm{O}\left(2^{n}\right)，O(n!)\mathrm{O}(n !)，O(nn)\mathrm{O}\left(n^{n}\right)这些，过大的n都将会是噩梦般的运行时间，所以这种不切实际的时间复杂度我们一般不讨论。

通常，除非特别指定，我们提到的运行时间都是最坏情况的运行时间。一般在没有特殊说明的情况下，我们说的时间复杂度都是指最坏时间复杂度。

空间复杂度

既然时间复杂度不是用来计算程序具体耗时的，那么我也应该明白，空间复杂度也不是用来计算程序实际占用的空间的**。空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度，同样反映的是一个趋势，我们用 S(n) 来定义**（时间复杂度T(n)，空间复杂度S(n)）。空间复杂度比较常用的有：O(1)，O(n)，O(n²)。

O(1)

如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)。

例子：

1
2
3
4
5
6
int i = 1;
int j = 2;
i++;
j++;
int m = i + j;
System.out.println(m);

代码中的 i，j，m 所分配的空间都不随着处理数据量变化，因此它的空间复杂度 S(n) = O(1)。

O(n)

例子：

1
2
3
4
5
6
7
8
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] arr = new int[n];
int j;
for (int i = 0; i < n; i++) {
    j = i*i;
    System.out.println(j);
}

这段代码中，第3行new了一个数组出来，这个数据占用的大小为n，这段代码的5-8行，虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 S(n) = O(n)。

算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作: S(n)= O(f(n)), 其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数。

一般情况下， 一个程序在机器上执行时，除了需要存储程序本身的指令、常数、变量和输入数据外，还需要存储对数据操作的存储单元。若输入数据所占空间只取决于问题本身，和算法无关，这样只需要分析该算法在实现时所需的辅助单元即可。若算法执行时所需的辅助空间相对于输入数据量而言是个常数，则称此算法为原地工作，空间复杂度为0(1)。

通常，我们都使用“时间复杂度”来指运行时间的需求，使用“空间复杂度”指空间需求。当不用限定词地使用“复杂度”时，通常都是指时间复杂度。

抽象数据类型(ADT)

抽象数据类型( abstract data type, ADT)是带有一组操作的一些对象的集合。抽象数据类型是数学的抽象；在ADT的定义中没有地方提到关于这组操作是如何实现的任何解释。诸如表、集合、图以及与它们各自的操作一起形成的这些对象都可以被看做是抽象数据类型，这就像整数、实数、布尔数都是数据类型一样。整数、实数和布尔数各自都有与之相关的操作，而抽象数据类型也是如此。对于集合ADT，可以有像添加(add)、删除(remove)以及包含(contain)这样一些操作。当然，也可以只要两种操作并(union)和查找(find)，这两种操作又在这个集合上定义了一种不同的ADT。

Java类也考虑到ADT的实现，不过适当地隐藏了实现的细节。这样，程序中需要对ADT实施操作的任何其他部分可以通过调用适当的方法来进行。如果由于某种原因需要改变实现的细节，那么通过仅仅改变执行这些ADT操作的例程应该是很容易做到的。这种改变对于程序的其余部分是完全透明的。

对于每种ADT并不存在什么法则来告诉我们必须要有哪些操作，这是一个设计决策。错误处理和结构调整(在适当的地方)一般也取决于程序的设计者。后面的笔记中我们将要讨论的表、栈和队列这三种数据结构是ADT的最基本的例子。我们将会看到它们中的每一种是如何以多种方法实现的，不过，当它们被正确地实现以后，使用它们的程序却没有必要知道它们是如何实现的。