Árvore de decisão inferiores para encontrar dois elementos de matriz soma para zero

Question

Eu tenho que resolver este exercício:

.

Dado uma matriz não ordenada $ a [1], \ LDOTs, um [n] $ de inteiros positivos e negativos, determinar se há dois índices $ i \ neq j $ tal que $ a [i] + a [j]= 0 $ .Estabelecer um limite inferior para o problema usando o Técnica de árvore de decisão.

A solução deve ser $ Ω (\ log s (n)) $ , onde $ s (n) $ é o número de soluções possíveis, neste caso $ n ^ 2 $ .

Mas, eu não entendo porque o número de soluções possíveis é $ n ^ 2 $ em vez de $ \binom {n} {2} $ .

Answer 1

Você está certo que há apenas $ \ binom {n} {2} $ muitas soluções desequivalentes. Felizmente, $ \ ômega (\ log \ binom {n} {2})=ômega (\ log n) $ , então não há muita diferença entre < span class="contentor de matemática"> $ \ binom {n} {2} $ e $ n ^ 2 $ , a este respeito. .

No entanto, este é um limite inferior muito ruim. Você não especificou quais consultas são permitidas, mas assumindo que você tem permissão para calcular sinais de polinômios de grau constante, então eu esperaria uma $ \ ômega (n \ log n) $ < / Span> Limite inferior, já que a distinção do elemento de problema semelhante tem um limite tão baixo. Isso também corresponde ao limite superior obtido pela classificação (assumindo que seu modelo suporta isso).

De fato, isso é apenas 2sum (um irmão do mais famoso problema do 3SUM), e uma $ \ ômega (n \ log n) $ Baixa inferior foi provado por Chan, Gasarca e Kruskal em seu papel Limites superiores e inferiores refinados para 2 montá-lo .