你好，我是林森lsjs

我的Github 地址：sqyCoder (Qiyang) · GitHub

以博文记录成长，用心打磨代码与思维

目录

一、集合类引入

1.与数据结构的联系

二、时间复杂度

1.概念

2.计算

1.1 例1：O (N²)

1.2 例2：O(M+N)

1.3 例3：O(1)

1.3.1 注意！

1.4 例4：冒泡排序 O(N的2次方)

1.4.1 注意！

1.5 例5：二分查找 O(logN)

1.6 例6：递归 O(N)

1.7 例7：递归斐波那契 O(2的n次方)

三、空间复杂度

1.概念

2.计算

1.1 例1：O(1)

1.2 例2：非递归斐波那契 O(N)

1.3 例3：递归O(N)

一、集合类引入

Java里的集合类就是java.util包下一系列用来存放多个对象的工具类，用来弥补数组长度固定、操作不便的缺陷。

集合长度能够动态变化，只能存储引用类型数据，整体分为两大体系

Collection单列集合每次存放单个元素，包含有序可重复的List、不允许重复元素的Set以及队列Queue

Map双列集合用来存储键值对数据，键不能重

常用实现类有ArrayList、HashSet、HashMap等，并且集合自带增删查找、遍历等现成方法，方便我们批量操作数据。

1.与数据结构的联系

我们学习的Java集合类底层实现全都依托各类数据结构，数据结构本质研究如何组织多个数据，目的是高效完成数据的增删改查

就像过去依靠档案室人工整理档案，计算机诞生后借助不同的数据结构自动化管理海量数据

互联网项目里往往要处理大量用户数据，不同集合对应不同的数据结构，也带来不一样的存取效率，开发时我们要根据业务场景挑选合适的集合。

二、时间复杂度

1.概念

时间:程序运行的快慢

2.计算

1.1 例1：O (N²)

我们先看这段代码，里面的 count++ 就是我们要观察的基本操作，第一层双重循环会执行 N 乘 N 次 count++，下方 for 循环执行 2N 次，while 循环执行 10 次，合起来精确执行次数就是 N²+2N+10

时间复杂度采用大 O 渐进表示法，它不去纠结精确的执行数字

重点关注数据规模 N 不断变大时代码耗时的增长趋势，当 N 取值很大，2N 和常数 10 这类低阶部分带来的影响几乎可以忽略，同时表达式的系数也会舍弃，最后只保留最高阶项记作 O (N²)

void func1(int N){ int count = 0; for (int i = 0; i < N ; i++){ for (int j = 0; j < N; j++){ count++; } } for (int k = 0; k < 2 * N ; k++){ count++; } int M = 10; while ((M--) > 0){ count++; } System.out.println(count); }

要是解决同一个问题有两份代码，一份复杂度 O (N²)、一份 O (N)，O (N) 曲线上涨更平缓，运行效率就更优秀，还要注意 O (N²) 和 O (2N²) 增长走向是相同的，所以大 O 写法里直接去掉常数系数。

1.2 例2：O(M+N)

这段代码存在两个独立的循环，第一个循环执行M次count++，第二个循环执行N次count++，基础操作总次数为M+N

这里N和M是两个相互独立的数据规模，无法互相替代，因此时间复杂度不能随意消去任意一个变量，最终记作O(M+N)

这也说明大O渐进表示法里允许同时出现多个代表问题规模的变量，只有当多个变量存在大小确定的约束关系时，才可以进行简化，如果题目没有说明M和N的大小关系，就必须保留两个变量。

void func3(int N, int M) { int count = 0; for (int k = 0; k < M; k++) { count++; } for (int k = 0; k < N; k++) { count++; } System.out.println(count); }

1.3 例3：O(1)

这段代码里循环的执行次数固定是100次，不会随着参数N的大小发生任何变化，按照大O渐进表示法的规则，常数统一简化记作1，不能写成O(100)，所以最终时间复杂度是O(1)

也就是常数阶，O(1)代表代码运行耗时稳定，不受输入数据规模影响，无论传入多大的N，基础操作的执行总量始终固定。

void func4(int N) { int count = 0; for (int k = 0; k < 100; k++) { count++; } System.out.println(count); }

1.3.1 注意！

时间复杂度刻画的是代码执行次数随数据规模增长的变化趋势，并不是程序实际运行耗费的绝对时间

常量阶 O (1) 代表操作次数不会随 N 变化，通常认为拥有很好的效率，但我们不能直接断言 O (1) 一定比 O (N) 运行更快

因为 O (1) 背后可能是一万次固定运算，而 O (N) 里的 N 如果只是 100 这种很小的数值，此时 O (N) 真实耗时反而更短

