文章目录时空复杂度分析1.借助复杂度反推题解思路2.由于编码失误导致复杂度异常的可能原因3.Big O 表示法4.非递归算法分析 ⭐5.递归算法分析 ⭐6.常见时间复杂度分析时空复杂度分析简单理解时间复杂度大部分情况下就是看 for 循环的最大嵌套层数空间复杂度就看算法申请了多少空间来存储数据。[!important]非递归算法中嵌套循环的复杂度依然可能是线性的数据结构 API 需要用平均时间复杂度衡量性能递归算法本质是遍历递归树时间复杂度取决于递归树中节点的个数递归次数和每个节点的复杂度递归函数本身的复杂度。1.借助复杂度反推题解思路举例来说吧比如一个题目给你输入一个数组其长度能够达到10^6这个量级那么我们肯定可以知道这道题的时间复杂度大概要小于O ( N 2 ) O(N^2)O(N2)得优化成O ( N l o g N ) O(NlogN)O(NlogN)或者O ( N ) O(N)O(N)才行。因为如果你写的算法是O ( N 2 ) O(N^2)O(N2)的最大的复杂度会达到10^12这个量级在大部分判题系统上都是跑不过去的。为了把复杂度控制在O ( N l o g N ) O(NlogN)O(NlogN)或者O ( N ) O(N)O(N)我们的选择范围就缩小了可能符合条件的做法是对数组进行排序处理、前缀和、双指针、一维 dp 等等从这些思路切入就比较靠谱。像嵌套 for 循环、二维 dp、回溯算法这些思路基本可以直接排除掉了。再举个更直接的例子如果你发现题目给的数据规模很小比如数组长度N不超过20这样的那么我们可以断定这道题大概率要用暴力穷举算法。因为判题平台肯定是尽可能扩大数据规模难为你它一反常态给这么小的数据规模肯定是因为最优解就是指数/阶乘级别的复杂度。你放心用回溯算法招呼它就行了不用想别的算法了。所以说不看数据规模上来就闷声写代码这是不对滴。你先把题目给的所有信息都考虑进去再写代码这样才能少走弯路。2.由于编码失误导致复杂度异常的可能原因使用了标准输出。因为标准输出属于 I/O 操作会很大程度上拖慢你的算法代码运行。 -System.out.println()错误地「传值」而非「传引用」。错误地传值几乎必然导致超时或超内存。 - 搞清楚值传递和引用传递。3.Big O表示法只保留增长速率最快的项其他的项可以省略。首先乘法和加法中的常数因子都可以忽略不计比如下面的例子O(2N100)O(N)O(2^(N1))O(2*2^N)O(2^N)O(M3N99)O(MN)当然不要见到常数就消有的常数消不得可能会用到我们中学学过的指数运算法则O(2^(2N))O(4^N)除了常数因子增长速率慢的项在增长速率快的项面前也可以忽略不计O(N^3999*N^2999*N)O(N^3)O((N1)*2^N)O(N*2^N2^N)O(N*2^N)Big O 记号表示复杂度的「上界」。4.非递归算法分析 ⭐非递归算法的空间复杂度看有没有申请数组之类的存储空间就行了。非递归算法的时间复杂度非递归算法中嵌套循环很常见大部分场景下只需把每一层的复杂度相乘就是总的时间复杂度。// 复杂度 O(N*W)for(inti1;iN;i){for(intw1;wW;w){dp[i][w]...;}}// 1 2 ... n n/2 (n^2)/2// 用 Big O 表示化简为 O(n^2)for(inti0;in;i){for(intji;j0;j--){dp[i][j]...;}}但有时候只看嵌套循环的层数并不准确还得看算法具体在做什么。比如nSum问题和滑动窗口算法。重点看指针回不回退。// 左右双指针intlo0,hinums.length;while(lohi){intsumnums[lo]nums[hi];intleftnums[lo],rightnums[hi];if(sumtarget){while(lohinums[lo]left)lo;}elseif(sumtarget){while(lohinums[hi]right)hi--;}else{while(lohinums[lo]left)lo;while(lohinums[hi]right)hi--;}}这段代码看起来很复杂大 while 循环里面套了好多小 while 循环感觉这段代码的时间复杂度应该是O ( N 2 ) O(N^2)O(N2)但是lo指针一直在往右走lohi指针一直在往左走hi--它俩有没有走着走着突然往回走没有。所以这段算法的逻辑就是lo和hi不断相向而行相遇时算法结束那么它的时间复杂度就是线性的O ( N ) O(N)O(N)。intleft0,right0;while(rightnums.size()){// 增大窗口window.addLast(nums[right]);right;while(window needs shrink){// 缩小窗口window.removeFirst(nums[left]);left;}}乍一看也是个嵌套循环但仔细观察发现这也是个双指针技巧left和right指针从 0 开始一直向右移直到移动到s的末尾结束外层 while 循环没有回退过。用N代表字符串s的长度那么该算法做的事情就是把left和right两个指针从 0 移动到N只要使用合适的数据结构使得扩大缩小窗口的操作复杂度为O ( 1 ) O(1)O(1)那么滑动窗口算法的时间复杂度为线性的O ( N ) O(N)O(N)。5.递归算法分析 ⭐所有递归算法的本质是树的遍历。计算算法的时间复杂度无非就是看这个算法做了些啥事儿花了多少时间。而递归算法做的事情就是遍历一棵递归树在树上的每个节点所做一些事情罢了。递归算法的时间复杂度 递归的次数 x 函数本身的时间复杂度递归算法的空间复杂度 递归堆栈的深度 算法申请的存储空间⬇️递归算法的时间复杂度 递归树的节点个数 x 每个节点的时间复杂度递归算法的空间复杂度 递归树的高度 算法申请的存储空间6.常见时间复杂度分析