如何降低交易txs与区间interval匹配场景下两层for循环的O(n²)复杂度

安全阿岳

2026-10-1

优化方案

核心思路

时间复杂度为O(M log M + N log M + T)，其中：

M是txs数组的长度
N是interval数组的长度
T是所有区间最终包含的tx总数量（该开销为业务必要开销，任何实现都无法避免）

对比原O(N*M)的双层循环方案，在万级数据场景下性能提升可达数百倍。

实现步骤

预处理txs数组：按date字段升序排序，同时单独提取出所有date组成有序数组方便二分查找
遍历每个区间，通过两次二分查找定位到符合该区间date范围的tx的左右边界
把边界内的tx批量添加到当前区间的txs数组中

代码实现

// 1. 排序txs，同时提取有序date数组
const sortedTxs = txs.sort((a, b) => a.date - b.date);
const dates = sortedTxs.map(tx => tx.date);

// 二分查找左边界：第一个 >= target的索引
function binarySearchLeft(target) {
  let left = 0, right = dates.length;
  while (left < right) {
    const mid = (left + right) >> 1;
    if (dates[mid] >= target) right = mid;
    else left = mid + 1;
  }
  return left;
}

// 二分查找右边界：最后一个 <= target的索引
function binarySearchRight(target) {
  let left = 0, right = dates.length;
  while (left < right) {
    const mid = (left + right) >> 1;
    if (dates[mid] > target) right = mid;
    else left = mid + 1;
  }
  return left - 1;
}

// 2. 遍历每个区间匹配tx
for (const intervalItem of interval) {
  const leftIdx = binarySearchLeft(intervalItem.from);
  const rightIdx = binarySearchRight(intervalItem.to);
  if (leftIdx > rightIdx) continue; // 该区间无匹配tx
  // 批量提取price添加到区间
  intervalItem.txs = sortedTxs.slice(leftIdx, rightIdx + 1).map(tx => ({ price: tx.price }));
}