只有当数据规模 N 持续不断增大之后，二者的趋势差距才会体现出来，O (N) 的耗时会持续上涨，而 O (1) 依旧保持稳定，这也是我们分析复杂度更多用来预判大数据量场景下程序性能的原因。

1.4 例4：冒泡排序 O(N的2次方)

我们先设定数组长度为 N，全程分析最坏情况（数组完全逆序，不会触发break提前退出）。

外层循环变量end初始等于数组长度N，每一轮循环结束end自减1，循环条件end>0，单纯看外层循环最多可以执行 N 轮，end取值依次为 N，N-1，N-2 …… 1。

接下来解释内层循环次数：内层循环条件i < end，i从1开始。

第一轮 end=N，i < N → 内层循环执行 N-1 次；

第二轮 end=N-1，i < N-1 → 内层循环执行 N-2 次；

第三轮 end=N-2，i < N-2 → 内层循环执行 N-3 次；

……

最后一轮 end=1，i < 1，内层循环执行 0 次。

所以全部内层循环执行总数就是一串数字相加：(N-1)+(N-2)+(N-3)+…+1+0。

这是等差数列，首项0，末项N‑1，总项数N项。

等差数列求和： 总和 = (首项 + 末项) × 项数 / 2 = (0 + N‑1) × N / 2 = 0.5N² − 0.5N

现在套用大O渐进表示法规则：只保留最高阶项，去掉系数、低次项。

式子 0.5N² − 0.5N 最高阶是 N²，舍弃系数0.5与一次项−0.5N，最终时间复杂度 O(N²)。

1.4.1 注意！

O（N的二次方）是最坏复杂度；如果数组初始有序，第一轮遍历后sorted保持true，直接break跳出，最好时间复杂度O(N)；算法复杂度默认无说明时取最坏情况。

1.5 例5：二分查找 O(logN)

int binarySearch(int[] array, int value) { int begin = 0; int end = array.length - 1; while (begin <= end) { int mid = begin + (end - begin) / 2; if (array[mid] < value) { begin = mid + 1; } else if (array[mid] > value) { end = mid - 1; } else { return mid; } } return -1; }

还是先明确前提：我们算的是最坏情况，也就是目标值不存在，循环完整跑完才退出

设数组总长度是N，循环一共执行了k次，我们的目标就是算出k和N的关系。

最开始还没进入循环的时候，整个数组都是查找区间，区间长度就是N。

执行第1次循环，我们算出中间位置，直接舍弃一半元素，区间长度砍掉一半，变成 N / 2。

执行第2次循环，剩下的区间再砍掉一半，长度变成 N/2 再除以2，也就是 N / 2² = N / 4。

执行第3次循环，继续砍半，长度变成 N / 2³ = N / 8。

以此类推，每多执行一次循环，分母上的2就多乘一次，所以执行完第k次循环的时候，剩下的区间长度就是 N 除以 2的k次方，也就是 N / 2ᵏ。

接下来是循环停止的条件：当区间里没有元素了，也就是区间长度小于1的时候，循环就结束了。最坏情况下，我们会一直砍到区间里只剩1个元素，做完最后一次比较后区间为空，也就是当 N / 2ᵏ = 1 的时候，刚好完成最后一次有效比较。

我们把这个等式变形一下，两边同时乘 2ᵏ，就得到 N = 2ᵏ。

现在我们要求循环次数k，就对等式两边同时取以2为底的对数，左边是log₂N，右边log₂(2ᵏ)就等于k，所以最终得到 k = log₂N。

也就是说，长度为N的有序数组，二分查找最坏情况下最多执行 log₂N 次循环，每次循环里的比较、移动指针都是固定次数的常数操作，所以整体的时间复杂度就是 O(logN)。

接下来通过增长曲线对比，就能直观看出对数复杂度的优势。

O(N)是匀速上升的直线，数据规模N扩大多少倍，操作次数就会同步增长多少倍；

而O(logN)的曲线上升趋势越来越平缓，数据量越大，它的性能优势就越突出，比如当N等于1024时，O(N)需要执行1024次操作，O(logN)仅需要10次就能完成查找

这也是行业内普遍认为对数级复杂度远优于线性复杂度的原因。

1.6 例6：递归 O(N)

long factorial(int N) { return N < 2 ? 1 : factorial(N - 1) * N; }

我们先打破一个容易产生的误区：代码表面看不到循环，不代表不存在重复执行的基本操作，递归调用本身就是重复执行的载体。

我们设定问题规模为传入参数N，先梳理完整调用流程，以N=5举例：factorial(5)调用factorial(4)，factorial(4)调用factorial(3)，factorial(3)调用factorial(2)，factorial(2)调用factorial(1)，factorial(1)触发基线条件直接返回结果，整条调用链一共发生5次方法调用。

