.forEach 和 .find

Question

以下代码的大 O 表示法是什么？

    _data.validatorInfo.result.validators.forEach((_validator) => {
        let del = {
            delegation: _data.delegations.result.delegation_responses.find(
                res => res.delegation.validator_address === _validator.operator_address
            ),
            validator: _validator,
            rewards: _data.totalRewards.result.rewards.find(
                re => re.validator_address === _validator.operator_address
            )
        }
        result.delegations.push(del);
    })

因为它有一个

.forEach

和两个

.find()

嵌套操作，我可以假设它是 O(N^3) 吗？

Answer 1

你遍历所有

validators

（V），对于它们中的每一个遍历

delegation_responses

（P）和

rewards

（W）直到找到某个元素，这平均意味着要遍历数组的一半。

这会给你

V * (P + W)/2

。大 O 忽略了常量因子（将它们设置为 1），所以这给了你

O(V * (P + W))

。到那时，您可以开始争论：

• 如果 P 和 W 与 V 相比非常小（如数量级），您会争辩说它们的行为就像常数并且仅略微缩放驱动因子 V，并且您有效地处理线性复杂性

  O(N)

  ，其中 N 是验证者的数量。

• 如果 V 与 P 和/或 W 相比非常小（同样是数量级），您将得到

  O(N)

  或

  O(N + M)

  ，其中 N 和 M 是响应/奖励的数量，再次论证 V 的行为就像一个常数。

• 如果它们的大小都差不多（或者你不能对它们的大小做出假设），你会得到

  O(N * 2N)

  ，也就是

  O(N²)

  。

Answer 2

你的复杂度是

O(N*(M+Q))

，哪里

• N 是

  _data.validatorInfo.result.validators.length

• M 是

  _data.delegations.result.delegation_responses.length

  和
• Q是

  _data.totalRewards.result.rewards.length

你可以假设这

• 是二次如果 N ~ M+Q
• 线性如果 N >> M + Q

Answer 3

我不想直接回答你的问题，而是想指出可以很容易地提高性能。一种常见的方法是使用 哈希表（

Object

或

Map

）来查找您要查找的项目。

const delegations = new Map();
_data.delegations.result.delegation_responses.forEach((res) => {
  delegations.set(res.delegation.validator_address, res);
});

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

_data.validatorInfo.result.validators.forEach((_validator) => {
  result.delegations.push({
    delegation: delegations.get(_validator.operator_address),
    validator: _validator,
    rewards: rewards.get(_validator.operator_address),
  });
});

使用与Radu Dişă

的答案相同的字母

• N 是

  _data.validatorInfo.result.validators.length

• M 是

  _data.delegations.result.delegation_responses.length

  和
• Q是

  _data.totalRewards.result.rewards.length

这个改进版本会导致复杂性

O(N+M+Q)

.

---

你也许可以使用

result.delegations = _data.validatorInfo.result.validators.map(...);

如果您的情况允许。

Answer 4

我会认为 O(N^2)，原因是第一个操作是 forEach，N 是这里数组的长度。第二个操作是 .find 也是 O(N)，具有最坏情况的时间复杂度。在我看来，这等于 O(N^2)。