. foreach与.find的大0表示法

Question

以下代码的大0符号是什么?

_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 is_data.validatorInfo.result.validators.length
• M是_data.delegations.result.delegation_responses.length和
• Q is_data.totalRewards.result.rewards.length

你可以假设这个

如果N ~ M+Q

• 为二次曲线
• 线性if 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 is_data.validatorInfo.result.validators.length
• M是_data.delegations.result.delegation_responses.length和
• Q is_data.totalRewards.result.rewards.length

这个改进的版本将导致复杂性O(N+M+Q).

---

你可以使用

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

如果你的场景允许的话。