推广到通用情况，参数为N时，每一次递归都会让参数减少1，持续向下调用直到参数等于1

总共会产生N次递归调用

每一次方法内部执行的判断、乘法运算，都属于固定次数的常数操作

也就是我们分析复杂度时的基准操作。基准操作一共执行N次，操作总次数和N呈线性正比关系。

按照大O渐进表示法规则，最终这段递归阶乘代码的时间复杂度为$$\boldsymbol{O(N)$$。

1.7 例7：递归斐波那契 O(2的n次方)

int fibonacci(int N) { return N < 2 ? N : fibonacci(N-1) + fibonacci(N-2); }

我们先看清这段递归代码的执行特点，它和之前阶乘递归最大的区别在于：每次调用不会只产生一次递归，当N≥2时，一个fibonacci(N)会同时分出两路调用：fibonacci(N-1)与fibonacci(N-2)。

我们可以把调用关系画成一棵二叉树，fib(N)是根节点，每个节点向下生成两个子节点，树的大致高度为N层。第一层调用数量1，第二层最多2个，第三层最多4个，第四层最多8个，每往下一层，调用次数近似翻倍，形成等比数列：1,2,4,8,16

等比数列求和，N层节点总数近似等于2^N

这意味着函数调用次数随N指数级暴涨。

所以时间复杂度为O(2^N）。指数复杂度增长速度极其恐怖，远超平方复杂度O(N^2）

同时还有一个严重缺陷：存在大量重复计算，例如fib(37)会被fib(38)和fib(39)分别重复求解，大量冗余递归不断消耗算力

这也是朴素递归斐波那契效率极低的根源。后续可以用数组缓存、迭代或者矩阵快速幂的方式优化，把复杂度降低到O(N）甚至O(log N）。

三、空间复杂度

1.概念

所谓的“空间复杂度”就是看你这段代码中,定义了多少个变量,变量个数和问题规模N之间的趋势关系

2.计算

1.1 例1：O(1)

void bubbleSort(int[] array) { for (int end = array.length; end > 0; end--) { boolean sorted = true; for (int i = 1; i < end; i++) { if (array[i - 1] > array[i]) { Swap(array, i - 1, i); sorted = false; } } if (sorted == true) { break; } } }

首先明确空间复杂度分析的第一条规则：传入的原始数组array属于函数外部输入，计算额外空间时一般不纳入统计，我们只关注方法内部新开辟的存储空间。

这段代码里定义了end、sorted、i三个局部变量，很多人会误以为循环多次运行就会持续累积占用空间，这里要区分空间和时间的核心差异：时间一旦消耗无法回收，但是内存空间可以重复复用。每一轮循环创建的sorted、i，在本轮循环结束后对应的内存就被释放

下一轮循环可以重新使用同一块内存地址，不会叠加占用，程序运行全程最多同时占用这3份固定大小的额外空间

常量空间统一记作$$\boldsymbol{O(1)$$

1.2 例2：非递归斐波那契 O(N)

int[] fibonacci(int n) { long[] fibArray = new long[n + 1]; fibArray[0] = 0; fibArray[1] = 1; for (int i = 2; i <= n; i++) { fibArray[i] = fibArray[i - 1] + fibArray[i - 2]; } return fibArray; }

我们分析这段迭代实现斐波那契代码的空间复杂度，核心关注点是代码中新开辟的存储空间。方法内部创建了数组fibArray，数组长度为n+1，输入规模n越大，数组占用的内存就同步线性变大，存储空间的大小和输入参数n成正比。

循环里的局部变量i只是固定大小的常量空间，在大O表示中可以忽略，起决定性作用的就是这个长度随n变化的数组。按照空间复杂度判定规则，额外空间随输入规模线性增长

因此这段代码空间复杂度为$$\boldsymbol{O(N)$$。

1.3 例3：递归O(N)

long factorial(int N) { return N < 2 ? 1 : factorial(N-1)*N; }

不少人初次观察这段代码时，发现代码内没有主动new数组或者对象，仅有传入参数，容易错误判定空间复杂度为O(1)

核心误区就是忽略了函数调用栈所消耗的额外内存。

每一次方法调用，都会在调用栈中生成一块独立内存单元，也就是栈帧，栈帧中存放着方法地址、形参、局部变量、程序返回位置等运行信息。以N=5为例，递归执行时会依次压入factorial(5)、factorial(4)、factorial(3)、factorial(2)、factorial(1)多层栈帧

直到抵达递归终止条件之后，栈帧才会逐层弹出释放。同一时刻调用栈中最多同时存在N个栈帧

占用的内存规模与输入规模N呈线性关系，因此线性递归实现阶乘的空间复杂度为O(N)

今天的数据结构讲解就到这了，我们下期再见！

诸位共勉！