Análise de Algoritmos c/ Python
Parte 1
Objetivo:
- Entender o porquê análise de algoritmos é importante.
O que é Análise de Algoritmos?
Quando dois estudantes iniciantes de Ciência da Computação começam a programar, comparam seus algoritmos e percebem que os dois programas feitos resolvem o mesmo problema, mas são diferentes: Há um programa melhor do que o outro?
Comparando esses dois algoritmos, notamos que a diferença única e notável é de fato os nomes das variáveis, funções/métodos. A sintaxe é exatamente a mesma. Nessa comparação, o primeiro algoritmo se mostra muito melhor escrito, já que há uma melhor escolha da nomeação de variáveis e função. Ele fica mais “legível”, um código de melhor entendimento.
Porém, a análise de algoritmos entra em questão a comparação de algoritmos, baseado em recursos computacionais. Recursos computacionais nesse caso são dois tipos importantes:
— Quantidade de memória que o algoritmo utiliza para resolver determinado problema
— Quantidade de tempo necessário para a execução do algoritmo. Conhecido como “Tempo de Execução”.
Com o código Python, podemos entender essa análise baseada no tempo de execução dos algoritmos. O Python tem o módulo time que possui a função time(). Essa função retorna o tempo de execução, em segundos, desde um ponto de início (starting point).
Aqui está o mesmo algoritmo que vimos acima. Mas agora com a função time (no ínicio e no fim do algoritmo), para retornar o tempo de execução.
Rodando a função sumOfN com parâmetro 10.000 (somar os 10.000 primeiros números), o tempo de execução do algoritmo requerido fica em torno de 0,0018 e 0,0019.
Porém, para fazer a soma dos “N” primeiros números, podemos fazer um algoritmo diferente. Sabendo que há uma equação para a soma dos “N” primeiro números, conseguimos fazer o algoritmo sem mesmo precisar iterá-lo.
- Equação da soma dos “N” primeiros inteiros:
- A função com a equação matemática e sem necessidade de iteração (sem loop):
Sem a necessidade de utilizar o for (loop), o algoritmo se mostra muito mais eficiente em questão de tempo de execução, levando muito menos tempo para rodar o código Python. Esse é o resultado da execução da função sumOfN3() com argumento de 10000, assim como no algoritmo anterior:
Esse foi apenas um pequeno exemplo de como a análise de algoritmos é significamente importante para a implementação de códigos. É claro que não é a melhor forma de mensuração, já que depende do tipo de compiladores, os programas, as máquinas utilizadas e linguagens de programação.
Uma boa forma de mensuração é a utilização do Big-O Notation (Notação Big-O) para medir a eficiência dos algoritmos em termos de tempo de execução e as performances das estruturas de dados.
