发现不同数字的乘法表的数量 [英] Find the number of distinct numbers in multiplication table

问题描述

通过上mathoverflow 这个问题

假设我有一个 N X <强> N 乘法表，什么是不同的值的数量就可以了？

Suppose I have a n x n multiplication table, what is the number of distinct values on it?

例如，一个3X3乘法表

For example, a 3X3 multiplication table

1 2 3
   2 4 6
   3 6 9

1 2 3
2 4 6
3 6 9

有 6 独特的价值观即的 [1，2，3，4，6，9] 的

到目前为止，我只有一个为O（n ² ）解决方案

So far I only have a O(n²) solution

 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（n ² ）

Is there a better approach which is less than O(n²) ?

推荐答案

现在的问题是，要使用一组验证独特性，你必须先填充它，它是为O（n ^ 2），这种或那种方式; 没有一组，你不能轻易验证，如果一个号码是唯一的，或者不...

The problem is that to use a set to verify the uniqueness, you have to populate it first, and it's O(n^2), one way or another; without a set, you can't easily verify if a number is unique or not...

作为一个方面说明：由于大O类是有些大（例如，它可以描述任何复杂的不高于的比什么，但不一定 不低于的，即。线性复杂性和二次复杂算法可以被描述为为O（n ^ 2），由于在两种情况下，复杂性 不高于的小于n ^ 2） - 因此，假设每个O（X）在这个答案的意思是大西塔，即。渐近上/下边界，使得 F（n）是在O（克（n））的装置，该K1 * G（N）＆其中; = F（N）＆其中; = K2 * G（N）（K1，K2正当然）

As a side note: since big-O class is somewhat broad (i.e. it can describe any complexity not higher than something, but not necessarily not lower, ie. both linear complexity and quadratic complexity algorithms can be described as O(n^2), since, in both cases, the complexity is not higher than n^2) - as such, assume that every O(x) in this answer means "Big Theta", ie. asymptotical up/down boundary, such that f(n) is in O(g(n)) means that k1*g(n)<=f(n)<=k2*g(n) (k1,k2 positive of course).

作为<一个href="http://mathoverflow.net/questions/108912/number-of-elements-in-the-set-1-cdots-n-times-1-cdots-n?lq=1">http://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 -

As http://mathoverflow.net/questions/108912/number-of-elements-in-the-set-1-cdots-n-times-1-cdots-n?lq=1 points out, the exact amount is asymptotically approaching a well-known value; even so, the exact value for any given n is not something that can be calculated simply, as, in essence, it's quite similar to solving http://en.wikipedia.org/wiki/Prime-counting_function -

这是说，让我们尝试总结的事实，（为什么？）标志着我懒得/累解释ATM领域，但其中有兴趣的读者 我确认（或否定）本人：

that said, let's try to summarize the facts, "(why?)" marking the fields I'm too lazy/tired to explain ATM, but which an interested reader my verify (or disprove) himself:

a）任何众所周知的公式由一个简单的函数得到的结果一（n）的当前存在，

a) no well-known formula to get the result by a simple function a(n) currently exists,

二）因为，我们必须以产生一组与所有的独特号码和返回集的基数作为结果，

b) because of that, we are required to generate a set with all of the unique numbers and return the cardinality of that set as the result,

C），因为实际数字的设定量被证明是O（N ^ 2）（请参阅参考资料），严格来说O（N ^ 2 /（log n）的^ C *（loglog N）^ 3/2）  生成组至少要花那么多的操作 - 这是我们的低约束 - 假设的我们已经知道，如果一个数字是集合或不的

c) since the amount of actual numbers in the set is proven to be o(n^2) (see the reference), strictly speaking o(n^2/(log n)^c * (loglog n)^3/2), generating the set would take at least that much operations - that's our low bound - assuming we already know if a number is in the set or not,

d）就这样，我们的算法A的复杂度C能够是虽然，充其量是使得

d) as such, complexity C of our algorithm A can be though, at best, to be such that

为O（n ^ 2）> 0（C）>为O（n ^ 2 /（log n）的^ C *（loglog N）^ 3/2）（请注意，这再$ P $只psents 微不足道的改进，纯N ^ 2！）。

O(n^2) > O(C) > O(n^2/(log n)^c * (loglog n)^3/2) (please note that this represents only minuscule improvement over pure n^2!).

这是说，我主张A进入如下：

That said, my proposition for A goes as follows:

a）由于矩阵是对称VS对角线，假设我们只分析如右上角的三角形加斜

a) since the matrix is symmetric vs the diagonal, assume we're analysing only e.g. upper right triangle plus diagonal

二）假设，你的N，任何数x =＆LT; n是在该组

b) assume that, for your n, any number x =< n is in the set

c）计算Y = INT（SQRT（N）） - 排为r的每一个角值= y是已经present在设置中，行r>Ÿ每一个对角线值 已被检查

c) calculate y=int(sqrt(n)) - every diagonal value of row r <= y is already present in the set, every diagonal value of row r > y has to be checked

c'）中N *（N + 1）/ 2-正INT（SQRT（n））的元件需要处理（加入到设置）中的常规方法

c') n*(n+1)/2-n-int(sqrt(n)) elements need to be processed (added to set) in the "conventional" method

