基础数据结构

数组

概述

定义

在计算机科学中，数组是由一组元素（值或变量）组成的数据结构，每个元素有至少一个索引或键来标识

In computer science, an array is a data structure consisting of a collection of elements (values or variables), each identified by at least one array index or key

因为数组内的元素是连续存储的，所以数组中元素的地址，可以通过其索引计算出来，例如：

1
int[] array = {1,2,3,4,5}

知道了数组的数据起始地址 $BaseAddress$，就可以由公式 $BaseAddress + i * size$ 计算出索引 $i$ 元素的地址

  • $i$ 即索引，在 Java、C 等语言都是从 0 开始
  • $size$ 是每个元素占用字节，例如 $int$ 占 $4$，$double$ 占 $8$

小测试

1
byte[] array = {1,2,3,4,5}

已知 array 的数据的起始地址是 0x7138f94c8，那么元素 3 的地址是什么？

答：

元素3的地址可以通过数组的起始地址加上元素3的索引乘以元素的大小来计算。在这种情况下，元素3的索引是2（数组索引从0开始），元素的大小是1字节（byte类型的大小为1字节）。

0x7138f94c8 + 2 * 1 = 0x7138f94ca

空间占用

Java 中数组结构为

  • 8 字节 markword
  • 4 字节 class 指针（压缩 class 指针的情况）
  • 4 字节 数组大小（决定了数组最大容量是 $2^{32}$）
  • 数组元素 + 对齐字节（java 中所有对象大小都是 8 字节的整数倍[^12]，不足的要用对齐字节补足）

例如

1
int[] array = {1, 2, 3, 4, 5};

的大小为 40 个字节，组成如下

1
8 + 4 + 4 + 5*4 + 4(alignment)

随机访问性能

即根据索引查找元素，时间复杂度是 $O(1)$

动态数组

java 版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
public class DynamicArray implements Iterable<Integer> {
    private int size = 0; // 逻辑大小
    private int capacity = 8; // 容量
    private int[] array = {};


    /**
     * 向最后位置 [size] 添加元素
     *
     * @param element 待添加元素
     */
    public void addLast(int element) {
        add(size, element);
    }

    /**
     * 向 [0 .. size] 位置添加元素
     *
     * @param index   索引位置
     * @param element 待添加元素
     */
    public void add(int index, int element) {
        checkAndGrow();

        // 添加逻辑
        if (index >= 0 && index < size) {
            // 向后挪动, 空出待插入位置
            System.arraycopy(array, index,
                    array, index + 1, size - index);
        }
        array[index] = element;
        size++;
    }

    private void checkAndGrow() {
        // 容量检查
        if (size == 0) {
            array = new int[capacity];
        } else if (size == capacity) {
            // 进行扩容, 1.5 1.618 2
            capacity += capacity >> 1;
            int[] newArray = new int[capacity];
            System.arraycopy(array, 0,
                    newArray, 0, size);
            array = newArray;
        }
    }

    /**
     * 从 [0 .. size) 范围删除元素
     *
     * @param index 索引位置
     * @return 被删除元素
     */
    public int remove(int index) { // [0..size)
        int removed = array[index];
        if (index < size - 1) {
            // 向前挪动
            System.arraycopy(array, index + 1,
                    array, index, size - index - 1);
        }
        size--;
        return removed;
    }


    /**
     * 查询元素
     *
     * @param index 索引位置, 在 [0..size) 区间内
     * @return 该索引位置的元素
     */
    public int get(int index) {
        return array[index];
    }

    /**
     * 遍历方法1
     *
     * @param consumer 遍历要执行的操作, 入参: 每个元素
     */
    public void foreach(Consumer<Integer> consumer) {
        for (int i = 0; i < size; i++) {
            // 提供 array[i]
            // 返回 void
            consumer.accept(array[i]);
        }
    }

    /**
     * 遍历方法2 - 迭代器遍历
     */
    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            int i = 0;

            @Override
            public boolean hasNext() { // 有没有下一个元素
                return i < size;
            }

            @Override
            public Integer next() { // 返回当前元素,并移动到下一个元素
                return array[i++];
            }
        };
    }

    /**
     * 遍历方法3 - stream 遍历
     *
     * @return stream 流
     */
    public IntStream stream() {
        return IntStream.of(Arrays.copyOfRange(array, 0, size));
    }
}
  • 这些方法实现，都简化了 index 的有效性判断，假设输入的 index 都是合法的

插入或删除性能

头部位置，时间复杂度是 $O(n)$

中间位置，时间复杂度是 $O(n)$

尾部位置，时间复杂度是 $O(1)$（均摊来说）

二维数组

1
2
3
4
5
int[][] array = {
    {11, 12, 13, 14, 15},
    {21, 22, 23, 24, 25},
    {31, 32, 33, 34, 35},
};

内存图如下

image-20221104114132056

  • 二维数组占 32 个字节，其中 array[0]，array[1]，array[2] 三个元素分别保存了指向三个一维数组的引用

  • 三个一维数组各占 40 个字节

  • 它们在内层布局上是连续的

更一般的，对一个二维数组 $Array[m][n]$

  • $m$ 是外层数组的长度，可以看作 row 行
  • $n$ 是内层数组的长度，可以看作 column 列
  • 当访问 $Array[i][j]$，$0\leq i \lt m, 0\leq j \lt n$时，就相当于
    • 先找到第 $i$ 个内层数组（行）
    • 再找到此内层数组中第 $j$ 个元素（列）

小测试

Java 环境下（不考虑类指针和引用压缩，此为默认情况），有下面的二维数组

1
2
3
4
5
byte[][] array = {
    {11, 12, 13, 14, 15},
    {21, 22, 23, 24, 25},
    {31, 32, 33, 34, 35},
};

已知 array 对象起始地址是 0x1000，那么 23 这个元素的地址是什么？（不太理解对齐字节！！！）

答：

  • 起始地址 0x1000
  • 外层数组大小：16字节对象头 + 3元素 * 每个引用4字节 + 4 对齐字节 = 32 = 0x20
  • 第一个内层数组大小：16字节对象头 + 5元素 * 每个byte1字节 + 3 对齐字节 = 24 = 0x18
  • 第二个内层数组，16字节对象头 = 0x10，待查找元素索引为 2
  • 最后结果 = 0x1000 + 0x20 + 0x18 + 0x10 + 2*1 = 0x104a

局部性原理

这里只讨论空间局部性

  • cpu 读取内存（速度慢）数据后，会将其放入高速缓存（速度快）当中，如果后来的计算再用到此数据，在缓存中能读到的话，就不必读内存了
  • 缓存的最小存储单位是缓存行（cache line），一般是 64 bytes，一次读的数据少了不划算啊，因此最少读 64 bytes 填满一个缓存行，因此读入某个数据时也会读取其临近的数据，这就是所谓空间局部性

