从零开始搞懂时间/空间复杂度 + 图解三指针合并有序数组（力扣88题）

一、什么是时间复杂度和空间复杂度？——用5段代码讲明白

在算法世界里，我们不只关心“能不能跑通”，更关心“跑得快不快”、“占不占地方”。这就是时间复杂度和空间复杂度要解决的问题。

时间复杂度：衡量“执行步骤”的增长趋势

不是看实际运行几毫秒，而是看随着输入数据变大，操作次数怎么变。我们用大O表示法（Big O）来描述这个“趋势”。

来看几个经典例子：

例1：线性遍历 →O(n)

来自1.js：

// T(n) = 3n+3 function traverse(arr) { var len = arr.length; // 1次 for (let i = 0; i < len; i++) { // 循环 n 次 console.log(arr[i]); // 每次循环1次 } } // T(n) = 1 + 1 + n + 1 + n + n = 3n+3 → 忽略常数和低阶项 → O(n)

解释：数组越长，打印次数越多，成正比关系。就像你数100个人的名字，肯定比数10个人花10倍时间。

例2：双重循环 →O(n²)

来自2.js：

function traverse(arr) { var outlen = arr.length; for (var i = 0; i < outlen; i++) { var inlen = arr[i].length; for (var j = 0; j < inlen; j++) { console.log(arr[i][j]); } } } // T(n) ≈ 4n² + ... → O(n²)

解释：比如一个 n×n 的表格，你要把每个格子都点一遍，总共点 n² 次。数据量翻倍，操作次数变成4倍！很可怕。

例3：指数级跳跃 →O(log n)

来自3.js：

for (var i = 1; i < len; i = i * 2) { console.log(arr[i]); } // T(n) = 2logn + 4 → O(log n)

解释：i 每次翻倍（1→2→4→8...），所以循环次数是 log₂(len)。比如 len=1024，只循环10次！这是非常高效的节奏，像二分查找。

例4：额外开数组 →O(n)空间

来自4.js：

function init(n) { var arr = []; // 新开辟空间！ for (var i = 0; i < n; i++) { arr[i] = i; } return arr; } // S(n) = O(n)

空间复杂度：衡量额外内存占用。这里新建了一个长度为 n 的数组，所以空间是 O(n)。

例5：原地操作 →O(1)空间

还是1.js：

// S(1) 因为只有一个arr，其他作为参数，没有额外的内存开销

没有 new 数组、没递归、没哈希表，只是用几个变量（i, len），所以空间是常数级O(1) —— 最省！

✅总结一句话：

• 时间复杂度：看“操作次数”随输入规模怎么涨。
• 空间复杂度：看“额外内存”用了多少。
• 我们追求：时间快 + 空间省！

二、实战：力扣88题《合并两个有序数组》——三指针 + 原地合并

题目要求：

• nums1长度为m + n，前m个是有用数字，后n个是 0（预留空间）
• nums2长度为n
• 把nums2合并进nums1，最终nums1变成一个有序数组
• 不能返回新数组！必须原地修改 nums1

错误思路：从前向后合并？

很多人第一反应：用两个指针从前往后比，小的放前面。

但问题来了：nums1 后面有空位，前面却有数据！
如果你把小的数往前面插，会覆盖掉还没处理的 nums1 元素！

比如：

nums1 = [1,2,3,0,0,0], m=3 nums2 = [2,5,6], n=3

如果从前往后，第一步把 1 放好没问题，但第二步要把 2（来自 nums2）放进去时，nums1[1] 原本是 2，会被覆盖，而那个 2 还没被处理！

所以不能从前向后！

正确思路：从后往前 + 三指针！

利用 nums1尾部有空位的特点，从最大的数开始填，就不会覆盖未处理的数据！

来看代码（一字不变）：

function merge(nums1, m, nums2, n) { // 数组是连续的存储空间，所以可以从后往前合并 let i = m - 1; // i 是 nums1 里面“有用数字”的最后一位的位置（从0开始数） let j = n - 1; // j 是 nums2 里面“有用数字”的最后一位的位置 let k = m + n - 1; // k 是 nums1 整个数组最后一位的位置（因为nums1已经预留了足够空间） // 数组是有序的 while(i >= 0 && j >= 0) { // 只要 nums1 和 nums2 都还有数字没比完，就继续比 if (nums1[i] > nums2[j]) { // 如果 nums1 当前的数字比 nums2 的大 nums1[k] = nums1[i]; // 就把大的那个放到 nums1 的最后面（k的位置） i--; // 然后 nums1 的指针往前面走一步（看下一个数字） } else { // 否则（nums2 的数字更大或一样大） nums1[k] = nums2[j]; // 把 nums2 的这个数字放到 nums1 的最后面 j--; // 然后 nums2 的指针往前面走一步 } k--; // 不管放了谁，最后面的位置都要往前挪一格，准备放下一个 } while(j >= 0) { // 如果 nums2 还剩下一些小数字没放完（nums1已经放完了） nums1[k] = nums2[j]; // 就把这些剩下的小数字一个个放到 nums1 前面空着的位置 j--; // 每放一个，nums2 的指针往前走 k--; // 放的位置也往前走 } }

图解三指针工作过程

初始状态：

nums1 = [1, 2, 3, 0, 0, 0] ↑ ↑ ↑ i | k | nums2 = [2, 5, 6] ↑ j

Step 1: 比较 nums1[i]=3 和 nums2[j]=6 → 6 更大 → 放到 k 位置

nums1 = [1, 2, 3, 0, 0, 6] ↑ ↑ ↑ i | k | nums2 = [2, 5, 6] ↑ j

Step 2: 比较 3 vs 5 → 5 更大

nums1 = [1, 2, 3, 0, 5, 6] ↑ ↑ ↑ i | k | nums2 = [2, 5, 6] ↑ j

Step 3: 比较 3 vs 2 → 3 更大

nums1 = [1, 2, 3, 3, 5, 6] ↑ ↑ ↑ i | k | nums2 = [2, 5, 6] ↑ j

Step 4: 比较 2 vs 2 → 相等，放 nums2 的（或 nums1 的也行）

nums1 = [1, 2, 2, 3, 5, 6] ↑ ↑↑ i k nums2 = [2, 5, 6] (j=-1，结束)

此时j < 0，说明 nums2 已全部放入。而 nums1 剩下的 [1,2] 本来就在正确位置，不用动！

💡 注意：如果 nums1 先耗尽（i<0），但 nums2 还有剩，就需要第二个 while 循环把剩下的 nums2 元素补到前面。

复杂度分析

• 时间复杂度：O(m + n)
  每个元素最多被访问一次，总共 m+n 个元素。

• 空间复杂度：O(1)
  只用了 i, j, k 三个变量，没有额外数组！完美符合“原地合并”要求。

为什么这个方法聪明？

1. 利用了“有序”特性：最大值一定在两个数组的末尾。
2. 利用了“预留空间”：从后往前写，不会踩到自己的脚。
3. 三指针分工明确：
   • i：负责 nums1 的有效数据
   • j：负责 nums2 的所有数据
   • k：负责写入位置

三、结语：算法之美，在于洞察结构

这道题看似简单，却完美展示了：

• 如何通过分析数据结构特点（有序 + 尾部空闲）设计高效策略；
• 如何用极低的空间代价（O(1)）完成任务；
• 为什么时间复杂度 O(m+n)是最优的（每个元素至少要看一次）。

下次遇到“合并有序数组”，别再想着新建数组了！试试从后往前，三指针出击！

🌟记住：好的算法，不是代码多炫，而是恰到好处地利用已知条件。

Happy Coding！🚀