Изменения

Перейти к: навигация, поиск

Meet-in-the-middle

19 байт убрано, 23:15, 16 декабря 2012
Нет описания правки
// <tex>sum</tex> - массив сумм <tex> a + b </tex>, <tex> cnt </tex> - счетчик массива <tex> sum </tex>
'''findsum()'''
sum <tex> sum \leftarrow \emptyset </tex> '''for''' a = 0 <tex> a \in A rightarrow </tex>N - 1 '''for''' b = 0 <tex> b \in A rightarrow </tex>N - 1 <tex> sum[cnt].s <tex>\leftarrow </tex> A[a] + B[b] </tex> <tex> sum[cnt].a <tex>\leftarrow a </tex>a <tex> sum[cnt].b <tex>\leftarrow b </tex>b <tex> cnt++ </tex> '''sort'''<tex>(sum)</tex> '''for''' c = 0 <tex> c \in A rightarrow </tex>N - 1 '''for''' d = 0 <tex> d \in A rightarrow </tex>N - 1 '''if''' сумма <tex> -(A[c] + A[d]) </tex> есть в массив <tex> sum </tex> index <tex> index \leftarrow </tex> индекс суммы <tex> -(A[c] + A[d]) </tex> '''return''' <tex>(sum[index].a, sum[index].b, A[c], A[d]) </tex>
'''return''' "No solution"
Итоговое время работы <tex> {O(N^2\log{N}}) </tex>.
28
правок

Навигация