2

现在我有一个表达式y=0.5*a+0.7*b+0.4*c，where 0<a,b,c<1。假设有一个用于 的值的列表a,b,c，例如：

(a,   b,   c)
---------------
(0.9, 0.4, 0.6)
(0.5, 0.8, 0.4)
(0.7, 0.4, 0.8)
(0.9, 0.2, 0.1)
...

是否有一些快速的方法可以找到 的最高k=3值y？

我知道蛮力的方法是枚举(a,b,c)计算的每个元组y，然后找到y的k个最大值，但是当元组的数量很大时，这种方法似乎效率不高。所以欢迎任何其他方式！

4

3 回答 3

2

使用 QuickSelect 平均会给你一个 O(n) 的复杂度：

  1. 假设有 N 个元素并且 y=f(a,b,c)，为 (a,b,c) 中的每一个计算长度为 N 的数组 Y（也将 (a,b,c) 的索引添加到 Y供您稍后需要的反向参考）。
  2. 在 Y 上使用 QuickSelect 获得 (Nk) 阶统计量，并获得结果 Y。元素 Y[Nk-1] 到 Y[N-1] 将是您的 k 个最大元素。
  3. 将 Y[Nk-1] 排序为 Y[N-1] 以获得您的结果。
于 2013-03-26T03:38:20.787 回答
2

遍历每个元组。当您读入它时，评估其上的表达式，并随时维护一个包含前 3 个值的数组。

尝试比这更聪明的问题在于，如果您的元组列表很大，那么您的程序花费的时间将完全被阅读它所支配，没有任何聪明可以让您摆脱困境。评估您的表达式和使数组与前三个值保持最新的开销将是完全微不足道的，只需在阅读部分顶部的一些说明。

（至于为什么我建议将您的最高值保存在一个数组中，而不是像堆这样的花哨的东西：当 k=3 时，任何使用大量指令执行的东西的持续开销，或者需要足够的内存并不总是会获得缓存命中，它会超过数据结构提供的任何渐近收益。）

于 2013-03-26T03:34:59.093 回答
1

不管你做什么，你仍然需要遍历表中的每个元组，所以这至少是一个O(n)操作。只有前 3 个值，您可以硬编码一个大小为 3 的数组和if所需的检查。

O(n)因此，鉴于您必须至少遍历整个表一次，在这种情况下您不会做得更好。

于 2013-03-26T03:37:26.377 回答