d）现在，因为我们排除了一切可以$ P $轻松pdicted，我们进入主循环的值： 为（行r n种）//最大数量为r * N   所有X：X>（R-1）* N保证是唯一的到现在的，所以它们不需要被处理，假设我们的也不会保持设定唯一的数字！ 的;   自排的集为数字（R ^ 2; R * n）时，所有的数字范围内的（（R-1）* N，R * n）以行r是在范围内   现在，因为在行r的实际组数字A_N = 1'，2 * R，3 * R ... N * R，明显的问题是要找到   一个边界码整数Y * R满足y * R>（R-1）* N，因为这将意味着我们必须保证纽约州独有。   注：如果我们发现的（（R-1）* N）/ R的精确值是一个整数，我们可以安全地假设Y =（（R-1）* N）/ R + 1（为什么？）   并且准确的整数不是唯一的。   正因为如此，恰好有最大（NR，CEIL（N / R）），每一行中独有保证（为什么？）;我们得到这个在O（1），每行

d) now, since we ruled out all the values that can be predicted easily, we enter the main loop: for (row r < n) // max number is r * n all x : x > (r-1) * n are guaranteed to be unique till now, so they needn't be processed, assuming we wouldn't have to maintain unique numbers set!; since the row's set is for numbers (r^2;r*n), all numbers in range ((r-1)*n,r*n) in row r are in range now, since the actual set of numbers in row r is a_n = r, 2*r, 3*r ... n*r, the obvious problem is to find a "border" integer y*r such that y*r > (r-1)*n, because that would mean that we have n-y guaranteed uniques. nb if we find an exact value of ((r-1)*n)/r to be an integer, we can safely assume that y = ((r-1)*n)/r + 1 (why?), and that exact integer is not unique. because of this, there is exactly max(n-r,ceil(n/r)) guaranteed uniques in every row (why?); we get this in O(1) for every row

E）的最棘手的部分：我们已经有了一些数> =比R * R，但明显小于（R-1）* N;   这是硬范围，[R * R，（R-1）* N），其中的数目可以是或不是唯一的;   我们可以有最多I_R = MAX（0，NR-地板（N / R））的数字来检查这个范围（为什么？）   甚至天真检查此范围内的每个数字明显快于O（n）是（为什么？ - 地（N / R）相对于n因子的增长！）

e) the trickiest part: we've got some number >= than r*r, but obviously smaller than (r-1)*n; that is the "hard range", [r*r, (r-1)*n) , in which the number can be or not be unique; we can have at most i_r = max(0,n-r-floor(n/r)) numbers to check this range (why?) even naive checking every number in this range is obviously faster than O(n) (why? -floor(n/r) factor grows with respect to n !)

我们已经为O得到更好的（N ^ 2） - 我们有总和（I_R）迭代，当R =第2..N（第一行是无操作），所以实际上等于   总和R =第2..N（MAX（0，NR-地板（N / R））） - 我将无法提供一个确切的复杂性类的结果在这里，因为它不是一个pretty的数量，   让我们尝试走得更远......

we already got better than O(n^2) - we have sum(i_r) iterations, for r = 2..n (first row is no-op), so this is actually equal to sum for r=2..n(max(0,n-r-floor(n/r))) - I won't provide an exact complexity class result here, as it's not a pretty number, Let's try to go even further...

F）怎么样弹射器？

g）对于奇数行，我们不能做更多的事情（因为这会，其中包括很多东西，需要我们解决一些黄金相关的   问题，在评论中，还没有被解决了世界上最好的matematicians但已经提到过） - 但我们仍然可以   帮助我们自己，每连 - [R！

g) For odd rows, we can't do much more (since this would, amongst many things, require us to solve some prime-related problems, already mentioned in the comments, which hasn't been solved for world's best matematicians yet) - yet we still can help ourselves for every even r!

除以2河每数为＆lt; = R / 2 * n个的已处理！它要么唯一与否，我们不必在意！的。

divide r by two. every number that is <= r/2 * n has already been processed! it's either unique or not, we don't have to care!.

请注意，由于我们实际上已经下降（和大部分开端太）行的目的，其工作原理出奇的好。   因为我们做这种检查只在偶数行，我们就开始检查他们（添加设置）不从x = R *（R + 1），但是从R / 2 * N + R，而不是！

Note that since we actually dropped the ends of the rows already (and most of the beginnings too), this works surprisingly good. Since we do this check only on even rows, we just start checking them (adding to set) not from x = r*(r+1), but from r/2*n+r instead!

高），但现在，最重要的事情：如何检查他们，如果我们没有一套已经找到独有定义？可悲的是，这是主要的    问题的任意的算法，尝试下面去〜N * N / 2元迭代      - ？因为你不处理所有的值，你怎么能知道是否值已被处理过。

h) but now, the most important thing: how to check them if we don't have a set of already found uniques defined? sadly, this is the main problem with any algorithm that tries to go below ~n*n/2 element iterations - since you don't process all values, how can you know if the value has been processed or not?

我）如果有一个简单的方法来predict怎样的可能是唯一的数字很多（如％）真的是唯一的，不会有任何真正的问题就在这里，    这将是一个O（n）的问题 - 但我只是认为这是不可能的，由于上述困难

i) if there was an easy way to predict how many (eg. %) of the "potentially unique" numbers are really unique, there won't be any real problem here, it would be a O(n) problem - but I simply consider it impossible, due to above difficulties.

TL;博士 - 我呼吁任何回答努力做到严格低于Ø有心计（N ^ 2） - 你可以降到几个位，但在复杂的类  不会得到反正下降。

tl;dr - I call shenanigans on any answer trying to do it strictly below O(n^2) - you can drop a few bits below, but the complexity class won't get reduced anyway.

这篇关于发现不同数字的乘法表的数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！