Учитывая положительное целое число x и отсортированный массив положительных чисел A
Существует ли какой-либо алгоритм быстрее, чем O(N), чтобы определить, является ли какой-либо элемент из A кратным x? В A нет отрицательных элементов.
Наивный цикл A один раз является моей единственной идеей до сих пор, я не знаю, есть ли способ использовать тот факт, что A сортируется, чтобы ускорить его.
Это, по-видимому, очень сильно зависит от размера x и количества элементов внутри A и, в частности, количества кратных кандидатов x внутри A.
Двоичный поиск определенного числа внутри A занимает время O (log (n)) (n - количество элементов внутри A), поэтому, если есть k возможные кратные x между первый и последний элемент A, для проверки всех них потребуется O(k * log(N)). Если это число меньше, чем n, вы можете использовать этот алгоритм, иначе просто выполните линейный поиск.
(Кроме того, существует, вероятно, несколько небольших оптимизаций выше алгоритма. Например, после того, как вы проверили x*i (и не нашли его), вы можете использовать позицию, где x*i должна была быть нижней границей, когда поиск x*(i+1) вместо самого первого элемента массива.)
HT @tobias_k комментарий.
Вы можете решить эту проблему в ~ O(n/x) (обновление может быть O(N*log(N)/X^2))). Вы выполняете двоичный поиск для всех кратных x одновременно. Где вы разбиваете каждое пространство поиска на каждую итерацию и когда пространство поиска не может содержать кратное x, вы прерываете эту ветвь. Поэтому вместо бинарного поиска каждое значение вы двоичный поиск всех значений, но только для тех ветвей, которые по-прежнему содержат допустимый множитель в пределах их диапазона. Лучше всего это то, что он полностью предотвращает исследование одного и того же пространства дважды, что делает худший случай x = 1 или O(n/1) O(n). В лучшем случае он будет знать, что диапазон не может содержать кратное и прерывать в O (1).
Поскольку вам гарантируется худший случай O (n), в котором вы в основном пропускаете каждый проклятый поиск кеша (помните, что в реальных условиях это может оказаться более важным, чем временная сложность, следовательно, проверять такие вещи). Вы получили бы теоретическую временную сложность, которая могла бы быть лучше, чем O (n), но никогда не хуже этого (за исключением того, что прыжки вокруг массива будут пропускать кеши, поскольку это то, как компьютеры фактически работают в реальном мире).
Как и было предсказано, увеличение скорости зависит от значения k (x).
Это начинается быстрее, чем исходный цикл при k = ~ 128. (коэффициент деления)
Усечение ветвей управляет реальным миром, превосходящим необработанный цикл. Я предполагаю, что значение n не будет иметь большого значения, поскольку оно, похоже, масштабируется примерно одинаково, но, возможно, непосредственно проверяет, что это лучше.
Примечание: по характеру этого кода он пропускает удвоения, что является разницей в подсчетах.
public class MultipleSearch {
public static void main(String[] args) {
Random random = new Random();
int[] array = new int[500000000];
for (int i = 0, m = array.length; i < m; i++) {
array[i] = Math.abs(random.nextInt());
}
Arrays.sort(array);
for (int k = 1; k < 16777216; k *= 2) {
long time;
time = System.currentTimeMillis();
binaryFactorLocator(array, k);
System.out.println("Factors found multi: " + (System.currentTimeMillis() - time) + " @" + k);
time = System.currentTimeMillis();
loopFactorLocator(array, k);
System.out.println("Factors found loop: " + (System.currentTimeMillis() - time) + " @" + k);
}
}
public static void loopFactorLocator(int[] array, int k) {
int count = 0;
for (int i = 0, m = array.length; i < m; i++) {
if (array[i] % k == 0) {
count++;
//System.out.println("loop: " + array[i] + " value at index " + i + " is a proven multiple of " + k);
}
}
System.out.println(count + " items found.");
}
public static void binaryFactorLocator(int[] array, int k) {
int count = binaryFactorLocator(0, array, k, 0, array.length);
System.out.println(count + " items found.");
}
public static int binaryFactorLocator(int count, int[] array, int k, int start, int end) {
if (start >= end) { //contains zero elements. (End is exclusive)
return count;
}
int startValue = array[start]; //first value
int endValue = array[end - 1]; //last value;
if (startValue / k == endValue / k) { //if both values are contained within the same factor loop.
if (startValue % k == 0) { //check lower value for being perfect factor.
//System.out.println("multi-binary: " + startValue + " value at index " + start + " is a proven multiple of " + k);
return count + 1;
}
return count; //There can be no other factors within this branch.
}
int midpoint = (start + end) / 2; //subdivide
count = binaryFactorLocator(count, array, k, start, midpoint); //recurse.
count = binaryFactorLocator(count, array, k, midpoint, end); //recurse.
return count;
}
}
Эта реализация должна быть довольно прочной, поскольку она обрезает цикл в элементах start/k == end/k, он должен пропускать двойной (иногда он может расщепляться между двумя удвоенными значениями). Очевидно, что рекурсивный, как это, вероятно, не будет оптимальным и должен быть, возможно, переписан с меньшим стеком стоп-кода.
474682772 items found.
Factors found multi: 21368 @1
500000000 items found.
Factors found loop: 5653 @1
236879556 items found.
Factors found multi: 21573 @2
250000111 items found.
Factors found loop: 7782 @2
118113043 items found.
Factors found multi: 19785 @4
125000120 items found.
Factors found loop: 5445 @4
58890737 items found.
Factors found multi: 16539 @8
62500081 items found.
Factors found loop: 5277 @8
29399912 items found.
Factors found multi: 12812 @16
31250060 items found.
Factors found loop: 5117 @16
14695209 items found.
Factors found multi: 8799 @32
15625029 items found.
Factors found loop: 4935 @32
7347206 items found.
Factors found multi: 5886 @64
7812362 items found.
Factors found loop: 4815 @64
3673884 items found.
Factors found multi: 3441 @128
3906093 items found.
Factors found loop: 4479 @128
1836857 items found.
Factors found multi: 2100 @256
1953038 items found.
Factors found loop: 4592 @256
918444 items found.
Factors found multi: 1335 @512
976522 items found.
Factors found loop: 4361 @512
459141 items found.
Factors found multi: 959 @1024
488190 items found.
Factors found loop: 4447 @1024
229495 items found.
Factors found multi: 531 @2048
243961 items found.
Factors found loop: 4114 @2048
114715 items found.
Factors found multi: 295 @4096
121964 items found.
Factors found loop: 3894 @4096
57341 items found.
Factors found multi: 195 @8192
61023 items found.
Factors found loop: 4061 @8192
28554 items found.
Factors found multi: 106 @16384
30380 items found.
Factors found loop: 3757 @16384
14282 items found.
Factors found multi: 65 @32768
15207 items found.
Factors found loop: 3597 @32768
7131 items found.
Factors found multi: 35 @65536
7575 items found.
Factors found loop: 3288 @65536
3678 items found.
Factors found multi: 17 @131072
3883 items found.
Factors found loop: 3281 @131072
1796 items found.
Factors found multi: 13 @262144
1900 items found.
Factors found loop: 3243 @262144
873 items found.
Factors found multi: 6 @524288
921 items found.
Factors found loop: 2970 @524288
430 items found.
Factors found multi: 3 @1048576
456 items found.
Factors found loop: 2871 @1048576
227 items found.
Factors found multi: 2 @2097152
238 items found.
Factors found loop: 2748 @2097152
114 items found.
Factors found multi: 1 @4194304
120 items found.
Factors found loop: 2598 @4194304
48 items found.
Factors found multi: 0 @8388608
51 items found.
Factors found loop: 2368 @8388608
В предыдущей попытке я пробовал простой дихотомический поиск, но, как было указано, на самом деле ничего не ведет.
Вот моя лучшая попытка. Я сомневаюсь, что это стоит хлопот, и это может быть даже медленнее для случаев реального мира, но здесь идет.
Если у вас есть массив A [0..n] отсортированных положительных целых чисел, и вы хотите проверить, существует ли кратное положительное целое число X в [i..j], где 0≤i
If i>j then A[i..j] ist empty and thus contains no multiple of X
Else if A[i] % X = 0 or A[j] % X = 0 then A[i..j] contains a multiple of X
Else if A[i] / X = A[j] / X then A[i..j] contains no multiple of X
Else A[i..j] contains a multiple of X iff A[i+1..(i+j)/2] or A[(i+j)/2+1..j-1] contains a multiple of X
Я предполагаю, что сложность будет O (n/X) ish, поэтому, на самом деле, не улучшение в великой схеме вещей.
Отредактировано для добавления: Если ваши данные действительно необычны, это может реально помочь. Во многих случаях это может повредить:
Я считаю, что ответ на общий вопрос - нет. Предположим, что для A следующая структура: i -ный элемент A ai задается i*x +1, поэтому в A нет элементов, кратных x. Однако вы никогда не сможете сэкономить время, используя описанную выше "обманку"... вам в основном нужно сделать выбор, основываясь на ваших знаниях A и x. В основном вы можете выбирать между O (N) и O (K), где K - число возможных кратных x в A, вы можете достичь O (K) с помощью хэширования, так что i*x in A станет постоянная работа (в среднем...).
Две вещи, которые нужно попробовать - сначала найдите первый элемент в массиве, отличный от x. Не нужно искать нижнюю половину. Бинарный поиск может это сделать. Это сократит время в некоторых случаях, но если самый первый элемент больше x, то нет необходимости, очевидно. Затем, идентифицировав раздел с возможными кратными x, выполните двоичный поиск, если выполняете один поток, или если вы можете запускать несколько потоков, разделять верхнюю половину на сегменты и каждый отдельный поиск по нити. Я думаю, что это может быть наиболее эффективным способом, но с учетом следующих оговорок.
Если первый элемент, превышающий x, достаточно мал в массиве, вы потратите больше времени на создание бинарного поиска, чем на линейное сканирование.
Существует также стоимость бинарных поисков. Если вы массив не очень большой, вы будете менее эффективны, чем линейный поиск. Я не говорю о порядке алгоритма. Я рассматриваю только время выполнения.
Если вы можете выполнять несколько потоков, для их настройки также требуется довольно высокая стоимость. Если ваш массив неприлично длинный, вы не сможете получить какие-либо выгоды, сделав это тоже. Тем не менее, если это несколько миллионов предметов, вы можете извлечь выгоду, разделив их на более мелкие куски. Я бы сказал, что для этого сценария будет редко.
Вычитайте x из A итеративно. Остановитесь, если какой-либо результат равен 0.
Что касается вычитаний, вы делаете это 1 + {max(A) DIV x} раз в худшем сценарии таким образом, так как вы должны вычитать x из максимального элемента A после того, как все остальные уже не прошли проверку, и еще раз (следовательно, 1) к самому самому максимальному элементу, который также терпит неудачу, как 7 DIV 3 = 2, поэтому в трех итерациях:
Это по-прежнему считается O(n), но заканчивается быстрым, делая целочисленное вычитание в массиве.