Ответ 1
Общая проблема 3SUM-Hard и вопрос о том, есть ли более квадратичный алгоритм, открыт.
Итак, если вам нужен более быстрый алгоритм, вам, вероятно, потребуется использовать тот факт, что они 32-разрядные.
Определите, существует ли A + B = C в массиве из n целых чисел
Это проблема, которую мой друг получил в качестве домашней работы (в алгоритме и классе структуры данных). Он спросил меня об этом. Однако я не могу решить эту проблему и думал об этом в течение нескольких последних дней.
В диапазоне [0, 2 31 -1] есть n случайных целых чисел (могут быть дубликаты. Определите, удовлетворяют ли 3 номерам этих чисел A + B = C.
Сначала я придумал наивный алгоритм, что O (n 2 log n). Затем я придумал алгоритм, что O (n 2). Вот псевдокод:
sort(a); // non-descending
for (i = 0; i < n; i++) {
j = i; k = i + 1;
while (j < n && k < n) {
if (a[i] + a[j] == a[k])
return true;
else if (a[i] + a[k] < a[j])
k++;
else
j++;
}
}
return false;
Однако проблема заключается в том, что 1 < n <= 10 6. Я считаю, что O (n 2) слишком медленный. Мое решение не использует случайность. Однако я не уверен, что это важная часть проблемы.
Ответы
Ответ 2
Если числа являются случайными, любой наихудший алгоритм O(n^2) (включая ваш) будет работать очень быстро. На самом деле практическая сложность будет O(n*logn) (сложность сортировки).
Это очень похоже на quicksort, где у нас O(n*logn) среднее значение и крошечная вероятность удара O(n^2).
10^6 случайные числа дают нам ~ 10^6*10^6 "почти случайные" суммы в диапазоне ~ 0..10^9. Какова вероятность того, что одна из этих 10^12 случайных сумм будет равна заданному случайному значению в целочисленном диапазоне? Довольно хорошо.
Теперь, какова вероятность того, что одна из этих 10^12 случайных сумм будет равна одному из 10 ^ 6 заданных случайных значений? 100%, говоря поэтично.
Я реализовал ваше предлагаемое решение, для n = 10^6 он выполняет в среднем 5000-10000 операции в самом внутреннем цикле. Так много для O(n^2). Сортировка - это самая дорогостоящая операция.
PS. Вы можете уменьшить сложность дальше и сделать ее еще O(1), если вы обновите решение, чтобы использовать хэш вместо сортировки.
PS 2. Программа тестирования в java, для справки. Запустите его и убедитесь сами.
int n = 1000000;
int[] a = new int[n];
// generate random array
Random r = new Random();
for (int i = 0; i < n; ++i) {
do {
a[i] = r.nextInt();
} while (a[i] < 0);
}
Arrays.sort(a);
// number of operations inside main loop
int ops = 0;
// main logic, pretty much as OP described it
boolean found = false;
for (int i = 0; i < n && !found; ++i) {
int j = i;
int k = i + 1;
while (k < n) {
++ops;
if (a[i] > a[k] - a[j]) {
++k;
} else if (a[i] < a[k] - a[j]) {
++j;
} else {
System.out.println(a[i] + " + " + a[j] + " = " + a[k]);
found = true;
break;
}
}
}
System.out.println(ops);
Ответ 3
Алгоритм, использующий хеширование, занимает 10-900 микросекунд в Python (в среднем: 200 медианов: 60):
#!/usr/bin/env python
import random
L = frozenset(random.sample(xrange(2**31), 10**6))
print next(((a,b,a+b) for a in L for b in L if (a + b) in L), None)
Это O(N**2), но кажется, что он достаточно быстр.
Для сравнения, амортизированная операция O(N) создания frozenset занимает 270 миллисекунды (в 1000 раз медленнее, чем поиск), и для создания случайного списка требуется 0.9 секунд.
Примечание. random.sample не возвращает повторяющиеся элементы, если входная последовательность содержит уникальные элементы, поэтому frozenset не отбрасывает никаких элементов в приведенном выше примере. Чтобы решить проблему для случайной последовательности, которая позволяет повторять элементы, мы должны использовать две структуры данных:
#!/usr/bin/env python
import random
L = [random.randrange(2**31) for _ in xrange(10**6)]
S = frozenset(L)
print len(L), len(S)
print next(((a, b, a+b) for a in L for b in L if (a + b) in S), None)
Выход
1000000 999762
(2055933464, 83277289, 2139210753)
Ответ 4
Я получаю O (n log n) при измерении этого по отсортированным спискам:
from bisect import bisect_right
import cProfile as prof
import random
def find3sum(T):
if len(T) < 3:
return None
n = len(T)
top = T[-1]
for i in range(len(T)-1):
b = top - T[i]
if b < T[i]:
return None
k = bisect_right(T, b, i, n-1)
while k > i:
c = T[i] + T[k]
j = bisect_right(T, c, k, n-1)
if j <= k:
break
elif T[j] == c:
return (i, k, j)
else:
k -= 1
def test_one(a):
a = sorted(a)
r = find3sum(a)
i, k , j = r
assert a[i] + a[k] == a[j]
def test():
n = 100000
max = 200000
random.seed(0)
for _ in range(100):
a = [random.randint(0,max) for _x in xrange(n)]
test_one(a)
a = range(n)
test_one(a)
prof.run('test()')
Это результаты (об одном вызове для деления пополам на элемент):
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.002 0.002 183.764 183.764 <string>:1(<module>)
200 0.005 0.000 89.996 0.450 find2sum.py:25(test_one)
1 17.269 17.269 183.762 183.762 find2sum.py:31(test)
200 35.096 0.175 79.601 0.398 find2sum.py:5(find3sum)
10000000 44.958 0.000 52.398 0.000 random.py:160(randrange)
10000000 23.891 0.000 76.289 0.000 random.py:224(randint)
1 0.000 0.000 0.000 0.000 random.py:99(seed)
19599982 44.077 0.000 44.077 0.000 {_bisect.bisect_right}
1 0.000 0.000 0.000 0.000 {function seed at 0x9a1972c}
600 0.001 0.000 0.001 0.000 {len}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
10000000 7.440 0.000 7.440 0.000 {method 'random' of '_random.Random' objects}
301 0.635 0.002 0.635 0.002 {range}
200 10.390 0.052 10.390 0.052 {sorted}
Существует несколько оптимизаций, которые могут значительно сократить время выполнения (например, пропустить числа пробегов, равные уже проверенным).
Ответ 5
A + B = C, следовательно B = C-A или = C-B
Вышеупомянутая проблема может быть выполнена в O (n) сложности с использованием хеш-таблицы.
var C; // the sum you are looking for
for(each element)
X = C - element
boolean exists = lookup for X in hash table
if (exists) combination A+B=C exists in the given input
else hashtable.put(element)
Надеюсь, что это поможет.