我看到这篇答案说有一种“花哨的离散数学方法”可以比O(n^2)更快地解决问题。然而我无法理解如何在O(n^2)以下完成链接问题。
使用离散数学,我该如何尝试解决此问题,以便理解更快的解决方案?
任务描述:
在一个列表中找到“幸运三元组”的数量。“幸运三元组”被定义为“在列表lst中,对于任何三个数的组合( lst[i],lst[j],lst[k] ),其中i < j < k,并且 lst[i]除以lst[j],lst[j]除以lst[k]。”
我看到这篇答案说有一种“花哨的离散数学方法”可以比O(n^2)更快地解决问题。然而我无法理解如何在O(n^2)以下完成链接问题。
使用离散数学,我该如何尝试解决此问题,以便理解更快的解决方案?
任务描述:
在一个列表中找到“幸运三元组”的数量。“幸运三元组”被定义为“在列表lst中,对于任何三个数的组合( lst[i],lst[j],lst[k] ),其中i < j < k,并且 lst[i]除以lst[j],lst[j]除以lst[k]。”
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
m
的每个数字的最小质因数,以便能够在O(log lst[i])
的时间内分解每个列表元素。然后我们需要一个额外的步骤来生成约数(在我们的条件下可以认为数量是恒定的),并执行类似于第一种方法的遍历。如果n
非常大,这种方法可能有所帮助,即使需要额外的m log m
成本也能获益。