Estrutura de dados baseada em comparação para localizar itens

34

Existe uma estrutura de dados que pega uma matriz não ordenada de nn itens, executa o pré-processamento em O ( n )O(n) e responde a consultas: existe algum elemento xx na lista, cada consulta no pior momento O ( log n )O(logn) ?

Eu realmente acho que não há, então uma prova de que não existe também é bem-vinda.

Chi-Lan
fonte
3
(1) Não sei por que você pode dizer "É claro que considero o tempo esperado", porque você não afirma "esperado" na sua pergunta. Por favor tente de afirmar a sua pergunta mais precisamente antes de dizer (2) Por favor, defina “claro.” “Non-Hashable.”
Tsuyoshi Ito
2
(1) Entendo. Obrigada pelo esclarecimento. Se alguém perguntasse “Você se importa com o tempo de execução?”, A resposta seria realmente “claro”. :) (2) Eu acho que “A única ação permitida é comparar dois valores na lista” é muito mais preciso do que apenas dizer “não-lavável”. Você pode editar a pergunta para que as pessoas não precisem ler os comentários para entender o que significa “não lavável”?
Tsuyoshi Ito
3
A propósito, se você não pode provar, por que você sabe que é impossível? Se for um exercício em um livro ou em uma aula, você está perguntando em um site errado.
Tsuyoshi Ito
6
Esta é a sua pergunta: existe uma estrutura de dados que pega uma matriz não ordenada de n itens, executa o pré-processamento em O (n) e responde a consultas: existe algum elemento x na lista, cada consulta no pior momento O (log n)?
precisa saber é o seguinte
2
@Filip: Isso é fácil de ver? Se for verdade, concordo que resolve a questão.
Tsuyoshi Ito

Respostas:

30

Aqui está uma prova de que é impossível. Suponha que você possa construir essa estrutura de dados. Construa. Em seguida, escolha n / log n itens aleatoriamente na lista, adicione ϵ a cada um deles, onde ϵ é menor que a diferença entre dois itens na lista e execute as consultas para verificar se algum dos itens resultantes está no Lista. Você realizou O ( n ) consultas até o momento.n/lognϵϵO(n)

Gostaria de afirmar que as comparações que você fez são suficientes para dizer se um item a na lista original é menor ou maior que qualquer novo item b . Suponha que você não saiba. Então, como esse é um modelo baseado em comparação, você não saberia se a era igual a b ou não, uma contradição da suposição de que sua estrutura de dados funciona.abab

Agora, como os itens n / log n que você escolheu eram aleatórios, suas comparações têm, com alta probabilidade, informações suficientes para dividir a lista original em listas n / log n, cada uma com o tamanho O ( log n ) . Ao classificar cada uma dessas listas, você obtém um algoritmo de classificação aleatório de tempo O ( n log log n ) baseado apenas em comparações, uma contradição.n/lognn/lognO(logn)O(nloglogn)

Peter Shor
fonte
Algumas dicas para ajudar a entender a prova (supondo que eu a entenda corretamente, é claro): os itens b devem ser preenchidos pelos itens após a adição de ϵ ; o modelo de comparação garante que você saiba quais dos casos a b e a b são válidos; as listas n / log n estão em 'ordem crescente': todo elemento em qualquer lista superior é maior que todo elemento em qualquer lista inferior; após as consultas originais você tem bastante informação para fazer as listas de volta os itens que você escolheu aleatoriamente,bϵababn/logn
Alex ten Brink
(continued) note that you don't even have to explicitly be able to build the list in the provided time for the proof to hold.
Alex ten Brink
I don't quiet understand this proof. The final contradiction is off "algorithm based solely on comparisons", but in the first steps of our algorithm we added ϵϵ to each item (further, "where ϵϵ is smaller than the difference between any two items on the list"). Why are we still justified that our algorithm still only comparison based if we assumed our items have a non-discrete total order on them?
Artem Kaznatcheev
5
@Artem: Your original input consists of elements xXxX. Then you construct a new set X=X×{0,1}X=X×{0,1}; you represent an original xXxX as (x,0)X(x,0)X and a modified x+ϵx+ϵ as (x,1)X(x,1)X. Now you use the black box algorithm; the algorithm compares elements of XX to each other; to answer such queries, you only need to compare a constant number of elements of XX to each other. Hence everything should be doable in the comparison model, with a constant overhead.
Jukka Suomela
1
@Aryabhata: it does. What is the O(log2n)O(log2n) algorithm?
Peter Shor
24

