Conceito
Análise de algoritmos, é uma área voltada para o desenvolvimento de algoritmos mais eficientes. Pela grande variedade de possíveis resoluções de um determinado problema, nem sempre uma solução é a mais eficiente, seja em sua velocidade ou no consumo de memória. Porém, a maior parte dos problemas estão relacionados ao tempo do processamento, com base no tamanho dos dados de entrada, como por exemplo algoritmos de ordenação. Existem duas principais maneiras de se avaliar um algoritmo, a analise empírica e analise matemática.
Análise empírica
Avalia a forma como ele é executado apos a sua implementação. Com isso é levado em consideração alguns fatores como a linguagem utilizada e o hardware. Porém esse método acaba se limitando na capacidade do programador em implementar a solução para determinado problema.
Analise matemática
Permite um estudo mais individual da algoritmo, ele como uma ideia, onde somente os custos dominantes são levados em consideração. Detalhes de baixo nível como hardware e a linguagem utilizada são deixados de fora dessa analise. Instruções que não crescem com o tamanho dos dados de entrada, não são considerados na montagem da função de relação de tempo.
Código 1.1<syntaxhighlight lang="c" line="1">
- include<stdio.h>
- include<stdlib.h>
int n = 10;
int main(){
int i,j,v[10][10];
for(i=0;i<n;i++){
v[i][j] = j;
}
}
} </syntaxhighlight>
Como no código acima, as instruções contidas na linha 7 e na linha 4 de declaração e atribuição, não são contadas junto com instruções simples, como um if, comando de aritmética, entre outros.
Na linha 8 a inicialização do laço for tem duas contagens, uma de atribuição do i, outra de comparação, totalizando em 2. Em seguida a uma operação de incremento da variável i e uma comparação executadas n vezes, totalizando 2n.
Ignorando o que ocorre dentro do laço for, temos que 2 + 2n instruções. Com isso temos uma função matemática do custo do algoritmo com um laço vazio em função da quantidade de dados de entrada: f(n) = 2n + 2.
Normalmente se ignora termos que crescem lentamente, atribuições e comparações. Com isso temos uma função que se aproxima bastante da função original, essa medida de eficiência é chamada de complexidade assintótica. Constantes que multiplicam valor de n, também são descartadas, pois representam a particularidade de cada compilador e linguagem de programação, já que a ideia é ter uma analise independente destes limitadores.
O exemplo do código 1.1, no fim acaba se tornando: f(n) = n.
Notação O-Grande ou grande-O.
É a forma de analise assintótica mais utilizada. Ela parte do principio do pior caso, ou seja, nosso algoritmo não será tão ruim quanto esse resultado ou não ira ultrapassar tal resultado. Uma alternativa de se chegar a esse resultado, é utilizando da estimativa de um limite superior. Com isso, acabamos por utilizar nosso algoritmo no pior caso.
Código 1.2<syntaxhighlight lang="c" line="1"> void selectionSort(int *V, int n){
int i,j,me,troca;
for(i= 0;i <n-1;i++){
me = i;
for(j=i+1; j < n; j++){
if(V[j] < V[me]){
troca = V[i];
V[i] = V[me];
V[me] = troca;
}
}
}
} </syntaxhighlight>
Neste caso, o algoritmo de ordenação selection sort sempre ira executar o for mais interno, n vezes. Com isso temos dois laços aninhados, logo uma complexidade n², que em notação grande-O seria O(n²), ou seja, nosso algoritmo nunca sera pior do que n².
Outros tipos de análise assintótica
Notação Grande-Omega
Refere-se ao melhor caso, do algoritmo.
Notação Grande-Theta
É utilizado para analisar o limite inferior e superior.
Bibliografia
- BACKES, André. Aula 01 - Análise de Algoritmos Parte 1 Aula 02 - Análise de Algoritmos Parte 2. Disponível em <http://www.facom.ufu.br/~backes/gsi011.html>
- DROZDEK, Adam. Estrutura de dados e algoritmos em c++. 2.ed. São Paulo, Brasil: Cengage Learning, 2010, 579p.
- CORMEN, Thomas H. et al. Algoritmos: Teoria e Prática. 2.ed. São Paulo, Brasil: Elsevier Editora Ltda, 2002, 898p.