原地修改数组：O(n)与O(1)哪个更高效？附示例与疑问

函数示例 #

非原地修改版本 #

function increaseByOne(nums) {
  const increased = [];
  for (let i = 0 ; i < nums.length ; i++) {
      increased.push(nums[i] + 1);
  }
  return increased;
}

原地修改版本 #

function increaseByOneInPlace(nums) {
  for (let i = 0 ; i < nums.length ; i++) {
      nums[i]++;
  }
  return nums;
}

示例输出 #

nums = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];

console.log(increaseByOne(nums));
// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

console.log(increaseByOneInPlace(nums));
// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

效率对比及原因 #

increaseByOneInPlace函数更高效，核心差异在空间复杂度：

• 时间复杂度上，两个函数都是O(n)：都需要遍历数组中所有n个元素，每个元素只执行一次加1操作，总操作次数和数组长度线性相关。
• 空间复杂度上，increaseByOne是O(n)：它需要创建一个和原数组长度相同的新数组来存储结果，额外占用的空间随数组规模n线性增长；而increaseByOneInPlace是O(1)：直接在原数组上修改元素，除了循环变量这类常数级的内存开销，不需要额外开辟和原数组等大的存储空间。

关于O(n)和O(1)的差异：
O(n)表示资源（时间/空间）消耗会随着输入规模n的增大而线性增长，比如处理100个元素要100份空间，处理1000个就要1000份；O(1)则表示不管输入规模多大，资源消耗始终是固定的常数，不会随n变化。

额外问题：除嵌套循环外的O(n²)时间复杂度实现 #

当然有，举几个常见场景：

• 嵌套数组方法调用：比如用forEach遍历每个元素时，内部调用find/filter遍历整个数组。例如遍历数组时，为每个元素查找数组中比它大的所有元素，每次find都会遍历n个元素，总操作次数是n*n，时间复杂度O(n²)。
• 生成所有两两元素组合：比如计算数组中所有元素的两两和、两两乘积，这类操作的总组合数是n*(n-1)/2，属于O(n²)量级，实现时即使不用显式嵌套循环，底层的组合生成逻辑也会带来n²级的操作次数。
• 低效的递归实现：比如某个递归函数，每次调用会触发n次递归调用，总调用次数累计下来是n²级别，时间复杂度自然是O(n²)。

内容的提问来源于stack exchange，提问作者zunny