算法系列：
概览：
1，常数操作，固定时间的操作，执行时间和数据量无关
2，时间复杂度，一个和数据量有关、只要高阶项、不要低阶项、不要常数项的操作次数表达式
举例：选择、冒泡、插入
3，严格固定流程的算法，一定强调最差情况！比如插入排序
4，算法流程上利用随机行为作为重要部分的，要看平均或者期望的时间复杂度，因为最差的时间复杂度无意义
用生成相邻值不同的数组来说明
5，算法流程上利用随机行为作为重要部分的，还有随机快速排序（【必备】课）、跳表（【扩展】课）
也只在乎平均或者期望的时间复杂度，因为最差的时间复杂度无意义
6，时间复杂度的内涵：描述算法运行时间和数据量大小的关系，而且当数据量很大很大时，这种关系相当的本质，并且排除了低阶项、常数时间的干扰
7，空间复杂度，强调额外空间；常数项时间，放弃理论分析、选择用实验来确定，因为不同常数操作的时间不同
8，什么叫最优解，先满足时间复杂度最优，然后尽量少用空间的解
9，时间复杂度的均摊，用动态数组的扩容来说明（等比数列、均摊的意义）
并查集、单调队列、单调栈、哈希表等结构，均有这个概念。这些内容【必备】课都会讲
10，不要用代码结构来判断时间复杂度，比如只有一个while循环的冒泡排序，其实时间复杂度O(N^2)
11，不要用代码结构来判断时间复杂度，比如：N/1 + N/2 + N/3 + … + N/N，这个流程的时间复杂度是\(O(N * logN)\)，著名的调和级数
12，时间复杂度只能是对算法流程充分理解才能分析出来，而不是简单的看代码结构！这是一个常见的错误！
甚至有些算法的实现用了多层循环嵌套，但时间复杂度是O(N)的。在【必备】课程里会经常见到
13，常见复杂度一览：
\[O(1) \ O(logN) \ O(N) \ O(N*logN) \ O(N^2) \ … \ O(N^k) \ O(2^N) \ … \ O(k^N) \ … \ O(N!)\]14，时间复杂度非常重要，可以直接判断某个方法能不能通过一个题目，根据数据量猜解法，【必备】课都会讲
15，整套课会讲很多算法和数据结构，也会见到很多的时间复杂度的表达，持续看课即可
补充1: 常数时间
常数操作是指无论输入数据量有多大，操作的执行时间都保持不变，用时间复杂度表示为 O(1)。这些操作通常是基本的、底层的计算或访问。
例如：
1
2
3
4
5
int a = 5; // 赋值操作，O(1)
int b = a + 3; // 简单算术运算，O(1)
int[] arr = new int[10];
int value = arr[0]; // 数组索引访问，O(1)
System.out.println("Hello"); // 输出操作，O(1)
上面如果变成
a = 10亿，b = a + 1亿还是常数时间。上面如果变成
arr[100000]，和arr[10]一样，也是常数时间，因为是算的偏移。
补充2：严格固定流程的算法，一定强调最差情况
例如插入排序。对于下面2个序列：
1
2
[1, 2, 3, 4, 5]
[5, 4, 3, 2, 1]
显然上面要快，也就是说插入排序最佳的时间复杂度是\(O(N)\)，最差是\(O(N^2)\)
无论数据如何，流程固定，最差情况是性能瓶颈
补充3：利用随机行为的算法：分析平均/期望时间复杂度
对于引入随机行为的算法（如快速排序），最差情况（如每次选到最大/最小值）发生的概率极低，分析其平均时间复杂度或期望时间复杂度更有意义。
示例：生成相邻值不同的数组
假设我们要生成一个长度为 n 的数组，保证相邻元素不同（例如 [1, 2, 1, 3, 2]），可以用随机行为来构造。
如果按照最差情况去估计，那么比如第一个数是3，第二个数最差情况永远生成3，那么循环次数可能是无限的（理论上无上界），时间复杂度无意义，这么估计就没有意义了，这么估计也不具有代表性。
1
2
3
4
5
6
7
8
9
10
11
12
13
import java.util.Random;
public int[] generateAlternatingArray(int n) {
Random rand = new Random();
int[] arr = new int[n];
arr[0] = rand.nextInt(10); // 第一个数随机，范围 0-9
for (int i = 1; i < n; i++) {
do {
arr[i] = rand.nextInt(10); // 随机生成，直到与前一个不同
} while (arr[i] == arr[i - 1]);
}
return arr;
}
期望时间复杂度：
- 假设随机范围为 k（这里 k=10），相邻值相同的概率为
1/k。 - 每次循环的期望尝试次数为几何分布的期望：
1/(1-1/k)，即k/(k-1)。 - 对于 k=10，期望尝试约 10/9 ≈ 1.11 次。
- 总期望时间：
n * k/(k-1)，忽略常数项为 \(O(n)\)。均摊到每一个就是\(O(1)\)
补充4：时间复杂度的均摊分析：以动态数组扩容为例
均摊分析（Amortized Analysis） 是一种评估算法在多次操作后的平均时间复杂度的技术。它特别适用于某些操作偶尔会有高成本，但总体成本分布较为均匀的场景。动态数组（Dynamic Array）的扩容是一个经典例子。
动态数组（如 Java 的 ArrayList 或 C++ 的 std::vector）在底层使用固定大小的数组实现。当元素数量超过当前容量时，会触发扩容：一般是翻倍扩容。
操作成本如下：
- 添加元素到未满的数组：O(1)，仅赋值。
- 扩容时的添加：O(N)，需要分配新数组并拷贝旧数据。
当插入 N 个元素时，\(N ≈ 2^k\)，总成本为：\(1 + 2 + 4 + 8 + ... + 2^{(k-1)}\)
这是个等比数列，首项 1，公比 2，项数 k，总和为：\(S = 1 * (1 - 2^k) / (1 - 2) = 2^k - 1 ≈ N - 1\)
总成本 O(N) 除以操作次数 N，均摊时间复杂度为 O(1)。
为什么要均摊？单次操作可能高达 O(N)（扩容时），但这种高成本操作很少发生。
通过均摊分析，我们得出每次插入的平均成本是 O(1)，这更符合实际性能。
补充5：不要用代码结构判断时间复杂度
表面上看代码结构（如循环层数）判断复杂度很直观，但这是错误的。例如，冒泡排序可以用单 while 循环实现，但时间复杂度仍是 \(O(N^2)\)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void bubbleSort(int[] arr) {
int n = arr.length;
int i = 0, j = 0;
while (i < n - 1) {
if (j < n - i - 1) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
j++;
} else {
j = 0;
i++;
}
}
}
复杂度仍为 O(N²)，与双重循环版本相同。
补充6：空间复杂度，强调额外空间
输入数据本身不算，只算算法执行时新开辟的变量、数组、递归栈等空间。
如果算法只用几个固定变量（比如几个整数），无论 N 多大，空间都不变，这就是 (O(1)) 的空间复杂度。
补充7：调和级数的时间复杂度
比如下面的代码：
1
2
3
4
5
6
7
8
for (int i = 1; i <= N; i++) {
for (int j = i; j <= N; j += i) {
// 这两个嵌套for循环的流程，时间复杂度为O(N * logN)
// 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + ... + 1/n，也叫"调和级数"，收敛于O(logN)
// 所以如果一个流程的表达式 : n/1 + n/2 + n/3 + ... + n/n
// 那么这个流程时间复杂度O(N * logN)
}
}
调和级数 \(H_N = 1 + 1/2 + 1/3 + ... + 1/N\)，数学上已知 \(H_N \approx logN\)。每项是 \(N/i\)，总和是
\(N * (1 + 1/2 + 1/3 + ... + 1/N) = N * H_N \approx N * logN\)。
时间复杂度是 \(O(N∗logN)\)，而不是 (O(N))。
