如何高效计算数组内嵌套对象中颜色通道的平均值？（考虑Big O）

原始数据对象 #

const design = {
      designId: 1,
      shapes: [
        { shapeId: 'basic-square', color: { r: 255, g: 255, b: 255 }},
        { shapeId: 'basic-circle', color: { r: 255, g: 255, b: 255 }},
        { shapeId: 'basic-diamond', color: { r: 255, g: 0, b: 0 }},
        { shapeId: 'basic-rectangle', color: { r: 0, g: 255, b: 0 }}
      ]
    }

需求 #

计算该设计中所有形状的RGB颜色通道平均值，期望输出：

Design 1: {r: 191.25, g: 191.25, b: 127.5 }

低效的尝试代码 #

以下代码被指出效率不足：

const average = (arr) => arr.reduce((a, b) => a + b, 0) / arr.length;

const { shapes } = design;

const reds = shapes.map(shape => shape.color.r)
const greens = shapes.map(shape => shape.color.g)
const blues = shapes.map(shape => shape.color.b)

console.log(`Design ${design.designId}: {r: ${average(reds)}, g: ${average(greens)}, b: ${average(blues)} }`)

高效解决方案 #

核心思路

只遍历一次shapes数组，同时累加三个颜色通道的总和，最后用总和除以形状数量得到平均值。这种方式减少了遍历次数，同时避免额外存储三个通道的数组，优化了时间与空间效率。

实现代码

const { designId, shapes } = design;
const shapeCount = shapes.length;

// 初始化各通道总和
let totalR = 0, totalG = 0, totalB = 0;

// 单次遍历完成所有累加操作
for (const shape of shapes) {
  const { r, g, b } = shape.color;
  totalR += r;
  totalG += g;
  totalB += b;
}

// 计算各通道平均值
const avgR = totalR / shapeCount;
const avgG = totalG / shapeCount;
const avgB = totalB / shapeCount;

console.log(`Design ${designId}: {r: ${avgR}, g: ${avgG}, b: ${avgB} }`);

复杂度分析 #

• 时间复杂度：O(n)，其中n是shapes数组的长度。仅需遍历一次数组，所有累加、计算操作均为常数时间。
• 空间复杂度：O(1)，仅使用固定数量的变量存储总和、计数与平均值，无额外开辟与数组长度相关的存储空间。

与原代码的对比 #

原代码需要3次map遍历生成三个通道数组，再3次reduce遍历计算总和，总遍历次数为6次，空间复杂度为O(n)（需存储三个长度为n的数组）。虽然两者时间复杂度均为线性，但单次遍历的实际运行开销更低，且内存占用更少，当shapes数量极大时，优势会更明显。

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