Análise de Algoritmos: Eficiência e Estratégias de Ordenação
Classificado em Computação
Escrito em em 
português com um tamanho de 3,02 KB
O estudo aprofundado do algoritmo é fundamental para desenvolver aplicações eficientes. Em muitos casos, ampliar o poder computacional por meio de estratégias de hardware não tem sido suficiente, visto que diversos gargalos podem ser gerados. Assim, a melhoria por meio de software é a solução viável.
Ordenação Numérica
Trata-se de um problema clássico que possui várias estratégias para ordenar conjuntos numéricos:- Bubble Sort
- Selection Sort
- Insertion Sort
- Quick Sort
- Shell Sort
- Merge Sort
- Heap Sort
- Shaker Sort
Projeto Genoma
Identificação das 100.000 genes do DNA humano e mineração de sequências.Comunicação de Dados e Internet
Gestão dos algoritmos inteligentes de manipulação de dados trafegados e gestão de rotas.Comércio Eletrônico
Milhões (bilhões) de operações simultâneas, com necessidade de disponibilidade total.Análise de Dados para Tomada de Decisão
Indústria (produção), utilidade pública (eleições), tráfego aéreo.Problemas Difíceis
O objetivo é produzir algoritmos eficientes. Em geral, a medida de eficiência está relacionada à velocidade de execução. Porém, existem alguns problemas em que não se conhece uma solução eficiente.Algoritmos com Tecnologia
Mesmo que os PCs tivessem recursos infinitos (não é o caso), ainda assim, a análise de algoritmos seria necessária, especialmente para provar que uma solução termina e está correta.Eficiência
Algoritmos criados para resolver o mesmo problema. Muitos diferem de forma drástica em sua eficiência; uma análise pode ser feita em algoritmos de ordenação.Inserção: C1n² para ordenar n itens.
Intercalação: C3n log n para ordenar n itens.
Análise de Algoritmos
Analisar um algoritmo significa prover os recursos que o algoritmo necessitará. Ocasionalmente, recursos como memória, largura de banda, entre outros, são importantes, mas com frequência, o que se deseja medir é o tempo de computação.Em geral, pela análise de vários algoritmos candidatos para um problema, pode-se identificar o mais eficiente.
Para as análises a serem realizadas a seguir, serão adotadas a ideia de: processador sequencial, com único núcleo, máquina com instruções simples, instruções aritméticas, movimentação de dados e controle.
A seguir, será feita a análise de um algoritmo de ordenação por inserção. Em geral, o tempo de execução de um algoritmo cresce com o tamanho da entrada.