algorithm - 在乘法表中查找不同数字的数量

Question

灵感来自 this question on mathoverflow

假设我有一个 x 乘法表，的个数是多少不同的值 就可以了？

例如，一个 3X3 的乘法表

1 2 3
2 4 6
3 6 9

有 6 唯一值，即 [1, 2, 3, 4, 6, 9]

到目前为止我只有一个 O(n2) 解决方案

 public static void findDistinctNumbers(int n) {

    Set<Integer> unique = new HashSet<>();

    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            unique.add(i*j);
        }
    }
    System.out.println("number of unique values: " + unique.size());
  }

有没有比 更好的方法O(n2) ?

Answer 1

问题在于，要使用集合来验证唯一性，您必须先填充它，并且它是 O(n^2)，一种或另一种方式；
没有集合，您无法轻松验证数字是否唯一...

作为旁注:由于 big-O 类有点广泛(即它可以描述任何不高于某物的复杂性，但不一定
不低，即。线性复杂度和二次复杂度算法都可以描述为 O(n^2)，因为在这两种情况下，复杂度
不高于 n^2) - 因此，假设此答案中的每个 O(x) 都表示“大 Theta”，即。渐近上/下边界，使得
f(n) 在 O(g(n)) 中意味着 k1*g(n)<=f(n)<=k2*g(n)(当然 k1,k2 为正)。

如 https://mathoverflow.net/questions/108912/number-of-elements-in-the-set-1-cdots-n-times-1-cdots-n?lq=1指出，确切的金额是
渐近地接近一个众所周知的值；即便如此，任何给定的准确值 n不是可以简单计算的东西，
因为，本质上，它与解决 http://en.wikipedia.org/wiki/Prime-counting_function 非常相似。 ——

也就是说，让我们试着总结一下事实，“(为什么？)”标记了我懒得/厌倦了解释 ATM 的领域，但有兴趣的读者
可以验证(或反驳)自己:

a) 目前不存在通过简单函数 a(n) 得到结果的众所周知的公式，

b) 因此，我们需要生成一个包含所有唯一数字的集合，并返回该集合的基数作为结果，

c) 由于集合中实际数字的数量被证明是 o(n^2)(参见引用资料)，严格来说 o(n^2/(log n)^c * (loglog n)^3/2 ),
生成集合至少需要那么多操作——这是我们的下限——假设我们已经知道一个数字是否在集合中，

d) 因此，我们的算法 A 的复杂度 C 最多可以是这样的

O(n^2) > O(C) > O(n^2/(log n)^c * (loglog n)^3/2)(请注意，这仅表示对纯 n^2 的微小改进)。

也就是说，我对 A 的提议如下:

a) 由于矩阵与对角线对称，假设我们只分析例如右上角三角形加对角线

b) 假设，对于你的 n，任何数 x =< n 在集合中

c) 计算 y=int(sqrt(n)) - 行 r <= y 的每个对角线值已经存在于集合中，行 r > y 的每个对角线值
必须检查

c') n*(n+1)/2-n-int(sqrt(n)) 个元素需要在“常规”方法中处理(添加到集合)

d) 现在，由于我们排除了所有可以轻松预测的值，我们进入主循环:
for (row r < n)//最大数量为 r * n
到目前为止，所有 x : x > (r-1) * n 都保证是唯一的，因此不需要处理它们，假设我们不必维护唯一的数字集!
由于该行的集合用于数字 (r^2;r*n)，因此第 r 行中范围 ((r-1)n,rn) 中的所有数字都在范围内
现在，由于第 r 行中的实际数字集是 a_n = r, 2*r, 3*r ... nr，显而易见的问题是找到
一个“边界”整数 yr 使得 y*r > (r-1)*n，因为这意味着我们有 n-y 保证的唯一值。
nb 如果我们发现 ((r-1)*n)/r 的精确值是一个整数，我们可以安全地假设 y = ((r-1)*n)/r + 1(为什么？)，
并且那个确切的整数不是唯一的。
正因为如此，每一行中都有 max(n-r,ceil(n/r)) 保证唯一性(为什么？)；我们在每行的 O(1) 中得到这个

e) 最棘手的部分:我们有一些数字 >= 比 r*r，但明显小于 (r-1)n；
那是“硬范围”， [rr, (r-1)*n) ，其中数字可以是唯一的，也可以不是唯一的；
我们最多可以有 i_r = max(0,n-r-floor(n/r)) 数字来检查这个范围(为什么？)
即使简单地检查这个范围内的每个数字也显然比 O(n) 快(为什么？-floor(n/r) 因子相对于 n 增长!)

我们已经比 O(n^2) 更好 - 我们有 sum(i_r) 迭代，对于 r = 2..n(第一行是无操作)，所以这实际上等于
sum for r=2..n(max(0,n-r-floor(n/r))) - 我不会在这里提供确切的复杂性类结果，因为它不是一个漂亮的数字，
让我们试着走得更远……

f) 弹射器怎么样？

g) 对于奇数行，我们不能做更多(因为在很多事情中，这需要我们解决一些与素数相关的问题)
问题，已经在评论中提到了，还没有为世界上最好的数学家解决) - 但我们仍然可以
帮助自己每一个偶数!

将 r 除以 2。 <= r/2 * n 的每个数字都已经被处理了!它要么独特，要么不独特，我们不必关心!

请注意，由于我们实际上已经删除了行的结尾(以及大部分开头)，因此效果出奇地好。
因为我们只在偶数行上做这个检查，我们只是开始检查它们(添加到集合)不是从 x = r*(r+1) 而是从 r/2*n+r 开始!

h) 但现在，最重要的是:如果我们没有定义一组已找到的唯一值，如何检查它们 ?可悲的是，这是主要的
任何试图低于 ~n*n/2 元素迭代的算法的问题
- 由于您没有处理所有值，您如何知道该值是否已被处理？

i) 如果有一种简单的方法可以预测有多少(例如 %)的“潜在唯一”数字是真正唯一的，那么这里就不会有任何真正的问题，
这将是一个 O(n) 问题 - 但由于上述困难，我只是认为这是不可能的。

tl; dr - 我在任何试图严格低于 O(n^2) 的答案上都称其为恶作剧 - 你可以在下面降低几位，但无论如何都不会降低复杂性等级。