对效率的影响

比较下面 ij 和 ji 两个方法的执行效率

1
2
3
4
5
6
7
8
9
10
11
12
int rows = 1000000;
int columns = 14;
int[][] a = new int[rows][columns];

StopWatch sw = new StopWatch();
sw.start("ij");
ij(a, rows, columns);
sw.stop();
sw.start("ji");
ji(a, rows, columns);
sw.stop();
System.out.println(sw.prettyPrint());

ij 方法

1
2
3
4
5
6
7
8
9
public static void ij(int[][] a, int rows, int columns) {
    long sum = 0L;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < columns; j++) {
            sum += a[i][j];
        }
    }
    System.out.println(sum);
}

ji 方法

1
2
3
4
5
6
7
8
9
public static void ji(int[][] a, int rows, int columns) {
    long sum = 0L;
    for (int j = 0; j < columns; j++) {
        for (int i = 0; i < rows; i++) {
            sum += a[i][j];
        }
    }
    System.out.println(sum);
}

执行结果

1
2
3
4
5
6
7
8
0
0
StopWatch '': running time = 96283300 ns
---------------------------------------------
ns         %     Task name
---------------------------------------------
016196200  017%  ij
080087100  083%  ji

可以看到 ij 的效率比 ji 快很多，为什么呢？

  • 缓存是有限的，当新数据来了后，一些旧的缓存行数据就会被覆盖
  • 如果不能充分利用缓存的数据，就会造成效率低下

以 ji 执行为例，第一次内循环要读入 $[0,0]$ 这条数据，由于局部性原理，读入 $[0,0]$ 的同时也读入了 $[0,1] … [0,13]$，如图所示

image-20221104164329026

但很遗憾，第二次内循环要的是 $[1,0]$ 这条数据，缓存中没有，于是再读入了下图的数据

image-20221104164716282

这显然是一种浪费，因为 $[0,1] … [0,13]$ 包括 $[1,1] … [1,13]$ 这些数据虽然读入了缓存，却没有及时用上，而缓存的大小是有限的，等执行到第九次内循环时

image-20221104164947154

缓存的第一行数据已经被新的数据 $[8,0] … [8,13]$ 覆盖掉了，以后如果再想读，比如 $[0,1]$，又得到内存去读了

同理可以分析 ij 函数则能充分利用局部性原理加载到的缓存数据

举一反三

  1. I/O 读写时同样可以体现局部性原理

  2. 数组可以充分利用局部性原理，那么链表呢？

    答：链表不行，因为链表的元素并非相邻存储

链表

概述

定义

在计算机科学中，链表是数据元素的线性集合，其每个元素都指向下一个元素，元素存储上并不连续

In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next.

可以分类为[^5]

  • 单向链表，每个元素只知道其下一个元素是谁

image-20221110083407176

  • 双向链表，每个元素知道其上一个元素和下一个元素

image-20221110083427372

  • 循环链表，通常的链表尾节点 tail 指向的都是 null，而循环链表的 tail 指向的是头节点 head

image-20221110083538273

链表内还有一种特殊的节点称为哨兵（Sentinel）节点，也叫做哑元（ Dummy）节点，它不存储数据，通常用作头尾，用来简化边界判断，如下图所示

image-20221110084611550

随机访问性能

根据 index 查找，时间复杂度 $O(n)$

插入或删除性能

  • 起始位置：$O(1)$
  • 结束位置：如果已知 tail 尾节点是 $O(1)$，不知道 tail 尾节点是 $O(n)$
  • 中间位置：根据 index 查找时间 + $O(1)$

单向链表

根据单向链表的定义，首先定义一个存储 value 和 next 指针的类 Node，和一个描述头部节点的引用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class SinglyLinkedList {
    
    private Node head; // 头部节点
    
    private static class Node { // 节点类
        int value;
        Node next;

        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }
}
  • Node 定义为内部类，是为了对外隐藏实现细节，没必要让类的使用者关心 Node 结构
  • 定义为 static 内部类，是因为 Node 不需要与 SinglyLinkedList 实例相关，多个 SinglyLinkedList实例能共用 Node 类定义

头部添加

1
2
3
4
5
6
public class SinglyLinkedList {
    // ...
    public void addFirst(int value) {
		this.head = new Node(value, this.head);
    }
}
  • 如果 this.head == null，新增节点指向 null，并作为新的 this.head
  • 如果 this.head != null，新增节点指向原来的 this.head，并作为新的 this.head
    • 注意赋值操作执行顺序是从右到左

while 遍历

1
2
3
4
5
6
7
8
9
10
11
public class SinglyLinkedList {
    // ...
    public void loop() {
        Node curr = this.head;
        while (curr != null) {
            // 做一些事
            System.out.println(curr.value);
            curr = curr.next;
        }
    }
}

for 遍历

1
2
3
4
5
6
7
8
9
public class SinglyLinkedList {
    // ...
    public void loop() {
        for (Node curr = this.head; curr != null; curr = curr.next) {
            // 做一些事
 		   System.out.println(curr.value);
        }
    }
}
  • 以上两种遍历都可以把要做的事以 Consumer 函数的方式传递进来
    • Consumer 的规则是一个参数，无返回值，因此像 System.out::println 方法等都是 Consumer
    • 调用 Consumer 时，将当前节点 curr.value 作为参数传递给它
1
2
3
4
5
6
7
8
9
xxx.traverse(System.out::println);

public void traverse(Consumer<Integer> consumer) {
     Node p = head;
     while (p != null) {
         consumer.accept(p.value);
         p = p.next;
     }
 }

迭代器遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class SinglyLinkedList implements Iterable<Integer> {
    // ...
    private class NodeIterator implements Iterator<Integer> {
        Node curr = head;
        
        public boolean hasNext() {
            return curr != null;
        }

        public Integer next() {
            int value = curr.value;
            curr = curr.next;
            return value;
        }
    }
    
    public Iterator<Integer> iterator() {
        return new NodeIterator();
    }
}
  • hasNext 用来判断是否还有必要调用 next
  • next 做两件事
    • 返回当前节点的 value
    • 指向下一个节点
  • NodeIterator 要定义为非 static 内部类，是因为它与 SinglyLinkedList 实例相关，是对某个 SinglyLinkedList 实例的迭代

递归遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class SinglyLinkedList implements Iterable<Integer> {
    // ...
    public void loop() {
        recursion(this.head);
    }

    private void recursion(Node curr) {
        if (curr == null) {
            return;
        }
        // 前面做些事
        recursion(curr.next);
        // 后面做些事
    }
}

尾部添加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class SinglyLinkedList {
    // ...
    private Node findLast() {
        if (this.head == null) {
            return null;
        }
        Node curr;
        for (curr = this.head; curr.next != null; ) {
            curr = curr.next;
        }
        return curr;
    }
    
    public void addLast(int value) {
        Node last = findLast();
        if (last == null) {
            addFirst(value);
            return;
        }
        last.next = new Node(value, null);
    }
}
  • 注意，找最后一个节点，终止条件是 curr.next == null
  • 分成两个方法是为了代码清晰，而且 findLast() 之后还能复用

