Eliminação de duplicatas. Neste capítulo, vimos que a eliminação de duplicatas é simples quando se cria uma árvore binária de busca. Descreva como você realizaria a eliminação de duplicatas usando apenas um array subscritado. Compare o desempenho da eliminação de duplicatas baseada em array com o desempenho da eliminação de duplicatas baseada em árvore de busca binária.
Passo 1
Uma eliminação de duplicatas baseada em árvore de busca binária faz uma busca binária em cada nó. A complexidade de tempo deste algoritmo é
porque para n elementos fazemos uma busca binária de complexidade de tempo .
Passo 2
Por outro lado, a complexidade de tempo do algoritmo de eliminação de duplicatas para um único array subscrito é O(n^2)O(n2 ) para um array não classificado e O(n)O(n) para um array ordenado.
O desempenho da eliminação de duplicatas em uma matriz não classificada é tão ruim porque temos que comparar cada elemento na matriz com todos os elementos posteriores.
Passo 3
Podemos concluir que o algoritmo de eliminação de duplicatas tem o melhor desempenho em um único array com subscrito ordenado.
O desempenho do algoritmo de eliminação de duplicatas baseado em árvore de pesquisa binária é melhor do que em uma matriz com subscrito único não classificado.
Resposta
Ver o desenvolvimento.