Algoritmos

FACULDADE ANHANGUERA

Amanda Dias Oliveira - RA: 1099153844 -

Fábio Carmo - RA: 1053003750 -

Hitallo de Souza Santos - RA: 1053012008 -

Kelvin Rodrigues Ferreita - RA: 5661132826 -

Miller Leonardo Macêdo - RA: 1053008028 -

Classificação e Pesquisa

Relatório 4 – Árvores – Parte 2

Belo Horizonte

2012

ETAPA 4

Passo 1 - Apresentar explicações sobre as análises realizadas neste estudo: por que houve reclamações de clientes com relação a desempenho e se existe um algoritmo de ordenação que pode ser usado como padrão para qualquer.

Os algoritmos tem características únicas nos quais apresentam desempenho superior conforme a entrada no sistema (quantidade de dados) e recursos disponíveis:

➢ Selection

Características Desvantagens

Interessante para arquivos pequenos O fato de o arquivo já estar ordenado não ajuda

em nada, pois o custo continua quadrático.

O algoritmo não é estável.

➢ Bubble

Características Desvantagens

Para o usuário, não há vantagem. Percorre a estrutura muitas vezes, por isto se torna ineficiente.

➢ Insertion

Características Desvantagens

Eficiente quando a estrutura está "quase ordenada".

Boa escolha caso deseja inserir elementos aos poucos. Estável. O pior caso quando os itens estão originalmente na ordem reversa.

➢ Merge

Características Desvantagens

Recomendado para aplicações com restrição de tempo. A complexidade do merge sort é a mesma para o pior, médio e melhor caso. Independente da situação dos dados no vetor, o algoritmo irá sempre dividir e intercalar os dados. Utiliza memória auxiliar, já que utiliza outros vetores para as subordenações. Alto consumo de memória

➢ Shell

Características Desvantagens

A razão da eficiência do algoritmo ainda não é conhecida. Ninguém ainda foi capaz de analisar o algoritmo. A sua análise contém alguns problemas matemáticos muito difíceis. O que se sabe é que cada incremento não deve ser múltiplo do anterior.

Shellsort é uma ótima opção para arquivos de

tamanho moderado. O tempo de execução do algoritmo é sensível à

ordem inicial do arquivo.

O método não é estável,

➢ Quick

Características Desvantagens

O pior caso ocorre quando, sistematicamente, o pivô é escolhido como sendo um dos extremos de um arquivo já ordenado.

Isto faz com que o procedimento Ordena seja

chamado recursivamente n vezes, eliminando apenas um item em cada chamada.

Extremamente eficiente para ordenar arquivos de dados.

Necessita de apenas uma pequena pilha como

memória auxiliar. Em seu pior caso, realiza o mesmo número de comparações que o Bubble sort.

Não é estável.

Possui várias versões, o que pode trazer diversos problemas e diferenças de desempenho, como as versões utilizadas nos testes.

➢ Binary Tree Search

Características Desvantagens

Ordenação rápida. Foi um dos melhores métodos de ordenação testados.

Melhor rendimento com menor quantidade de elementos.

As árvores binárias são uma das estruturas

de dados mais importantes devido a grande

aplicabilidade das mesmas. Torna o processo de busca mais lento, devido a possibilidade de alta profundidade da árvore.

Seu desempenho depende da quantidade e ordem dos elementos de entrada.

 

➢ AVL Tree

Características Desvantagens

Objetiva buscas mais rápidas. Ordenação lenta devido aos inúmeros processos de calculo dos fatores de balanceamento e balanceamentos.

Sua ordenação foi uma das mais demoradas.

➢ B-Tree

Características Desvantagens

Arvore-B é uma estrutura balanceada projetada para trabalhar com dispositivos de armazenamento secundário como dispositivos magnéticos. Utilizada para manipular muitos dados, sendo utilizada por SGBDs