尾部添加多个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class SinglyLinkedList {
    // ...
	public void addLast(int first, int... rest) {
        
        Node sublist = new Node(first, null);
        Node curr = sublist;
        for (int value : rest) { //仅是遍历
            curr.next = new Node(value, null);
            curr = curr.next;
        }
        
        Node last = findLast();
        if (last == null) {
            this.head = sublist;
            return;
        }
        last.next = sublist;
    }
}
  • 先串成一串 sublist
  • 再作为一个整体添加

根据索引获取

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class SinglyLinkedList {
    // ...
	private Node findNode(int index) {
        int i = 0;
        for (Node curr = this.head; curr != null; curr = curr.next, i++) {
            if (index == i) {
                return curr;
            }
        }
        return null;
    }
    
    private IllegalArgumentException illegalIndex(int index) {
        return new IllegalArgumentException(String.format("index [%d] 不合法%n", index));
    }
    
    public int get(int index) {
        Node node = findNode(index);
        if (node != null) {
            return node.value;
        }
        throw illegalIndex(index);
    }
}
  • 同样，分方法可以实现复用

插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class SinglyLinkedList {
    // ...
	public void insert(int index, int value) {
        if (index == 0) {
            addFirst(value);
            return;
        }
        Node prev = findNode(index - 1); // 找到上一个节点
        if (prev == null) { // 找不到
            throw illegalIndex(index);
        }
        prev.next = new Node(value, prev.next);
    }
}
  • 插入包括下面的删除，都必须找到上一个节点

删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class SinglyLinkedList {
    // ...
	public void remove(int index) {
        if (index == 0) {
            if (this.head != null) {
                this.head = this.head.next;
                return;
            } else {
                throw illegalIndex(index);
            }
        }
        Node prev = findNode(index - 1);
        Node curr;
        if (prev != null && (curr = prev.next) != null) {
            prev.next = curr.next;
        } else {
            throw illegalIndex(index);
        }
    }
}
  • 第一个 if 块对应着 removeFirst 情况
  • 最后一个 if 块对应着至少得两个节点的情况
    • 不仅仅判断上一个节点非空，还要保证当前节点非空

完整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
public class SinglyLinkedList implements Iterable<Integer> {
    private Node head;

    /**
     * 根据索引移除节点
     *
     * @param index
     */
    public void remove(int index) {
        if (index == 0) {
            if (head == null) {
                this.head.next = head.next;
            } else {
                throw illegalIndex(index);
            }
        }
        Node prev = findNode(index - 1);
        Node curr;
        if (prev != null && (curr = prev.next) != null) {

            prev.next = curr.next;
        } else {
            throw illegalIndex(index);
        }

    }

    /**
     * 根据索引插入节点
     *
     * @param index
     * @param value
     */
    public void insert(int index, int value) {
        //为空
        if (head == null) {
            addLast(value);
            return;
        }
        Node prev = findNode(index - 1); // 找到上一个节点
        if (prev == null) { // 找不到
            throw illegalIndex(index);
        }
        prev.next = new Node(value, prev.next);

    }

    /**
     * 根据索引查询节点
     *
     * @param index
     * @return 查找到的节点
     */
    public Node findNode(int index) {
        int count = 0;
        for (Node curr = head; curr != null; curr = curr.next, count++) {
            if (index == count) {
                return curr;
            }
        }
        return null;
    }

    /**
     * 根据索引获取节点的值
     *
     * @param index
     * @return
     */
    public int get(int index) {
        Node node = findNode(index);
        if (node != null) {
            return node.value;
        }
        throw illegalIndex(index);
    }

    private IllegalArgumentException illegalIndex(int index) {
        return new IllegalArgumentException(String.format("index [%d] 不合法%n", index));
    }

    /**
     * 找到最后一个节点
     *
     * @return
     */
    private Node findLast() {
        if (this.head == null) return null;

        Node curr;

        for (curr = this.head; curr.next != null; curr = curr.next) ;

        return curr;
    }


    /**
     * 尾部添加多个
     */
    public void addLast(int first, int... rest) {
        Node sublist = new Node(first, null);
        Node curr = sublist;

        for (int i : rest) {
            curr.next = new Node(i, null);
            curr = curr.next;
        }

        Node last = findLast();
        if (last == null) {
            this.head = sublist;
            return;
        }

        last.next = sublist;
    }

    /**
     * 在链表末尾添加元素
     *
     * @param value
     */
    public void addLast(int value) {
        Node last = findLast();
        //链表为空 在头插入
        if (last == null) {
            addFirst(value);
            return;
        }

        last.next = new Node(value, null);
    }

    /**
     * 头部添加
     *
     * @param value
     */
    public void addFirst(int value) {
        this.head = new Node(value, head);
    }

    /**
     * while 循环遍历
     */
    public void loopWithWhile() {
        Node curr = this.head;

        while (curr != null) {
            System.out.println(curr.value);
            curr = curr.next;
        }
    }

    /**
     * for 循环遍历
     */
    public void loopWithFor() {
        for (Node curr = this.head; curr != null; curr = curr.next)
            System.out.println(curr.value);
    }

    /**
     * Consumer<T> 循环遍历
     */
    public void traverse(Consumer<Integer> consumer) {
        Node p = head;
        while (p != null) {
            consumer.accept(p.value);
            p = p.next;
        }
    }

    @Override
    public Iterator<Integer> iterator() {
        return new NodeIterator();
    }

    /**
     * 递归遍历
     */
    public void loop() {
        recursion(this.head);
    }

    private void recursion(Node curr) {
        if (curr == null) return;
        //正序
//        System.out.println(curr.value);
        recursion(curr.next);
        //逆序
        System.out.println(curr.value);

    }

    static class Node {
        int value;
        Node next;

        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

    private class NodeIterator implements Iterator<Integer> {
        Node p = head;

        @Override
        public boolean hasNext() {
            return p != null;
        }