I believe here is a different proof, proving the impossibility of an O(logkn)O(logkn) query time structure, with O(n)O(n) pre-processing.

Suppose in the preprocessing you do O(n)O(n) comparisons, leading to a partial order.

Now consider the size AA of the largest antichain in that. Since these elements are not comparable, for us to have an O(logkn)O(logkn) query algorithm, we must have that A=O(logkn)A=O(logkn).

Now by Dilworth's theorem, there is a partition of size AA, into chains.

Now we can complement the algorithm to determine the chains in the partition. We can determine if two elements are comparable by creating a directed graph of comparisons and doing a reachability analysis. This can be done without any additional comparisons. Now just brute force out each possible partition of size AA to determine if it is a partition of chains.

Once we have the chains, we can merge them to give an O(nloglogn)O(nloglogn) comparisons algorithm for sorting the whole list.

Aryabhata
fonte
1
This is a nice idea. And if you could show that the chain partition must be known to the algorithm then you could use mergesort to show that it would only take an additional O(n log log n) comparisons to sort the whole input, rather than using Jensen. But there is a problem: why must the preprocessing algorithm construct a chain partition? A chain partition must exist, yes, but that's very different from it being known to the algorithm.
David Eppstein
8
Ok, I now believe this proof. And it shows more strongly that to achieve polylog query time you have to use a number of comparisons that's within an additive O(nloglogn)O(nloglogn) of sorting. Nice. By the way, the chain partition can be found in polynomial time from the set of comparisons already performed, rather than needing a brute force search, but that doesn't make any difference for your argument.
David Eppstein
6
The proofs actually show that you must have either Ω(nlogn)Ω(nlogn) preprocessing or Ω(n)Ω(n) for each query. Of course both are tight. This shows that binary search and linear search are the only "interesting" search algorithms (at least in the classical world).
Yuval Filmus
1
@Yuval: maybe you should write up this observation as an actual answer, because it seems to me that you have to do a moderate amount of work to get the above result from the proofs in the answers.
Peter Shor
1
@Yuval: thinking about the proofs, I only see that you must have either Ω(nlogn)Ω(nlogn) preprocessing or Ω(n1ϵ)Ω(n1ϵ) query time for all ϵϵ. It's possible to have o(nlogn)o(nlogn) preprocessing time and O(n/logn)O(n/logn) query time. One can divide the list into lognlogn lists of size n/logn each in time θ(nloglogn) using repeated median-finding.
Peter Shor
0

As Peter Shor's answer notes, to rule out membership in a comparison-based model, we need to know how the element compares with every member. Thus, using k<n random queries (the number of members smaller than the queried nonmember is random), we gain Θ(nlogk) information relative to having n unsorted values. Therefore, for some constant c>0, using cnlogk preprocesssing, we cannot have cnlogk/k query cost. This is optimal up to a constant factor since we can sort the data into k=k/logkn/logn approximately equal buckets (each bucket unsorted) in O(nlogk)=O(nlogk) time, which allows O(n/k) query cost.

In particular, using O(n) preprocessing, we cannot have o(n) query cost. Also, o(nlogn) preprocessing corresponds to k in O(nε) for every ε>0 and thus Ω(n1ε) query cost.

Dmytro Taranovsky
fonte