你好我是林森lsjs我的Github 地址sqyCoder (Qiyang) · GitHub以博文记录成长用心打磨代码与思维目录一、集合类引入1.与数据结构的联系二、时间复杂度1.概念2.计算1.1 例1O (N²)1.2 例2O(MN)1.3 例3O(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 例1O(1)1.2 例2非递归斐波那契 O(N)1.3 例3递归O(N)一、集合类引入Java里的集合类就是java.util包下一系列用来存放多个对象的工具类用来弥补数组长度固定、操作不便的缺陷。集合长度能够动态变化只能存储引用类型数据整体分为两大体系Collection单列集合每次存放单个元素包含有序可重复的List、不允许重复元素的Set以及队列QueueMap双列集合用来存储键值对数据键不能重常用实现类有ArrayList、HashSet、HashMap等并且集合自带增删查找、遍历等现成方法方便我们批量操作数据。1.与数据结构的联系我们学习的Java集合类底层实现全都依托各类数据结构数据结构本质研究如何组织多个数据目的是高效完成数据的增删改查就像过去依靠档案室人工整理档案计算机诞生后借助不同的数据结构自动化管理海量数据互联网项目里往往要处理大量用户数据不同集合对应不同的数据结构也带来不一样的存取效率开发时我们要根据业务场景挑选合适的集合。二、时间复杂度1.概念时间:程序运行的快慢2.计算1.1 例1O (N²)我们先看这段代码里面的 count 就是我们要观察的基本操作第一层双重循环会执行 N 乘 N 次 count下方 for 循环执行 2N 次while 循环执行 10 次合起来精确执行次数就是 N²2N10时间复杂度采用大 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 例2O(MN)这段代码存在两个独立的循环第一个循环执行M次count第二个循环执行N次count基础操作总次数为MN这里N和M是两个相互独立的数据规模无法互相替代因此时间复杂度不能随意消去任意一个变量最终记作O(MN)这也说明大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 例3O(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循环条件end0单纯看外层循环最多可以执行 N 轮end取值依次为 NN-1N-2 …… 1。接下来解释内层循环次数内层循环条件i endi从1开始。第一轮 endNi N → 内层循环执行 N-1 次第二轮 endN-1i N-1 → 内层循环执行 N-2 次第三轮 endN-2i N-2 → 内层循环执行 N-3 次……最后一轮 end1i 1内层循环执行 0 次。所以全部内层循环执行总数就是一串数字相加(N-1)(N-2)(N-3)…10。这是等差数列首项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 注意ON的二次方是最坏复杂度如果数组初始有序第一轮遍历后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先梳理完整调用流程以N5举例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 例1O(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数组长度为n1输入规模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)核心误区就是忽略了函数调用栈所消耗的额外内存。每一次方法调用都会在调用栈中生成一块独立内存单元也就是栈帧栈帧中存放着方法地址、形参、局部变量、程序返回位置等运行信息。以N5为例递归执行时会依次压入factorial(5)、factorial(4)、factorial(3)、factorial(2)、factorial(1)多层栈帧直到抵达递归终止条件之后栈帧才会逐层弹出释放。同一时刻调用栈中最多同时存在N个栈帧占用的内存规模与输入规模N呈线性关系因此线性递归实现阶乘的空间复杂度为O(N)今天的数据结构讲解就到这了我们下期再见诸位共勉