        @Override
        public Integer next() {
            int value = p.value;
            p = p.next;
            return value;
        }

    }
    
}

单向链表（带哨兵）

观察之前单向链表的实现，发现每个方法内几乎都有判断是不是 head 这样的代码，能不能简化呢？

用一个不参与数据存储的特殊 Node 作为哨兵，它一般被称为哨兵或哑元，拥有哨兵节点的链表称为带头链表

1
2
3
4
public class SinglyLinkedListSentinel {
    // ...
    private Node head = new Node(Integer.MIN_VALUE, null);
}
  • 具体存什么值无所谓，因为不会用到它的值

加入哨兵节点后，代码会变得比较简单，先看几个工具方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class SinglyLinkedListSentinel {
    // ...
    
    // 根据索引获取节点
    private Node findNode(int index) {
        int i = -1;
        for (Node curr = this.head; curr != null; curr = curr.next, i++) {
            if (i == index) {
                return curr;
            }
        }
        return null;
    }
    
    // 获取最后一个节点
    private Node findLast() {
        Node curr;
        for (curr = this.head; curr.next != null; ) {
            curr = curr.next;
        }
        return curr;
    }
}
  • findNode 与之前类似，只是 i 初始值设置为 -1 对应哨兵，实际传入的 index 也是 $[-1, \infty)$
  • findLast 绝不会返回 null 了，就算没有其它节点，也会返回哨兵作为最后一个节点

这样，代码简化为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
public class SinglyLinkedListSentinel {
    // ...
    
    public void addLast(int value) {
        Node last = findLast();
        /*
        改动前
        if (last == null) {
            this.head = new Node(value, null);
            return;
        }
        */
        last.next = new Node(value, null);
    }
    
    public void insert(int index, int value) {
        /*
        改动前
        if (index == 0) {
            this.head = new Node(value, this.head);
            return;
        }
        */
        // index 传入 0 时，返回的是哨兵
        Node prev = findNode(index - 1);
        if (prev != null) {
            prev.next = new Node(value, prev.next);
        } else {
            throw illegalIndex(index);
        }
    }
    
    public void remove(int index) {
        /*
        改动前
        if (index == 0) {
            if (this.head != null) {
                this.head = this.head.next;
                return;
            } else {
                throw illegalIndex(index);
            }
        }
        */
        // index 传入 0 时，返回的是哨兵
        Node prev = findNode(index - 1);
        Node curr;
        if (prev != null && (curr = prev.next) != null) {
            prev.next = curr.next;
        } else {
            throw illegalIndex(index);
        }
    }
    
    public void addFirst(int value) {
        /*
        改动前
        this.head = new Node(value, this.head);
        */
		this.head.next = new Node(value, this.head.next);
        // 也可以视为 insert 的特例, 即 insert(0, value);
    }
}
  • 对于删除，前面说了【最后一个 if 块对应着至少得两个节点的情况】，现在有了哨兵，就凑足了两个节点

完整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
public class SinglyLinkedListSentinel {

    static class Node {
        int value;
        Node next;

        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

    //哨兵节点
    private Node head = new Node(Integer.MIN_VALUE, null);


    /**
     * 根据索引获取节点
     * count当不带哨兵因为有头结点所以从0开始，带了哨兵，初始值设置为 -1 对应哨兵
     * @param index
     * @return 查找到的节点
     */
    public Node findNode(int index) {
        int count = -1;
        for (Node curr = head; curr != null; curr = curr.next, count++) {
            if (index == count) {
                return curr;
            }
        }
        return null;
    }

    /**
     * 在链表末尾添加元素
     *
     * @param value
     */
    public void addLast(int value) {
        //找到最后一个节点
        Node last = findLast();
        //添加节点
        last.next = new Node(value, null);
    }

    // 获取最后一个节点 不用再判断头结点为空的情况
    private Node findLast() {
       Node curr;
        for (curr = this.head; curr.next != null; ) {
            curr = curr.next;
        }
        return curr;
    }

    /**
     * 尾部添加多个
     */
    public void addLast(int first, int... rest) {
        Node sublist = new Node(first, null);
        Node curr = sublist;

        for (int i : rest) {
            curr.next = new Node(i, null);
            curr = curr.next;
        }

        Node last = findLast();

        last.next = sublist;
    }

    /**
     * 头部添加
     *
     * @param value
     */
    public void addFirst(int value) {
      /*
        改动前
        this.head = new Node(value, this.head);
        */
        this.head.next = new Node(value, this.head.next);
        // 也可以视为 insert 的特例, 即 insert(0, value);
    }

    /**
     * 索引越界异常
     * @param index
     * @return
     */
    private IllegalArgumentException illegalIndex(int index) {
        return new IllegalArgumentException(String.format("index [%d] 不合法%n", index));
    }

    /**
     * 根据索引获取节点的值
     *
     * @param index
     * @return
     */
    public int get(int index) {
        Node node = findNode(index);
        if (node != null) {
            return node.value;
        }
        throw illegalIndex(index);
    }

    /**
     * 根据索引插入节点
     *
     * @param index
     * @param value
     */
    public void insert(int index, int value) {
        // index 传入 0 时，返回的是哨兵
        Node prev = findNode(index - 1); // 找到上一个节点
        if (prev !=null) {
            prev.next = new Node(value, prev.next);
        }else {
            throw  illegalIndex(index);
        }

    }

    /**
     * 根据索引移除
     * @param index
     */
    public void remove(int index) {
        Node prev = findNode(index - 1);
        Node curr;
        if (prev != null && (curr = prev.next) != null) {
            prev.next = curr.next;
        } else {
            throw illegalIndex(index);
        }
    }

    public  void traverse(Consumer<Integer> consumer) {
        Node p = head.next;
        while (p != null) {
            consumer.accept(p.value);
            p = p.next;
        }
    }

}

双向链表（带哨兵）

完整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
public class DoublyLinkedListSentinel implements Iterable<Integer> {

    private final Node head;
    private final Node tail;


    public DoublyLinkedListSentinel() {
        this.head = new Node(null, 666, null);
        this.tail = new Node(null, 888, null);

        head.next = tail;
        tail.prev = head;
    }

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node p = head.next;

            @Override
            public boolean hasNext() {
                return p != tail;
            }

            @Override
            public Integer next() {
                int value = p.value;
                p = p.next;
                return value;
            }
        };
    }


    public void addFirst(int value) {
        insert(0, value);
    }

    private Node findNode(int index) {
        int i = -1;//从头节点开始
        Node curr;
        for (curr = head; curr != tail; curr = curr.next, i++) {
            if (i == index) {
                return curr;
            }
        }
        return null;
    }

    private void insert(int index, int value) {
        //找到要插入的前一个位置
        Node prev = findNode(index - 1);

        if (prev == null) {
            throw illegalIndex(index);
        }

        Node next = prev.next;
        //插入
        Node added=new Node(prev,value,next);
        //重新指向
        prev.next=added;
        next.prev=added;
    }

    public void removeFirst() {
        remove(0);
    }

    private void remove(int index) {
        //找到要删除的前一个位置
        Node prev = findNode(index - 1);
        if (prev == null) {
            throw illegalIndex(index);
        }
        //需要用它指向删除后的下一个
        Node removed = prev.next;
        if (removed == tail) {
            throw illegalIndex(index);
        }
        Node next = removed.next;
        prev.next=next;
        next.prev=prev;
    }

    public void addLast(int value) {
        Node prev = tail.prev;
        //单向指向
        Node added = new Node(prev, value, tail);
        //添加的前一个和tail 指向
        prev.next = added;
        tail.prev = added;
    }

