含.forEach与嵌套.find操作的代码的Big O表示法及复杂度疑问

先直接给出结论：这段代码的时间复杂度不是O(N³)，具体分析如下：

变量定义（明确集合规模） #

假设：

• _data.validatorInfo.result.validators数组的长度为 N（外层遍历的次数）
• _data.delegations.result.delegation_responses数组的长度为 M
• _data.totalRewards.result.rewards数组的长度为 K

逐步骤复杂度拆解 #

1. 外层的forEach循环：遍历N个验证器元素，时间复杂度为 O(N)
2. 循环内的两个find操作：
   • 第一个find需要遍历delegation_responses的全部M个元素（最坏情况），时间复杂度为 O(M)
   • 第二个find需要遍历rewards的全部K个元素（最坏情况），时间复杂度为 O(K)

总时间复杂度 #

将各部分叠加，总时间复杂度为 O(N(M+K))*

如果这三个集合的规模属于同一量级（比如M≈N、K≈N，比如所有数据都和验证器数量正相关），可以简化为 O(N²)，远低于O(N³)——O(N³)需要三层嵌套遍历同规模的集合，而这里只有外层一层遍历，内层是两个独立的线性查找，并非三层嵌套。

优化建议 #

如果想降低时间复杂度，可以提前把delegation_responses和rewards转换成以validator_address为键的对象：

// 预先生成映射表
const delegationMap = new Map();
_data.delegations.result.delegation_responses.forEach(res => {
  delegationMap.set(res.delegation.validator_address, res);
});

const rewardMap = new Map();
_data.totalRewards.result.rewards.forEach(re => {
  rewardMap.set(re.validator_address, re);
});

// 遍历验证器时直接O(1)查找
_data.validatorInfo.result.validators.forEach((_validator) => {
  let del = {
      delegation: delegationMap.get(_validator.operator_address),
      validator: _validator,
      rewards: rewardMap.get(_validator.operator_address)
  }
  result.delegations.push(del);
})

优化后总时间复杂度降至 O(N+M+K)，属于线性时间复杂度，效率提升明显。

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