如何优化离散算法

Question

我看到这篇答案说有一种“花哨的离散数学方法”可以比O(n^2)更快地解决问题。然而我无法理解如何在O(n^2)以下完成链接问题。

使用离散数学，我该如何尝试解决此问题，以便理解更快的解决方案？

任务描述：

在一个列表中找到“幸运三元组”的数量。“幸运三元组”被定义为“在列表lst中，对于任何三个数的组合( lst[i]，lst[j]，lst[k] )，其中i < j < k，并且 lst[i]除以lst[j]，lst[j]除以lst[k]。”

- user760900

---

确切的引用是：“可能有一些更好的算法，使用花哨的离散数学来更快地完成它。”“可能有”和“一定有”之间存在很大的区别。前者意味着作者不知道这样的解决方案，而后者则意味着作者知道这样的解决方案存在。 - user3386109

也许有一种方法可以将元素链接成除数链，只需通过原始数组迭代一次... - Daniel

@user3386109 我的问题更多关于如何思考找到这样一个解决方案的过程。 - user760900

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成本也能获益。

- גלעד ברקן