Análise de algoritmo e análise assintótica: um resumo
BREVE DEBATE
Esses dias, participando de um processo seletivo, o gestor mencionou a minha experiência acadêmica e me perguntou o que era Análise Assintótica — confesso que eu não fazia a mínima ideia.
Quando falamos sobre a necessidade de ter uma boa base teórica, principalmente em relação aos fundamentos da programação, seja em algoritmos ou estrutura de dados, queremos apenas que as pessoas não cometam os mesmos erros que a gente.
Eu sei, assim como vocês, eu também pulei diversas etapas importantes. O que me salvou, e muito, foi a faculdade, pois tive que aprender os diversos fundamentos para conquistar o meu diploma. Só me arrependo de não ter me aprofundado mais conforme os assuntos chegavam. Fiquei ansioso para programar, assim como todo mundo.
No artigo que escrevi sobre lógica matemática, expliquei de forma muito breve os conceitos de algoritmo. Caso você não saiba sobre o que estou falando, aconselho a leitura.
EFICIÊNCIA E RECURSOS
Aposto que vocês já ouviram diversas vezes sobre a necessidade de criar uma aplicação eficiente. Mas vocês sabem como essa eficiência é calculada? Podemos usar como estimativa o tempo e o espaço — quantidade de memória, por exemplo. Porém, o resultado dessas estimativas dependem da complexidade do problema e do tamanho da solução.
Vamos usar alguns exemplos atuais?
Hoje em dia, nós, programadores, principalmente iniciantes, estamos mais preocupados em facilitar a nossa vida na hora de programar do que em criar aplicações eficientes. Responda a seguinte pergunta com honestidade:
— “Eu penso na eficiência do código na hora de programar?”
Ter um código com ferramentas mais “modernas” não significa ter uma aplicação mais eficiente. Podemos falar, por exemplo, sobre o uso de bibliotecas JavaScript. Eu amo trabalhar com React, pois facilita demais a minha vida. Só que tem alguns projetos que poderiam ser construídos apenas com HTML, CSS e JavaScript, diminuindo os recursos desnecessários que as bibliotecas possuem.
E O ALGORITMO?
“um código bem escrito é um código bem escrito”. — alguém já deve ter falado isso.
Vamos além dos conceitos de SOLID dessa vez. Quando pensamos em algoritmos, logo nos vem a cabeça uma sequência de passos ou execuções para se chegar a um determinado resultado. Mas vai além, pois ao criar um algoritmo, dependendo do tamanho do projeto, é necessário calcular a sua eficiência — os critérios são: correção, eficiência temporal e eficiência de espaço.
É importante reforçar que, apesar dos computadores estarem cada vez mais rápidos e potentes, os problemas também estão cada vez mais complexos, tornando ainda mais necessário o desenvolvimento de bons algoritmos. Também preciso lembrar que análise de algoritmos estuda o comportamento dos algoritmos e não dos programas. Enquanto o primeiro é testado utilizando matemática, o segundo é por testes de softwares — automatizados e unitários, por exemplo.
CRITÉRIOS DE EFICIÊNCIA E ANÁLISE DE COMPLEXIDADE
Como mencionei anteriormente, temos alguns critérios para calcular a eficiência do nosso algoritmo.
- Correção: De forma bem simples e objetiva, a análise de correção seria o uso de um método, geralmente um loop, para entender porque o algoritmo retorna uma resposta correta.
- análise de complexidade: procura estimar a velocidade do algoritmo, assim como os recursos gastos por ele: espaço, memória e etc.
- complexidade de tempo: f(n) = mede o tempo necessário para executar um algoritmo com problema de tamanho n
- complexidade de espaço: s(n) = memória necessário para executar um algoritmo com problema de tamanho n
Avaliação de um algoritmo.
Apesar do algoritmo não ser um programa, existem algumas similaridades que podemos levar em consideração na hora de avalia-lo.
- Simplicidade: Assim como o código, um algoritmo precisa ser simples, fácil de ser entendido e implementado.
- Eficiência: Resultados da análise de complexidade mencionados no tópico acima. Preciso lembrar que existem outros critérios também. Mas para este artigo vou me limitar a esses.
PIOR CASO, CASO MÉDIO, MELHOR CASO
Além de calcular o tempo de execução, podemos analisar pelos extremos ou limites. Eu não sei se vocês vieram de algum curso de exatas — como matemática, engenharia ou física, por exemplo — mas podemos relacionar com a função limitada.
- Pior caso: Colocamos como limite neste método o maior tempo de execução possível ou, como o nome diz, o pior que pode acontecer. Este calculo é baseado no maior tempo de execução sobre todas as entradas de tamanho n
- Caso médio: Colocamos como tempo limite neste método o tempo esperado. Então o calculo será baseado na média sobre todas as entradas.
- Melhor caso: O limite será o menor tempo de execução ou o melhor resultado que podemos ter.
O “pior caso” é o mais frequente a ser utilizado.
ANÁLISE EMPÍRICA E ANÁLISE TEÓRICA
existem alguns modelos para analisar os algoritmos: Empírica, teórica, assintótica, matemática e etc:
- Análise empírica: Rodar dois algoritmos e verificar qual é o mais eficiente. Aqui temos os seguintes passos: Entender o propósito, escolher a métrica de eficiência e a unidade de medida, usar uma linguagem de programação para escrever uma aplicação com esse algoritmo, gerar uma amostra de entradas, guardar os resultados e analisar.
- Análise teórica: Como o próprio nome diz, seria estudar e analisar o código com profundidade. Fazer perguntas, analisar os números, entender os resultados. Entender teoricamente o algoritmo.
- Análise matemática: Testar o algoritmo por meio de provas e funções matemáticas. Vocês já ouviram falar sobre análise real? é um estudo da matemática que visa prover provas sobre as funções (limite, derivada, integrais) e etc.
https://pt.wikipedia.org/wiki/An%C3%A1lise_num%C3%A9rica
https://pt.wikipedia.org/wiki/An%C3%A1lise_real
ANÁLISE ASSINTÓTICA
Assintótica vem da palavra assíntota:
Numa curva plana, linha que expressa uma distância infinita em relação ao ponto P, quando esse ponto se afasta ao infinito sem jamais encontrá-la. — dicionário.
Vejam o gráfico de um assintota no link abaixo - infelizmente não consegui colar a imagem aqui:
https://pt.wikipedia.org/wiki/Assintota
De forma bem didática, imagina que essa linha vermelha continue crescendo em direção ao valor de zero, sem nunca “tocá-lo” — tornando-se infinita.
Quando temos um número de entrada gigantesco ou o valor de n tende ao infinito, trabalhamos com a análise assintótica.
Enfim, esse capítulo foi apenas uma curiosidade para demonstrar o poder que a análise de algoritmo têm. Imagina lidar com um projeto tão absurdo a ponto de termos de lidar com limites tendendo ao infinito?
Eu preciso saber trabalhar com isso para me tornar um programador? Não! afinal, estamos lidando com valores extremamente complexos, o que seria necessário um projeto complexo. Mas é de suma importância entender a teoria, pois não sabemos os desafios que nos aguardam em nossa carreira.
A tecnologia e a ciência são lindas, né? ❤
FONTES E EXEMPLOS
https://www.dcce.ibilce.unesp.br/~aleardo/cursos/apa/apa1