    public void removeLast() {
        Node removed = tail.prev;
        Node prev = removed.prev;
        if (prev == null) {
            throw illegalIndex(0);
        }
        //移除 removed 重新指向
        prev.next = tail;
        tail.prev = prev;
    }

    /**
     * 参数异常
     *
     * @param index
     * @return
     */
    private IllegalArgumentException illegalIndex(int index) {
        return new IllegalArgumentException(
                String.format("index [%d] 不合法%n", index));
    }


    static class Node {
        Node prev;
        int value;
        Node next;

        public Node(Node prev, int value, Node next) {
            this.prev = prev;
            this.value = value;
            this.next = next;
        }
    }
}

环形链表（带哨兵）

双向环形链表带哨兵，这时哨兵既作为头，也作为尾

image-20221229144232651

image-20221229143756065

image-20221229153338425

image-20221229154248800

参考实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
public class CircularLinkedList implements Iterable<Integer> {

    private final Node sentinel = new Node(null, -1, null); // 哨兵

    public CircularLinkedList() {
        //一个哨兵 哨兵指向自己
        sentinel.next = sentinel;
        sentinel.prev = sentinel;
    }

    public static void main(String[] args) {
        CircularLinkedList list = new CircularLinkedList();
        list.addFirst(1);
        list.addLast(2);
        list.addLast(3);
        list.addLast(4);

        Node nodeByValue = list.findNodeByValue(2);
        list.removeByValue(5);

        Iterator<Integer> iterator = list.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
    }

    /**
     * 添加到第一个
     *
     * @param value 待添加值
     */
    public void addFirst(int value) {
        Node next = sentinel.next;

        Node added = new Node(sentinel, value, next);

        sentinel.next = added;
        next.prev = added;

    }

    /**
     * 添加到最后一个
     *
     * @param value 待添加值
     */
    public void addLast(int value) {

        Node prev = sentinel.prev;

        Node added = new Node(prev, value, sentinel);

        prev.next = added;
        sentinel.prev = added;
    }

    /**
     * 删除第一个
     */
    public void removeFirst() {
        Node removed = sentinel.next;
        if (removed == sentinel) {
            throw new IllegalArgumentException("非法");
        }
        Node a = sentinel;
        Node b = removed.next;
        a.next = b;
        b.prev = a;
    }

    /**
     * 删除最后一个
     */
    public void removeLast() {
        Node removed = sentinel.prev;
        if (removed == sentinel) {
            throw new IllegalArgumentException("非法");
        }

        Node a = removed.prev;
        Node b = sentinel;
        a.next = b;
        b.prev = a;
    }

    /**
     * 根据值删除节点
     * <p>假定 value 在链表中作为 key, 有唯一性</p>
     *
     * @param value 待删除值
     */
    public void removeByValue(int value) {
        Node removed = findNodeByValue(value);
        if (removed!=null){
            Node prev = removed.prev;
            Node next = removed.next;
            prev.next=next;
            next.prev=prev;
        }
        throw new IllegalArgumentException(value+"不存在！");
    }

    private Node findNodeByValue(int value) {
        for (Node p = sentinel.next; p != sentinel; p = p.next) {
            if (p.value == value) {
                return p;
            }
        }
        return null;
    }


    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node p = sentinel.next;

            @Override
            public boolean hasNext() {
                return p != sentinel;
            }

            @Override
            public Integer next() {
                int value = p.value;
                p = p.next;
                return value;
            }
        };
    }

    static class Node {
        Node prev; // 上一个节点指针
        int value; // 值
        Node next; // 下一个节点指针

        public Node(Node prev, int value, Node next) {
            this.prev = prev;
            this.value = value;
            this.next = next;
        }

    }
}

2.3 递归

概述

定义

计算机科学中，递归是一种解决计算问题的方法，其中解决方案取决于同一类问题的更小子集

In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem.

比如单链表递归遍历的例子：

1
2
3
4
5
6
7
8
void f(Node node) {
    if(node == null) {
        return;
    }
    println("before:" + node.value)
    f(node.next);
    println("after:" + node.value)
}

说明：

  1. 自己调用自己，如果说每个函数对应着一种解决方案，自己调用自己意味着解决方案是一样的（有规律的）
  2. 每次调用，函数处理的数据会较上次缩减（子集），而且最后会缩减至无需继续递归
  3. 内层函数调用（子集处理）完成，外层函数才能算调用完成

原理

假设链表中有 3 个节点，value 分别为 1，2，3，以上代码的执行流程就类似于下面的伪码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 1 -> 2 -> 3 -> null  f(1)

void f(Node node = 1) {
    println("before:" + node.value) // 1
    void f(Node node = 2) {
        println("before:" + node.value) // 2
        void f(Node node = 3) {
            println("before:" + node.value) // 3
            void f(Node node = null) {
                if(node == null) {
                    return;
                }
            }
            println("after:" + node.value) // 3
        }
        println("after:" + node.value) // 2
    }
    println("after:" + node.value) // 1
}

思路

  1. 确定能否使用递归求解
  2. 推导出递推关系，即父问题与子问题的关系，以及递归的结束条件

例如之前遍历链表的递推关系为
$$
f(n) =
\begin{cases}
停止& n = null \
f(n.next) & n \neq null
\end{cases}
$$

  • 深入到最里层叫做递
  • 从最里层出来叫做归
  • 在递的过程中，外层函数内的局部变量（以及方法参数）并未消失，归的时候还可以用到

单路递归 Single Recursion

E01. 阶乘

用递归方法求阶乘

  • 阶乘的定义 $n!= 1⋅2⋅3⋯(n-2)⋅(n-1)⋅n$，其中 $n$ 为自然数，当然 $0! = 1$

  • 递推关系

$$
f(n) =
\begin{cases}
1 & n = 1\
n * f(n-1) & n > 1
\end{cases}
$$

代码

1
2
3
4
5
6
private static int f(int n) {
    if (n == 1) {
        return 1;
    }
    return n * f(n - 1);
}

拆解伪码如下，假设 n 初始值为 3

1
2
3
4
5
6
7
8
9
f(int n = 3) { // 解决不了,递
    return 3 * f(int n = 2) { // 解决不了,继续递
        return 2 * f(int n = 1) {
            if (n == 1) { // 可以解决, 开始归
                return 1;
            }
        }
    }
}

E02. 反向打印字符串

用递归反向打印字符串，n 为字符在整个字符串 str 中的索引位置

  • 递：n 从 0 开始，每次 n + 1，一直递到 n == str.length() - 1
  • 归：从 n == str.length() 开始归，从归打印，自然是逆序的

递推关系
$$
f(n) =
\begin{cases}
停止 & n = str.length() \
f(n+1) & 0 \leq n \leq str.length() - 1
\end{cases}
$$
代码为

