|
1 | 1 | <!-- GFM-TOC --> |
2 | 2 | * [一、算法分析](#一算法分析) |
3 | | - * [函数转换](#函数转换) |
4 | 3 | * [数学模型](#数学模型) |
5 | 4 | * [ThreeSum](#threesum) |
6 | 5 | * [倍率实验](#倍率实验) |
|
34 | 33 |
|
35 | 34 | # 一、算法分析 |
36 | 35 |
|
37 | | -## 函数转换 |
38 | | - |
39 | | -指数函数可以转换为线性函数，从而在函数图像上显示的更直观。例如 |
40 | | - |
41 | | -<div align="center"><img src="https://latex.codecogs.com/gif.latex?T(N)=aN^3"/></div> <br> |
42 | | - |
43 | | -可以在其两端同时取对数，得到： |
44 | | - |
45 | | -<div align="center"><img src="https://latex.codecogs.com/gif.latex?log(T(N))=3logN+loga"/></div> <br> |
46 | | - |
47 | | -<div align="center"> <img src="../pics//a9098783-c24a-45b2-a226-725a59b6768e.png" width="800"/> </div><br> |
48 | | - |
49 | 36 | ## 数学模型 |
50 | 37 |
|
51 | 38 | ### 1. 近似 |
52 | 39 |
|
53 | | -使用 \~f(N) 来表示所有随着 N 的增大除以 f(N) 的结果趋近于 1 的函数，例如 N<sup>3</sup>/6-N<sup>2</sup>/2+N/3 \~ N<sup>3</sup>/6。 |
54 | | - |
55 | | -<div align="center"> <img src="../pics//81eb9879-40f2-421a-87de-2b953cfe8c32.png" width="800"/> </div><br> |
| 40 | +N<sup>3</sup>/6-N<sup>2</sup>/2+N/3 \~ N<sup>3</sup>/6。使用 \~f(N) 来表示所有随着 N 的增大除以 f(N) 的结果趋近于 1 的函数。 |
56 | 41 |
|
57 | 42 | ### 2. 增长数量级 |
58 | 43 |
|
59 | | -增长数量级将算法与它的实现隔离开来，一个算法的增长数量级为 N<sup>3</sup> 与它是否用 Java 实现，是否运行于特定计算机上无关。 |
60 | | - |
61 | | -<div align="center"> <img src="../pics//051760ba-e658-401f-9a1c-15adcb405191.png" width="800"/> </div><br> |
| 44 | +N<sup>3</sup>/6-N<sup>2</sup>/2+N/3 的增长数量级为 O(N<sup>3</sup>)。增长数量级将算法与它的实现隔离开来，一个算法的增长数量级为 O(N<sup>3</sup>)与它是否用 Java 实现，是否运行于特定计算机上无关。 |
62 | 45 |
|
63 | 46 | ### 3. 内循环 |
64 | 47 |
|
@@ -91,7 +74,7 @@ public class ThreeSum { |
91 | 74 | } |
92 | 75 | ``` |
93 | 76 |
|
94 | | -该算法的内循环为`if (a[i] + a[j] + a[k] == 0)`语句，总共执行的次数为 N(N-1)(N-2) = N<sup>3</sup>/6 - N<sup>2</sup>/2 + N/3，因此它的近似执行次数为 \~N<sup>3</sup>/6，增长数量级为 N<sup>3</sup>。 |
| 77 | +该算法的内循环为 if (a[i] + a[j] + a[k] == 0) 语句，总共执行的次数为 N(N-1)(N-2) = N<sup>3</sup>/6 - N<sup>2</sup>/2 + N/3，因此它的近似执行次数为 \~N<sup>3</sup>/6，增长数量级为 N<sup>3</sup>。 |
95 | 78 |
|
96 | 79 | <font size=4> **改进** </font></br> |
97 | 80 |
|
@@ -125,7 +108,14 @@ public class ThreeSumFast { |
125 | 108 |
|
126 | 109 | 例如对于暴力方法的 ThreeSum 算法，近似时间为 \~N<sup>3</sup>/6。进行如下实验：多次运行该算法，每次取的 N 值为前一次的两倍，统计每次执行的时间，并统计本次运行时间与前一次运行时间的比值，得到如下结果： |
127 | 110 |
|
128 | | -<div align="center"> <img src="../pics//2093ccfa-e560-44f3-84c7-487d66451708.png" width="300"/> </div><br> |
| 111 | +| N | Time | Ratio | |
| 112 | +| --- | --- | --- | |
| 113 | +| 250 | 0.0 | 2.7 | |
| 114 | +| 500 | 0.0 | 4.8 | |
| 115 | +| 1000 | 0.1 | 6.9 | |
| 116 | +| 2000 | 0.8 | 7.7 | |
| 117 | +| 4000 | 6.4 | 8.0 | |
| 118 | +| 8000 | 51.1 | 8.0 | |
129 | 119 |
|
130 | 120 | 可以看到，T(2N)/T(N) \~ 2<sup>3</sup>，因此可以确定 T(N) \~ aN<sup>3</sup>logN。 |
131 | 121 |
|
@@ -155,9 +145,7 @@ public class ThreeSumFast { |
155 | 145 |
|
156 | 146 | ## 栈 |
157 | 147 |
|
158 | | -first-in-last-out(FILO) |
159 | | - |
160 | | -<div align="center"> <img src="../pics//cc7bfdeb-452e-4fae-9bc8-323338b0dedb.png" width="400"/> </div><br> |
| 148 | +> First-In-Last-Out |
161 | 149 |
|
162 | 150 | <font size=4> **1. 数组实现** </font></br> |
163 | 151 |
|
@@ -220,12 +208,6 @@ public class ResizeArrayStack<Item> implements Iterable<Item> { |
220 | 208 | } |
221 | 209 | ``` |
222 | 210 |
|
223 | | -上面实现使用了泛型，Java 不能直接创建泛型数组，只能使用转型来创建。 |
224 | | - |
225 | | -```java |
226 | | -Item[] arr = (Item[]) new Object[N]; |
227 | | -``` |
228 | | - |
229 | 211 | <font size=4> **2. 链表实现** </font></br> |
230 | 212 |
|
231 | 213 | 需要使用链表的头插法来实现，因为头插法中最后压入栈的元素在链表的开头，它的 next 指针指向前一个压入栈的元素，在弹出元素使就可以通过 next 指针遍历到前一个压入栈的元素从而让这个元素称为新的栈顶元素。 |
@@ -265,11 +247,10 @@ public class Stack<Item> { |
265 | 247 | } |
266 | 248 | } |
267 | 249 | ``` |
268 | | -## 队列 |
269 | 250 |
|
270 | | -first-in-first-out(FIFO) |
| 251 | +## 队列 |
271 | 252 |
|
272 | | -<div align="center"> <img src="../pics//d9efd6bd-3f34-497e-911c-16d5ea38ce88.png" width="400"/> </div><br> |
| 253 | +> First-In-First-Out |
273 | 254 |
|
274 | 255 | 下面是队列的链表实现，需要维护 first 和 last 节点指针，分别指向队首和队尾。 |
275 | 256 |
|
|
0 commit comments