Complexidade de Algoritmos

Trabalho de Estruturas de Dados 2 – DAD2
Complexidade de Algoritmos

Willian Rudi Erdmann

1 Resumo: Muitas vezes as pessoas, quando, começam a estudar algoritmos, perguntam-se qual a necessidade de desenvolver novos algoritmos para problemas que já têm solução. A performance é extremamente importante na informática, pelo que existe uma necessidade constante de melhorar os algoritmo. Apesar de parecer o contraditório, com o aumento da velocidade dos computadores, torna-se cada vez mais importante desenvolver algoritmos mais eficientes, devido ao aumento constante do
“tamanho” dos problemas a serem desenvolvidos.
Palavras-chave: complexidade, algoritmo, notação, caso.

2 Complexidade de Algoritmo
A complexidade de um algoritmo consiste na quantidade de “trabalho” necessária para a execução, expressa em função das operações fundamentais, as quais variam de acordo com o algoritmo, e em função do volume de dados.
A comparação entre algoritmos, para execução de determinado problema, pode ser realizada de duas formas:
Comparação
de forma empírica, execução dos algoritmos e comparação dos tempos de execução, conhecido como comparação a Posteriori, ou ainda denominado como benchmarking;
A comparação sem a execução, ou seja, de forma analítica, conhecida como comparação a priori, a qual serão considerados dois fatos: a entrada ( fornecimento de dados) e o numero de instruções executadas pelo algoritmo.
Cada algoritmo tem diferentes proporções de crescimento. A taxa de crescimento gerada por esta proporção é o que determina a – complexidade de algoritmo - , que podemos verificar com melhor facilidade qual algoritmo tem melhor desempenho na execução. Vejamos:
Tamanho da Tempo
– Tempo
–
entrada
Algoritmo X Algoritmo Y

Figura 1 – Quadro comparativo de execução de algoritmo
X e algoritmo Y.

2.1Tipos de Complexidade
2.1.1 Espacial:
Este tipo de complexidade representa o espaço de memória usado para executar
o