1
2
3
4
5
6
7
public static void reversePrint(String str, int index) {
    if (index == str.length()) {
        return;
    }
    reversePrint(str, index + 1);
    System.out.println(str.charAt(index));
}

拆解伪码如下，假设字符串为 “abc”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void reversePrint(String str, int index = 0) {
    void reversePrint(String str, int index = 1) {
        void reversePrint(String str, int index = 2) {
            void reversePrint(String str, int index = 3) { 
                if (index == str.length()) {
                    return; // 开始归
                }
            }
            System.out.println(str.charAt(index)); // 打印 c
        }
        System.out.println(str.charAt(index)); // 打印 b
    }
    System.out.println(str.charAt(index)); // 打印 a
}

多路递归 Multi Recursion

E01. 斐波那契数列

  • 之前的例子是每个递归函数只包含一个自身的调用，这称之为 single recursion
  • 如果每个递归函数例包含多个自身调用，称之为 multi recursion

递推关系
$$
f(n) =
\begin{cases}
0 & n=0 \
1 & n=1 \
f(n-1) + f(n-2) & n>1
\end{cases}
$$

下面的表格列出了数列的前几项

F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13
0 1 1 2 3 5 8 13 21 34 55 89 144 233

实现

1
2
3
4
5
6
7
8
9
public static int f(int n) {
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    return f(n - 1) + f(n - 2);
}

执行流程

  • 绿色代表正在执行（对应递），灰色代表执行结束（对应归）
  • 递不到头，不能归，对应着深度优先搜索

时间复杂度

  • 递归的次数也符合斐波那契规律，$2 * f(n+1)-1$
  • 时间复杂度推导过程
    • 斐波那契通项公式 $f(n) = \frac{1}{\sqrt{5}}*({\frac{1+\sqrt{5}}{2}}^n - {\frac{1-\sqrt{5}}{2}}^n)$
    • 简化为：$f(n) = \frac{1}{2.236}*({1.618}^n - {(-0.618)}^n)$
    • 带入递归次数公式 $2\frac{1}{2.236}({1.618}^{n+1} - {(-0.618)}^{n+1})-1$
    • 时间复杂度为 $\Theta(1.618^n)$
  1. 更多 Fibonacci 参考[^8][^9][^10]
  2. 以上时间复杂度分析，未考虑大数相加的因素

变体1 - 兔子问题[^8]

image-20221110155655827

  • 第一个月，有一对未成熟的兔子（黑色，注意图中个头较小）
  • 第二个月，它们成熟
  • 第三个月，它们能产下一对新的小兔子（蓝色）
  • 所有兔子遵循相同规律，求第 $n$ 个月的兔子数

分析

兔子问题如何与斐波那契联系起来呢？设第 n 个月兔子数为 $f(n)$

  • $f(n)$ = 上个月兔子数 + 新生的小兔子数
  • 而【新生的小兔子数】实际就是【上个月成熟的兔子数】
  • 因为需要一个月兔子就成熟，所以【上个月成熟的兔子数】也就是【上上个月的兔子数】
  • 上个月兔子数，即 $f(n-1)$
  • 上上个月的兔子数，即 $f(n-2)$

因此本质还是斐波那契数列，只是从其第一项开始

变体2 - 青蛙爬楼梯

  • 楼梯有 $n$ 阶
  • 青蛙要爬到楼顶，可以一次跳一阶，也可以一次跳两阶
  • 只能向上跳，问有多少种跳法

分析

n 跳法 规律
1 (1) 暂时看不出
2 (1,1) (2) 暂时看不出
3 (1,1,1) (1,2) (2,1) 暂时看不出
4 (1,1,1,1) (1,2,1) (2,1,1)
(1,1,2) (2,2)		 最后一跳，跳一个台阶的，基于f(3)
最后一跳，跳两个台阶的，基于f(2)
5 … …

实现(Leetcode 运行会超时 待优化)

1
2
3
4
5
6
7
8
class Solution {
    public int climbStairs(int n) {
            if(n==1) return 1;
            if(n==2) return 2;
            if(n==3) return 3;
            return climbStairs(n-1)+climbStairs(n-2);
    }
}

递归优化-记忆法

上述代码存在很多重复的计算，例如求 $f(5)$ 递归分解过程

image-20221207092417933

可以看到（颜色相同的是重复的）：

  • $f(3)$ 重复了 2 次
  • $f(2)$ 重复了 3 次
  • $f(1)$ 重复了 5 次
  • $f(0)$ 重复了 3 次

随着 $n$ 的增大，重复次数非常可观，如何优化呢？

Memoization 记忆法（也称备忘录）是一种优化技术，通过存储函数调用结果（通常比较昂贵），当再次出现相同的输入（子问题）时，就能实现加速效果，改进后的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void main(String[] args) {
    int n = 13;
    int[] cache = new int[n + 1];
    Arrays.fill(cache, -1);
    cache[0] = 0;
    cache[1] = 1;
    System.out.println(f(cache, n));
}

public static int f(int[] cache, int n) {
    if (cache[n] != -1) {
        return cache[n];
    }

    cache[n] = f(cache, n - 1) + f(cache, n - 2);
    return cache[n];
}

优化后的图示，只要结果被缓存，就不会执行其子问题

image-20221213173225807

  • 改进后的时间复杂度为 $O(n)$
  • 请自行验证改进后的效果
  • 请自行分析改进后的空间复杂度

注意

  1. 记忆法是动态规划的一种情况，强调的是自顶向下的解决
  2. 记忆法的本质是空间换时间

递归优化-尾递归

爆栈

用递归做 $n + (n-1) + (n-2) … + 1$

1
2
3
4
5
6
public static long sum(long n) {
    if (n == 1) {
        return 1;
    }
    return n + sum(n - 1);
}

在我的机器上 $n = 12000$ 时，爆栈了

1
2
3
4
5
6
7
Exception in thread "main" java.lang.StackOverflowError
	at Test.sum(Test.java:10)
	at Test.sum(Test.java:10)
	at Test.sum(Test.java:10)
	at Test.sum(Test.java:10)
	at Test.sum(Test.java:10)
	...

为什么呢？

  • 每次方法调用是需要消耗一定的栈内存的，这些内存用来存储方法参数、方法内局部变量、返回地址等等
  • 方法调用占用的内存需要等到方法结束时才会释放
  • 而递归调用我们之前讲过，不到最深不会回头，最内层方法没完成之前，外层方法都结束不了
    • 例如，$sum(3)$ 这个方法内有个需要执行 $3 + sum(2)$，$sum(2)$ 没返回前，加号前面的 $3$ 不能释放
    • 看下面伪码
1
2
3
4
5
6
7
long sum(long n = 3) {
    return 3 + long sum(long n = 2) {
        return 2 + long sum(long n = 1) {
            return 1;
        }
    }
}

