Поиск максимального элемента массива является делителем другого элемента

Question

Учитывая массив ненулевых целых чисел N. Напишите функцию, которая возвращает максимальный элемент массива, который является делителем какого-либо другого элемента тот же массив. Если этого номера нет, верните 0. Я знаю, как решить в O(n^2). Возможно ли это сделать быстрее?

Answer 1

Прежде всего обратите внимание, что вы предполагаете, что тестирование, если целое число A делит целое число B, может быть выполнено в O (1). Я предполагаю, что вы также предполагаете, что предварительные вычисления (например, создание divisibility graph) не допускаются.

С integer factorization (для которого не известен полиномиальный алгоритм) не является вариантом, вы не можете делать быстрее, чем O (n^2) (наихудший случай).

Например, при вводе {11,127, 16139} (все целые числа являются целыми числами, каждое целое число меньше, чем следующее), вы не можете избежать проверки всех пар.

Answer 2

Я сделал это так

int f(int* a, int size) 
{ 
    int max = 0; 
    for (int i = 0; i < size; i++) 
     for (int j = 0; j < size; j++) 
      if (a[i] > a[j] && a[i] % a[j] == 0 && a[j] > max) 
       max = a[j]; 
    return max; 
} 

Answer 3

Я играл с вашей проблемой на некоторое время и нашел порой лучше, чем грубая силу раствора.

Он основан на идеи:

• Мы можем выполнить поиск в таком порядке, что большие кандидаты делителей испытываются первым. Таким образом, мы можем прекратить поиск, как только найдем делитель.

• Один из способов проверить, если какой-то кандидат divw является делителем для числа w, чтобы вычислить r = floor(w/divw), а затем проверить, что r * divw == w. Интересно, что когда он терпит неудачу, мы можем вычислить верхний предел для следующего кандидата дивизора w как topw = floor(w/(r + 1)). Поэтому мы можем отказаться от чего-либо между divw и topw.

Образец для этой второй точки: Представьте, что мы тестируем, если divw = 10 является делителем w = 12, вычислим r = floor(12/10) = 1 и topw = floor(w/2) = 6. Таким образом, нам не нужно проверять, являются ли числа в наборе между 7 и 9 включительно, являются делителями для 12.

Для реализации этого алгоритма я использовал кучу, чтобы сохранить числа в наборе, используя в качестве ключа следующий кандидат на дивизор, который должен быть протестирован.

Итак ...

1. Инициализировать кучу толкая каждый элемент, который его предшественник, как его больший потенциальный делитель.

2. Поместите первый элемент из кучи (w) и проверьте, является ли потенциальный кандидат на делитель (divw) на самом деле делителем.

3. Если да, то вернуть его как самый большой делитель

4. Calculate topw для w, divw; поиск следующего элемента в наборе divw', который равен или меньше topw (с использованием двоичного поиска); если найдено, нажмите w, divw' снова в очереди.

5. , если очередь не заполнена, goto 2.

Реализация в Common Lisp доступна here!

Я думаю, что вычисление теоретических вычислительных затрат для этого алгоритма было бы сложным, особенно для среднего случая, поэтому я не собираюсь это делать!

После того, как он работает десяток раз, он, кажется, ведет себя лучше, чем подход грубой силы, когда N велико, а числа рассеяны (что означает, что вероятность того, что одно число будет делителем другого, будет низким). С другой стороны, грубая сила, кажется, быстрее, когда N является низкой или когда числа плотно распределены в небольшом диапазоне (что означает, что вероятность того, что число является делителем другого, велико).