EstruturaII Ordenacao

Complexidade de algoritmos e
Classificação (Ordenação) de dados Créditos: Baseado no material do Prof. Alexandre Parra Carneiro

Complexidade de algoritmos


Antes de começarmos vamos falar um pouco a respeito da análise de complexidade de algoritmos

Considerações sobre Análise de
Complexidade


O programador deve estar ciente dos vários aspectos que influenciam a eficiência.



Objetivo: fazer uma opção “mais correta” quanto ao método de pesquisa e/ou ordenação a utilizar em um determinado cenário.



Aspectos mais relevantes:





O tempo que será gasto pelo programador para codificar determinado programa.
O tempo necessário para executar o programa.
Espaço de memória necessário para executar o programa. Aspecto: Codificação


Se o algoritmo de pesquisa ou ordenação for executado poucas vezes e existirem tempo e espaço na máquina suficientes para executá-lo


Não desperdiçar métodos. dias

programando

melhores



Ressalva: O tempo de programação nunca deve ser uma desculpa válida para usar um algoritmo inadequado.



Programador precisa conhecer os vários métodos de pesquisa e ordenação para uma escolha bem sucedida.

Aspectos: Tempo e Espaço


Na maioria dos programas, o programador deverá otimizar freqüentemente um desses aspectos à custa do outro.



Interessado na variação do tempo imposta mudança no tamanho do repositório de dados.



A eficiência de tempo é calculada pelo número de operações críticas efetuadas.



Operações críticas: (1) comparação entre chaves, (2) troca de dois registros, (3) ou movimentação de ponteiros para registros.

pela

Tempo de Execução de Algoritmos


Em alguns casos pode-se calcular exatamente o tempo de execução de um algoritmo.



Os objetos matemáticos de que precisamos são funções que mapeiem as entradas possíveis ao tempo (ou espaço) necessário!



O aspecto mais relevante da entrada que é determinante do tempo e do espaço necessários para executar o algoritmo é o tamanho!


O tamanho ou