Подтвердить что ты не робот

Найти количество различных чисел в таблице умножения

Вдохновленный этот вопрос о mathoverflow

Предположим, что у меня есть таблица n x n, каково количество различных значений на ней?

Например, таблица умножения 3X3

1 2 3
 2 4 6
 3 6 9

имеет 6 уникальные значения, а именно [1, 2, 3, 4, 6, 9]

Пока у меня есть решение O (n 2)

 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 2)?

4b9b3361

ОТВЕТЫ

Ответ 1

Проблема заключается в том, что для использования набора для проверки уникальности вы должны сначала заполнить его, а O (n ^ 2) - так или иначе; без набора, вы не можете легко проверить, уникален ли номер или нет...

В качестве побочного примечания: поскольку класс big-O несколько широк (т.е. он может описывать любую сложность не выше чем-то, но не обязательно не ниже, т.е. как алгоритмы линейной сложности, так и квадратичной сложности могут быть описаны как O (n ^ 2), поскольку в обоих случаях сложность не выше n ^ 2) - как таковое, предположим, что каждый O (x) в этом ответе означает "Большая тэта", т.е. асимптотическая граница вверх/вниз, такая, что 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) как таковая сложность C нашего алгоритма A может быть, в лучшем случае, таковой, что

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) теперь, поскольку мы исключили все значения, которые можно легко предсказать, мы вводим основной цикл: для (строка r < n)//максимальное число r * n все x: x > (r-1) * n гарантированы, что они уникальны до сих пор, поэтому их не нужно обрабатывать, предполагая, что нам не нужно поддерживать набор уникальных чисел!; так как множество строк для чисел (r ^ 2; r * n), все числа в диапазоне ((r-1) n, rn) в строке r находятся в диапазоне теперь, поскольку фактический набор чисел в строке r равен a_n = r, 2 * r, 3 * r... nr, очевидная проблема заключается в том, чтобы найти "граничное" целое число yr такое, что y * r > (r-1) * n, потому что это означает, что мы гарантируем n-y uniques. nb, если мы находим точное значение ((r-1) * n)/r как целое число, можно смело предположить, что y = ((r-1) * n)/r + 1 (почему?), и что точное целое не является уникальным. из-за этого существует точно max (n-r, ceil (n/r)), гарантированный uniques в каждой строке (почему?); мы получаем это в 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) - мы имеем итерации суммы (i_r), для r = 2..n(первая строка не-op), так что это фактически равно сумма для r = 2..n(max (0, n-r-floor (n/r))) - Я не буду предлагать точный результат класса сложности здесь, так как это не очень большое число, Попробуем еще пойти...

f) Как насчет катапульты?

g) Для нечетных строк мы не можем делать больше (поскольку это, во многом, требует от нас решения некоторых простых проблемы, уже упомянутые в комментариях, которые еще не решены для лучших мировых математиков), - но мы все еще можем помогите себе для каждого четного r!

разделите r на два. каждое число, которое является <= r/2 * n, уже обработано! это либо уникально, либо нет, нам не все равно!

Обратите внимание, что, поскольку мы фактически опущены концы строк уже (и большинство из них тоже), это работает на удивление хорошо. Поскольку мы делаем это только для четных строк, мы просто начинаем их проверять (добавляем в набор) не от x = r * (r + 1), а от r/2 * n + r вместо!

h), но теперь самое главное: как их проверить, если у нас нет набора уже найденных уникальных? к сожалению, это главная  проблема с любым алгоритмом, который пытается пройти ниже ~ n * n/2 итераций элементов   - поскольку вы не обрабатываете все значения, как вы можете узнать, было ли это значение обработано или нет?

i), если бы был простой способ предсказать, сколько (например.%) "потенциально уникальных" чисел действительно уникально, здесь не будет никакой реальной проблемы,  это была бы проблема O (n), но я просто считаю ее невозможной из-за вышеперечисленных трудностей.

tl; dr - я вызываю shenanigans при любом ответе, пытаясь сделать это строго ниже O (n ^ 2) - вы можете сбросить несколько бит ниже, но класс сложности не будет уменьшен в любом случае.

Ответ 2

Я убежден, что существует лучшее, чем O (n²) решение. Я не смог его найти, но я считаю, что я на правильном пути, всего несколько математических идей.

Это мой алгоритм-under-development:

public static int numberOfDistinctResults(int n) {
    if (n == 1) {
        return 1;
    }

    // runs a prime-number sieve in O(n log log n)
    Factorization.initialize(n); 
    int total = 1;
    for (int i = 2; i <= n; i++) {
        total += i;
        // divs[i] == 0 iff i is prime, or the lowest prime that divides i
        if (Factorization.divs[i] == 0) {
            // i is prime; for all j<=i, j*i is brand new; nothing to substract
        } else {
            // i is non-prime; discard already-seen decompositions
            total -= magic(n); // <--- this part needs work
        }
    }
    return total;
}

В настоящее время это выполняется под O (n²), пока magic(n) может работать под O (n). Однако я не смог найти такую ​​функцию magic. По существу, я добавляю термины из oeis.org/A062854 - на этом графике, похоже, много структуры.

