如何减少两个 for 循环的大 O (n ^ 2) 复杂度

Question

我有 2 个数组（txs 和间隔），我希望间隔包括日期介于 from 和 to（包括）之间的 txs。

const txs = [
   { price: 1, date: 1 },
   { price: 3, date: 2 },
   { price: 1.7, date: 4 }
];

const interval = [
   { from: 1, to: 2, txs: [] },
   { from: 2, to: 3, txs: [] },
   { from: 3, to: 4, txs: [] }
];

预期结果

[
   { from: 1, to: 2, txs: [{ price: 1 }, { price: 3 }] },
   { from: 2, to: 3, txs: [{ price: 3 }] },
   { from: 3, to: 4, txs: [{ price: 1.7 }] }
]

这是我在 O(n^2)

中的解决方案

for (let i of interval) {
  for (let j of txs) {
     if (j.date >= i.from && j.date <= i.to) {
        i.txs.push({ price: j.price });
     }
  }
}

这只是一个例子。真正的一个 txs 和 interval 可能有超过 10,000 个元素。有没有可以在 O(n) 或 O(n log n) 中完成的解决方案？

Answer 1

我把txs的长度叫做n，intervals的长度叫做m。在之后，您有一个 O(nlog(n)) 预计算。找到要包含的 first“txs”（如果有的话）每个间隔需要 O(logn)。添加一个 tx 应该花费 O(1) 总共 O(nlog(n) + mlog(n) +mn) = O((n+ m)log(n) +mn).
要从图片中删除那个烦人的术语 mn（“输出大小”），找到要包含的第一个 txs not 并且每个间隔代表txss 要包含的 txss，除了第一个之外还要指定这个。

对于非重叠区间，仅对两个数组排序并同时遍历可能更快，一个影响因素是相对数组大小。

如何减少两个 for 循环的大 O (n ^ 2) 复杂度

How can I reduce big O (n ^ 2) complexity of two for loops

javascript

algorithm

big-o