如何用离散来接近优化算法
How to approach optimizing algorithm with discrete
我遇到了 ，他说有一个比 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]s 的除数，花费时间 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 成本的情况下仍然受益。
我遇到了
我将如何使用离散方法解决此问题以尝试理解更快的解决方案？
任务描述：
找出列表中“幸运三元组”的数量。 “幸运三元组”被定义为“在列表 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]s 的除数，花费时间 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 成本的情况下仍然受益。