如何高效地找出低于阈值的最大值？

Question

我有两个列表。列表L1包含所有正整数，列表L2包含正数(例如0.01、0.1、0.5、3、5、10、100....)。

给定一个小的正数M(例如0.10948472)，从L1中找到a,b和从L2中找到c，使得(b/a)*c最大化但仍然<=M。

请注意，列表L2是固定的（长度大约为7000），列表L1具有可变长度（可以具有单个元素或多达3000个元素）。

我们如何有效地设计算法来解决这个问题？我在考虑对列表L1使用分治方法将其分成两部分再合并，但没有成功。有没有人可以高效地解决它？

更新：目前我已经想出了一些低效但正确的解决方案：首先对' L1 '进行排序。将'L1'分成两个块：一个块是前N-1个元素，另一个块是最后一个元素。假设最佳的a,b,c已经在L1的前N-1个元素中找到，我将检查是否可以在第一个块中找到一些a和第二个块中找到b（仅一个元素）以及一些c，使得(b/a)*c更好。由于我必须循环遍历L2中的每个元素，尽管它是nlogn，但仍然显得很慢。

- ADS_Auckland

---

你是不是先用了一种低效的方法来做这件事？ - Tobias Brösamle

是的，我想出了两种低效但正确的解决方案。请让我知道问题的最新情况，谢谢。 - ADS_Auckland

我猜可以通过创建所有可能的b/a和d/c数组并对它们进行排序，以O((n^2) * log(n^2))的时间复杂度完成。你想要实现什么样的时间复杂度？ - dWinder

@dWinder 我正在尝试至少实现O(nlogn) - ADS_Auckland

在O(nlog n)中，n是什么意思？从技术上讲，您有两个不同长度的数组，称它们为n1（长度为L1）和n2（长度为L2）。我认为您可以获得O(n1 * n2 * log(n1))，而且由于n2是固定的，因此在技术上是O(n*log n) - 但这似乎有些作弊。 - Hans Olsson

Answer 1

这个问题是3SUM-hard，因此你不太可能做得比Theta(n^2)更好。如果我理解正确，你目前的算法是O(n^2 log n)，这并没有留下太多改进的空间。

- David Eisenstat

---

考虑到L2是固定的，我认为当n=|L2|时，这个复杂度是O(n log n)。 - Dave

Answer 2

据我所了解，对于给定的a/b组合，您不需要循环遍历L2中的每个元素。将L2按升序排序。然后假设您从L1选择第一个a/b组合。对于c，您可以选择L2中间的元素，即索引为3500并乘以a/b。如果答案小于M，则可以选择更高索引处的元素，例如在7000 * 3/4处的5250。如果答案仍然较小，请继续提高。如果相反地，(a/b)*c超过了M，请选择较低的索引。您可以收敛到该特定a/b组合的最大化c值。

附言：不用说，在对L1和L2进行排序之后，您可以添加一个if语句来消除那些对于任何L2或L1的值都将始终超过M的元素。

- Shaheer Bin Arif

Answer 3

将L1按升序排序。假设|L1|=n。这是 O(n log n)。

对于L2中的每个元素（方程式中的'c'），执行以下操作（因为L2是固定的，所以只需要O(1)次）。

1. For the first element in L1 (which we'll treat as the 'a' in the equation), use binary search on L1 to find a second element (the 'b') s.t. (b/a)*c is maximized but still <=M.
2. Now, we'll move on to the next element in L1. Note that we're increasing the denominator, so the numerator will either stay the same or increase. We'll just iterate rather than using binary search.
3. repeat step 2.

在第2步和第3步中，我们跟踪迄今为止发现的a、b和c的最佳值。

运行时间：O（n log n）用于排序，然后在步骤2中，我们只从每个值一次递增分子或分母，因此这是O（n）+ O（n）= O（n）。

这利用了L2被固定的优势。如果|L2|= m且m不固定，则需要O（n log n）+ O（m*n）。

- Dave

---

嗨，戴夫，感谢您的建议。在第2步中，“分子要么保持不变，要么增加”：这意味着我们将一步一步向右移动当前位置，直到找到最大化的值，对吗？ - ADS_Auckland

@ADS_Auckland 是的！ - Dave