См. oeis.org/A027424 для большого фона по всему вопросу (все перечисленные алгоритмы, похоже, являются O (n²), хотя), и oeis.org/A108407 для списка значений для magic(n) и нескольких связанных последовательностей. Ниже следует небольшая таблица значений, в которой вы можете видеть, что простые числа легки (0 для вычитания), но непротивления жесткие (без непосредственного отношения к факторизации или существующим факторам):

f(1) = 1 ( prev + 1 = 1 - 0)
f(2) = 3 ( prev + 2 = 2 - 0)
f(3) = 6 ( prev + 3 = 3 - 0)
f(4) = 9 ( prev + 3 = 4 - 1)
    4 = 2^2; available = 2·3
f(5) = 14 ( prev + 5 = 5 - 0)
f(6) = 18 ( prev + 4 = 6 - 2)
    6 = 2·3; available = 2^2·3·5
f(7) = 25 ( prev + 7 = 7 - 0)
f(8) = 30 ( prev + 5 = 8 - 3)
    8 = 2^3; available = 2^2·3·5·7
f(9) = 36 ( prev + 6 = 9 - 3)
    9 = 3^2; available = 2^3·3·5·7
f(10) = 42 ( prev + 6 = 10 - 4)
    10 = 2·5; available = 2^3·3^2·5·7
f(11) = 53 ( prev + 11 = 11 - 0)
f(12) = 59 ( prev + 6 = 12 - 6)
    12 = 2^2·3; available = 2^3·3^2·5·7·11
f(13) = 72 ( prev + 13 = 13 - 0)
f(14) = 80 ( prev + 8 = 14 - 6)
    14 = 2·7; available = 2^3·3^2·5·7·11·13
f(15) = 89 ( prev + 9 = 15 - 6)
    15 = 3·5; available = 2^3·3^2·5·7·11·13
f(16) = 97 ( prev + 8 = 16 - 8)
    16 = 2^4; available = 2^3·3^2·5·7·11·13
f(17) = 114 ( prev + 17 = 17 - 0)
f(18) = 123 ( prev + 9 = 18 - 9)
    18 = 2·3^2; available = 2^4·3^2·5·7·11·13·17
f(19) = 142 ( prev + 19 = 19 - 0)
f(20) = 152 ( prev + 10 = 20 - 10)
    20 = 2^2·5; available = 2^4·3^2·5·7·11·13·17·19
f(21) = 164 ( prev + 12 = 21 - 9)
    21 = 3·7; available = 2^4·3^2·5·7·11·13·17·19
f(22) = 176 ( prev + 12 = 22 - 10)
    22 = 2·11; available = 2^4·3^2·5·7·11·13·17·19
f(23) = 199 ( prev + 23 = 23 - 0)
f(24) = 209 ( prev + 10 = 24 - 14)
    24 = 2^3·3; available = 2^4·3^2·5·7·11·13·17·19·23
f(25) = 225 ( prev + 16 = 25 - 9)
    25 = 5^2; available = 2^4·3^2·5·7·11·13·17·19·23
f(26) = 239 ( prev + 14 = 26 - 12)
    26 = 2·13; available = 2^4·3^2·5^2·7·11·13·17·19·23
f(27) = 254 ( prev + 15 = 27 - 12)
    27 = 3^3; available = 2^4·3^2·5^2·7·11·13·17·19·23
f(28) = 267 ( prev + 13 = 28 - 15)
    28 = 2^2·7; available = 2^4·3^3·5^2·7·11·13·17·19·23
f(29) = 296 ( prev + 29 = 29 - 0)
f(30) = 308 ( prev + 12 = 30 - 18)
    30 = 2·3·5; available = 2^4·3^3·5^2·7·11·13·17·19·23·29
f(31) = 339 ( prev + 31 = 31 - 0)
f(32) = 354 ( prev + 15 = 32 - 17)
    32 = 2^5; available = 2^4·3^3·5^2·7·11·13·17·19·23·29·31
f(33) = 372 ( prev + 18 = 33 - 15)
    33 = 3·11; available = 2^5·3^3·5^2·7·11·13·17·19·23·29·31
f(34) = 390 ( prev + 18 = 34 - 16)
    34 = 2·17; available = 2^5·3^3·5^2·7·11·13·17·19·23·29·31
f(35) = 410 ( prev + 20 = 35 - 15)
    35 = 5·7; available = 2^5·3^3·5^2·7·11·13·17·19·23·29·31
f(36) = 423 ( prev + 13 = 36 - 23)
    36 = 2^2·3^2; available = 2^5·3^3·5^2·7·11·13·17·19·23·29·31
f(37) = 460 ( prev + 37 = 37 - 0)
f(38) = 480 ( prev + 20 = 38 - 18)
    38 = 2·19; available = 2^5·3^3·5^2·7·11·13·17·19·23·29·31·37
f(39) = 501 ( prev + 21 = 39 - 18)
    39 = 3·13; available = 2^5·3^3·5^2·7·11·13·17·19·23·29·31·37