Existe uma estrutura de dados que pega uma matriz não ordenada de n
Eu realmente acho que não há, então uma prova de que não existe também é bem-vinda.
ds.data-structures
sorting
Chi-Lan
fonte
fonte
Respostas:
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.a b a b
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/logn n/logn O(logn) O(nloglogn)
fonte
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.
fonte
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/logk≤n/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.
fonte