Elemento problema distinção - Element distinctness problem
Em teoria complexidade computacional , o elemento de distinção problema ou elemento problema singularidade é o problema de determinar se todos os elementos de uma lista são distintos.
É um problema bem estudado em muitos modelos diferentes de computação. O problema pode ser resolvido através da ordenação da lista e, em seguida, verificar se existem elementos iguais consecutivos; ele também pode ser resolvido no tempo esperado linear por um algoritmo aleatório que insere cada item numa tabela hash e compara apenas aqueles elementos que são colocados na mesma célula tabela hash.
Vários limites inferiores em complexidade computacional está provado por redução do problema elemento de distinção para o problema em questão, isto é, através da demonstração de que a solução do problema elemento singularidade podem ser encontrados rapidamente depois de resolver o problema em questão.
Conteúdo
complexidade da árvore de decisão
Sabe-se que, por listas de números, o problema complexidade de tempo é Θ ( n log n ), ou seja, tanto os limites superiores e inferiores em sua complexidade de tempo são de ordem da função linearithmic na árvore de decisão algébrica modelo de computação , um modelo de computação, em que os elementos não podem ser utilizados para a memória do computador de índice (como na solução tabela hash), mas apenas pode ser acedido por computação e comparando funções algébricos simples dos seus valores. Em outras palavras, um assintoticamente ótima algoritmo de complexidade de tempo linearithmic é conhecido por este modelo. O modelo de árvore de computação algébrica, basicamente, significa que os algoritmos permitidos são apenas aqueles que podem executar operações polinômio de grau limitado com os dados introduzidos e comparações dos resultados desses cálculos.
O mesmo limite inferior foi mais tarde provou para o randomizado árvore de decisão algébrica modelo.
complexidade Quantum
Sabe-se também que algoritmos quânticos pode resolver este problema mais rápido em consultas. O algoritmo é ideal por Andris Ambainis . Yaoyun Shi primeiro provou ser um apertado limite inferior quando o tamanho do intervalo é suficientemente grande. Ambainis e Kutin independentemente (e através de diferentes provas) estendeu o trabalho para obter o limite inferior para todas as funções.
Generalização: encontrar elementos repetidos
Elementos que ocorrem mais do que n / k vezes em um multiconjunto de tamanho n pode ser encontrado em tempo O ( N log k ). O problema elemento de distinção é um caso especial de k = n . Este algoritmo é ótimo sob o modelo de árvore de decisão da computação.
O algoritmo é uma generalização de um para um caso especial de k = 2 (o algoritmo maioria Boyer-Moore ), que tinha uma história bastante complicada de publicação.
Os algoritmos acima confiar apenas no teste de identidade dos elementos. Se a classificação for permitido, previamente conhecidas estatísticas de ordem encontrar algoritmos podem ser exploradas. Por exemplo, para k = 2, uma mediana pode ser encontrado no primeiro tempo linear , e, em seguida, ela pode ser facilmente testado se existem mais do que n / 2 elementos medianos. No entanto, os algoritmos acima exigem menos comparações do que os algoritmos de estatísticas de ordem.