Analise Assintótica de Algorítimos

O mundo ao nosso redor está em constante mudança, principalmente se considerado o lado tecnológico das coisas, isso exige que profissionais das ares que envolvem TI estejam sempre se atualizando. Para que ocorra essa atualização e percepção profissional dos métodos e atividades que se tornaram obsoletos com o passar do tempo, os profissionais contam com um auxilio um tanto quanto especial: A matemática. É ela que torna possível a criação e a avaliação de novos modelos , ponto inicial de processos de desenvolvimento de todas as inovações tecnológicas.

Dentro dessa perspectiva não basta apresentar uma solução para um determinado problema. Na analise de algorítimos é importante apresentar a melhor solução ou até a solução mais viável para o momento e com os recursos disponíveis. Nunca deixando de se analisar os pontos positivos e negativos.

Para criar ou utilizar um algorítimo é importante determinar seu desempenho. Todo algoritmo é projetado e planejado para executar determinadas funções que exigem memoria e tempo de execução. E essa execução pode requerer diferentes algorítimos, sendo assim necessário analisar qual deles é mais eficiente em diversos aspectos.

Analisar um algorítimo significa prever os recursos de que ele necessitará. Em geral, memoria, largura de banda ou hardware são preocupações primordiais. Mas frequentemente é o tempo de computação que se deseja medir. Esse tempo de execução ou custo de utilização pode ser medido por meio de sua execução de um computador real, anotando-se o tempo levando em conta que depende do compilador, do hardware e quantidade de memória principal e secundaria.

Outro detalhe importante é o tamanho da entrada de dados no algorítimo. Para valores pequenos, para qualquer algorítimo, mesmo ineficiente, gastará pouco tempo. O que faz o programador escolher um algorítimo não é o seu desempenho sobre tamanhos de entrada pequenos, mas sim sobre tamanhos de entradas grandes. Logo, sua analise é feita sobre tamanhos de entradas grandes. Analisa-se então comportamento assintótico da função de complexidade de tempos dos algorítimos, sua eficiência assintótica.

Para isso existem os tipos de notação assintótica ou os elementos de analise assintótica. São utilizadas para representar o comportamento assintótico das funções de complexidade de tempo de algorítimos.
Seguindo esta linha de raciocínio temos:

• Notação O: Utilizada para da um limite superior
• Notação Ômega: Utilizada para dar um limite inferior
• Notação Teta: Utilizada para dar um limite "firme"
• Entre outras derivadas das já mencionadas.

Alguns algorítimos são recursivos, e tem por base a chamada a si próprio, dividindo um problema maior em sub-problemas menores.

Por terem uma estrutura diferenciada das demais estruturas algorítmicas, requerem maneiras um pouco diferentes para calcular-se a notação assintótica, contado com auxilio dos metodos iterativos e mestre.

De modo geral um método de uma classe que chama a si mesma é dita recursiva, e a analise do tempo de execução de um algorítimo recursivo é um pouco diferente dos algorítimos que não possuem recursividade.

Por exemplo, o calculo do fatorial de um numero n, pode ser elaborado por recursividade, e como a solução do problema de tamanho n depende da solução de problemas menores, o tempo de execução também é representado através do tempo de execução do problema para tamanhos menores.

Portanto, desenvolver uma solução nas basta, mas sim a melhor solução utilizando a ferramenta de analise de algorítimos.

Por,

Igor Matheus Diniz - Integrante do PET Computação