离散优化算法的探讨

Question

我遇到了this answer，他说有一个比O(n^2)更快的“复杂离散数学”。我不明白如何在O(n^2)下进行链接问题。

我将如何用离散的方法来处理这个问题，以尝试理解一个更快的解决方案？

任务说明：

在一个列表中找到“幸运三倍”的数目。"Lucky三元组“定义为”在列表1中，对于任何三重类(lsti、lstj、lstk)的组合，i

Answer 1

我们似乎没有足够的信息来回答，因为答案也取决于列表中的最大元素m。有两种方法可以比O(n^2)更快地完成，如果是n^2 > n * sqrt(m)或n^2 > m * log(m) + n * log(m)。

在第一种情况下，我们可以使用直接枚举遍历每个lst[i]的除数器，占用时间O(sqrt(lst[i]))，并查找它们中的多少，已经记录了谁的已见除数。(对于我们的讨论来说，除数是不变的，因为在我们的条件下，除数与m和n相比是可以忽略不计的。)例如,

2 8 5 16

2  -> nothing to do
8  -> divisors 2 4
      record {8: 1 divisor seen}
5  -> no divisors seen
16 -> divisors 2 4 8
      found 8 with 1 count in our record
      
Total 1 triple

在第二种方法中，我们预先计算了从2到m的每个数的最小素数，从而使我们能够对O(log lst[i])中的每个列表元素进行因子分解。然后，我们需要额外的一步来生成除数(在我们的条件下可以再次考虑常量的数量)，并执行与第一个类似的遍历。如果n非常大，这种方法可能会有所帮助，这样尽管增加了m log m成本，但仍能从中受益。