尾调用

如果函数的最后一步是调用一个函数，那么称为尾调用，例如

1
2
3
function a() {
    return b()
}

下面三段代码不能叫做尾调用

1
2
3
4
function a() {
    const c = b()
    return c
}
  • 因为最后一步并非调用函数
1
2
3
function a() {
    return b() + 1
}
  • 最后一步执行的是加法
1
2
3
function a(x) {
    return b() + x
}
  • 最后一步执行的是加法

一些语言[^11]的编译器能够对尾调用做优化，例如

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function a() {
    // 做前面的事
    return b() 
}

function b() {
    // 做前面的事
    return c()
}

function c() {
    return 1000
}

a()

没优化之前的伪码

1
2
3
4
5
6
7
function a() {
    return function b() {
        return function c() {
            return 1000
        }
    }
}

优化后伪码如下

1
2
3
a()
b()
c()

为何尾递归才能优化？

调用 a 时

  • a 返回时发现：没什么可留给 b 的，将来返回的结果 b 提供就可以了，用不着我 a 了，我的内存就可以释放

调用 b 时

  • b 返回时发现：没什么可留给 c 的，将来返回的结果 c 提供就可以了，用不着我 b 了，我的内存就可以释放

如果调用 a 时

  • 不是尾调用，例如 return b() + 1，那么 a 就不能提前结束，因为它还得利用 b 的结果做加法

尾递归

尾递归是尾调用的一种特例，也就是最后一步执行的是同一个函数

尾递归避免爆栈

安装 Scala

image-20221111122709227

Scala 入门

1
2
3
4
5
object Main {
  def main(args: Array[String]): Unit = {
    println("Hello Scala")
  }
}
  • Scala 是 java 的近亲，java 中的类都可以拿来重用
  • 类型是放在变量后面的
  • Unit 表示无返回值，类似于 void
  • 不需要以分号作为结尾，当然加上也对

还是先写一个会爆栈的函数

1
2
3
4
5
6
def sum(n: Long): Long = {
    if (n == 1) {
        return 1
    }
    return n + sum(n - 1)
}
  • Scala 最后一行代码若作为返回值，可以省略 return

不出所料，在 $n = 11000$ 时，还是出了异常

1
2
3
4
5
6
7
8
println(sum(11000))

Exception in thread "main" java.lang.StackOverflowError
	at Main$.sum(Main.scala:25)
	at Main$.sum(Main.scala:25)
	at Main$.sum(Main.scala:25)
	at Main$.sum(Main.scala:25)
	...

这是因为以上代码，还不是尾调用，要想成为尾调用，那么：

  1. 最后一行代码，必须是一次函数调用
  2. 内层函数必须摆脱与外层函数的关系，内层函数执行后不依赖于外层的变量或常量
1
2
3
4
5
6
def sum(n: Long): Long = {
    if (n == 1) {
        return 1
    }
    return n + sum(n - 1)  // 依赖于外层函数的 n 变量
}

如何让它执行后就摆脱对 n 的依赖呢？

  • 不能等递归回来再做加法，那样就必须保留外层的 n
  • 把 n 当做内层函数的一个参数传进去，这时 n 就属于内层函数了
  • 传参时就完成累加, 不必等回来时累加
1
sum(n - 1, n + 累加器)

改写后代码如下

1
2
3
4
5
6
7
@tailrec
def sum(n: Long, accumulator: Long): Long = {
    if (n == 1) {
        return 1 + accumulator
    } 
    return sum(n - 1, n + accumulator)
}
  • accumulator 作为累加器
  • @tailrec 注解是 scala 提供的，用来检查方法是否符合尾递归
  • 这回 sum(10000000, 0) 也没有问题，打印 50000005000000

执行流程如下，以伪码表示 $sum(4, 0)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 首次调用
def sum(n = 4, accumulator = 0): Long = {
    return sum(4 - 1, 4 + accumulator)
}

// 接下来调用内层 sum, 传参时就完成了累加, 不必等回来时累加，当内层 sum 调用后，外层 sum 空间没必要保留
def sum(n = 3, accumulator = 4): Long = {
    return sum(3 - 1, 3 + accumulator)
}

// 继续调用内层 sum
def sum(n = 2, accumulator = 7): Long = {
    return sum(2 - 1, 2 + accumulator)
}

// 继续调用内层 sum, 这是最后的 sum 调用完就返回最后结果 10, 前面所有其它 sum 的空间早已释放
def sum(n = 1, accumulator = 9): Long = {
    if (1 == 1) {
        return 1 + accumulator
    }
}

本质上，尾递归优化是将函数的递归调用，变成了函数的循环调用

改循环避免爆栈

1
2
3
4
5
6
7
8
public static void main(String[] args) {
    long n = 100000000;
    long sum = 0;
    for (long i = n; i >= 1; i--) {
        sum += i;
    }
    System.out.println(sum);
}

递归时间复杂度-Master theorem[^14]

若有递归式
$$
T(n) = aT(\frac{n}{b}) + f(n)
$$
其中

  • $T(n)$ 是问题的运行时间，$n$ 是数据规模
  • $a$ 是子问题个数
  • $T(\frac{n}{b})$ 是子问题运行时间，每个子问题被拆成原问题数据规模的 $\frac{n}{b}$
  • $f(n)$ 是除递归外执行的计算

令 $x = \log_{b}{a}$，即 $x = \log_{子问题缩小倍数}{子问题个数}$

那么
$$
T(n) =
\begin{cases}
\Theta(n^x) & f(n) = O(n^c) 并且 c \lt x\
\Theta(n^x\log{n}) & f(n) = \Theta(n^x)\
\Theta(n^c) & f(n) = \Omega(n^c) 并且 c \gt x
\end{cases}
$$

例1

$T(n) = 2T(\frac{n}{2}) + n^4$

  • 此时 $x = 1 < 4$，由后者决定整个时间复杂度 $\Theta(n^4)$
  • 如果觉得对数不好算，可以换为求【$b$ 的几次方能等于 $a$】

例2

$T(n) = T(\frac{7n}{10}) + n$

  • $a=1, b=\frac{10}{7}, x=0, c=1$
  • 此时 $x = 0 < 1$，由后者决定整个时间复杂度 $\Theta(n)$

例3

$T(n) = 16T(\frac{n}{4}) + n^2$

  • $a=16, b=4, x=2, c=2$
  • 此时 $x=2 = c$，时间复杂度 $\Theta(n^2 \log{n})$

例4

$T(n)=7T(\frac{n}{3}) + n^2$

  • $a=7, b=3, x=1.?, c=2$
  • 此时 $x = \log_{3}{7} < 2$，由后者决定整个时间复杂度 $\Theta(n^2)$

例5

$T(n) = 7T(\frac{n}{2}) + n^2$

  • $a=7, b=2, x=2.?, c=2$
  • 此时 $x = log_2{7} > 2$，由前者决定整个时间复杂度 $\Theta(n^{\log_2{7}})$

例6

$T(n) = 2T(\frac{n}{4}) + \sqrt{n}$

  • $a=2, b=4, x = 0.5, c=0.5$
  • 此时 $x = 0.5 = c$，时间复杂度 $\Theta(\sqrt{n}\ \log{n})$

例7. 二分查找递归

1
2
3
4
5
6
7
8
9
10
11
12
13
int f(int[] a, int target, int i, int j) {
    if (i > j) {
        return -1;
    }
    int m = (i + j) >>> 1;
    if (target < a[m]) {
        return f(a, target, i, m - 1);
    } else if (a[m] < target) {
        return f(a, target, m + 1, j);
    } else {
        return m;
    }
}
  • 子问题个数 $a = 1$
  • 子问题数据规模缩小倍数 $b = 2$
  • 除递归外执行的计算是常数级 $c=0$

$T(n) = T(\frac{n}{2}) + n^0$

  • 此时 $x=0 = c$，时间复杂度 $\Theta(\log{n})$

例8. 归并排序递归

1
2
3
4
5
6
7
8
9
10
11
12
13
void split(B[], i, j, A[])
{
    if (j - i <= 1)                    
        return;                                
    m = (i + j) / 2;             
    
    // 递归
    split(A, i, m, B);  
    split(A, m, j, B); 
    
    // 合并
    merge(B, i, m, j, A);
}
  • 子问题个数 $a=2$
  • 子问题数据规模缩小倍数 $b=2$
  • 除递归外，主要时间花在合并上，它可以用 $f(n) = n$ 表示

$T(n) = 2T(\frac{n}{2}) + n$

  • 此时 $x=1=c$，时间复杂度 $\Theta(n\log{n})$

例9. 快速排序递归

1
2
3
4
5
6
7
8
9
10
algorithm quicksort(A, lo, hi) is 
  if lo >= hi || lo < 0 then 
    return
  
  // 分区
  p := partition(A, lo, hi) 
  
  // 递归
  quicksort(A, lo, p - 1) 
  quicksort(A, p + 1, hi)
  • 子问题个数 $a=2$
  • 子问题数据规模缩小倍数
    • 如果分区分的好，$b=2$
    • 如果分区没分好，例如分区1 的数据是 0，分区 2 的数据是 $n-1$
  • 除递归外，主要时间花在分区上，它可以用 $f(n) = n$ 表示

情况1 - 分区分的好

$T(n) = 2T(\frac{n}{2}) + n$

  • 此时 $x=1=c$，时间复杂度 $\Theta(n\log{n})$

情况2 - 分区没分好

$T(n) = T(n-1) + T(1) + n$

  • 此时不能用主定理求解

递归时间复杂度-展开求解

像下面的递归式，都不能用主定理求解

例1 - 递归求和

1
2
3
4
5
6
long sum(long n) {
    if (n == 1) {
        return 1;
    }
    return n + sum(n - 1);
}

$T(n) = T(n-1) + c$，$T(1) = c$

下面为展开过程

$T(n) = T(n-2) + c + c$

$T(n) = T(n-3) + c + c + c$

…

$T(n) = T(n-(n-1)) + (n-1)c$

  • 其中 $T(n-(n-1))$ 即 $T(1)$
  • 带入求得 $T(n) = c + (n-1)c = nc$

时间复杂度为 $O(n)$

例2 - 递归冒泡排序

1
2
3
4
5
6
7
8
9
10
11
void bubble(int[] a, int high) {
    if(0 == high) {
        return;
    }
    for (int i = 0; i < high; i++) {
        if (a[i] > a[i + 1]) {
            swap(a, i, i + 1);
        }
    }
    bubble(a, high - 1);
}

$T(n) = T(n-1) + n$，$T(1) = c$

下面为展开过程

$T(n) = T(n-2) + (n-1) + n$

$T(n) = T(n-3) + (n-2) + (n-1) + n$

…

$T(n) = T(1) + 2 + … + n = T(1) + (n-1)\frac{2+n}{2} = c + \frac{n^2}{2} + \frac{n}{2} -1$

时间复杂度 $O(n^2)$

注：

  • 等差数列求和为 $个数*\frac{\vert首项-末项\vert}{2}$

例3 - 递归快排

快速排序分区没分好的极端情况

$T(n) = T(n-1) + T(1) + n$，$T(1) = c$

$T(n) = T(n-1) + c + n$

下面为展开过程

$T(n) = T(n-2) + c + (n-1) + c + n$

$T(n) = T(n-3) + c + (n-2) + c + (n-1) + c + n$

…

$T(n) = T(n-(n-1)) + (n-1)c + 2+…+n = \frac{n^2}{2} + \frac{2cn+n}{2} -1$

时间复杂度 $O(n^2)$

不会推导的同学可以进入 https://www.wolframalpha.com/

  • 例1 输入 f(n) = f(n - 1) + c, f(1) = c
  • 例2 输入 f(n) = f(n - 1) + n, f(1) = c
  • 例3 输入 f(n) = f(n - 1) + n + c, f(1) = c

附录

参考文章

[^1]: “Definition of ALGORITHM”. Merriam-Webster Online Dictionary. Archived from the original on February 14, 2020. Retrieved November 14, 2019.
[^2]: Introduction to Algorithm 中文译作《算法导论》
[^3]: 主要参考文档 https://en.wikipedia.org/wiki/Binary_search_algorithm
[^4]: 图片及概念均摘自 Introduction to Algorithm 4th，3.1节，3.2 节
[^5]: 图片引用自 wikipedia linkedlist 条目，https://en.wikipedia.org/wiki/Linked_list

[^6]: 也称为 Pascal’s triangle https://en.wikipedia.org/wiki/Pascal%27s_triangle

[^7]: 递归求解斐波那契数列的时间复杂度——几种简洁证明 - 知乎 (zhihu.com)
[^8]: Fibonacci 介绍：https://en.wikipedia.org/wiki/Fibonacci_number
[^9]: 几种计算Fibonacci数列算法的时间复杂度比较 - 知乎 (zhihu.com)
[^10]: 几种斐波那契数列算法比较 Fast Fibonacci algorithms (nayuki.io)

[^11]: 我知道的有 C++，Scala
[^12]: jdk 版本有关，64 位 jdk，按 8 字节对齐
[^13]: 汉诺塔图片资料均来自 https://en.wikipedia.org/wiki/Tower_of_Hanoi
[^14]: 与主定理类似的还有 Akra–Bazzi method，https://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method

[^15]: 龟兔赛跑动画来自于 Floyd’s Hare and Tortoise Algorithm Demo - One Step! Code (onestepcode.com)

[^16]: Josephus problem 主要参考 https://en.wikipedia.org/wiki/Josephus_problem

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

快来参与讨论吧~