A criação de um algoritmo pode parecer uma tarefa simples à primeira vista: definir uma sequência de passos em uma linguagem de programação e ver a funcionalidade ganhar vida no computador. Mas, e se nos aprofundarmos um pouco mais nesse processo, e nós preocuparmos com eficiência? Será que seus algoritmos são eficientes? Nesse artigo, vamos aprender um pouco sobre como podemos analisar a eficiência de nossos algoritmos.
Tempo e complexidade
Imagina esperar dias para ver o resultado do seu algoritmo? Dá um desconforto só de imaginar, não é mesmo? Mas, é o que pode acontecer com problemas complexos solucionados de forma não eficiente, são exemplos: o problema do caixeiro viajante, o problema da programação de horários ou o problema da coloração de grafos.
Esses são só alguns exemplos, e você pode até pensar que nunca topará com esses problemas, mas, e se eu te contar que o problema do caixeiro viajante, é usado no planejamento de rotas, estando presente em aplicativos de GPS. A programação de horários está em instituições escolares, universidades e locais de trabalho. E a coloração de grafos, na conectividade da internet que você está utilizando agora mesmo!
Mas não se engane, mesmo algoritmos simples com uma entrada muito grande, se mal otimizados, podem demorar anos para serem processados! Ainda neste artigo, irei apresentar um exemplo.
Bom, acredito que com essa introdução, deu para notar a importância de algoritmos eficientes para resolução de diferentes tipos de problemas, dado que estes estão tão presentes no nosso dia a dia. Mas como analisar a eficiência de um algoritmo?
Um pouco mais sobre tempo…
Existem duas medidas possíveis para se analisar um algoritmo, tempo de execução, e espaço em memória. Vamos considerar apenas o tempo de execução hoje, tudo bem?
Dito isso, dizemos então que o tempo de execução de um algoritmo é proporcional ao número de operações elementares realizadas pelo algoritmo. Logo, o tempo de execução depende do tamanho de sua entrada. Por exemplo, se o algoritmo precisa ordenar uma lista de números, o tempo de execução será maior quanto maior a lista a ser ordenada, concorda?
Através dessa relação, é possível então observar o comportamento do algoritmo ao longo de sua execução, e verificar para uma entrada n, o tempo T deste algoritmo, logo, temos a função matemática T(n) para um algoritmo, que descreve a quantidade de tempo gasta para processar a entrada n.
O pior e o melhor caso
Para cada tamanho de entrada, existe um tempo de execução mínimo e um tempo de execução máximo que o algoritmo pode levar. O tempo de execução mínimo é chamado de melhor caso. O tempo de execução máximo é chamado de pior caso. O melhor caso ocorre quando a entrada é a mais fácil possível para o algoritmo. O pior caso ocorre quando a entrada é a mais difícil possível para o algoritmo.
Normalmente, nos preocupamos mais em analisar o algoritmo no pior caso, uma vez que, desta forma, conseguimos mensurar o quão bom ou ruim, é nosso algoritmo. E, sabendo sua eficiência no pior caso, caso ela seja boa, imagine então no melhor caso?
Operações elementares
O tempo de execução de um algoritmo é proporcional ao número de operações elementares que ele executa. Uma operação elementar é uma operação simples que o computador pode executar rapidamente.
Por exemplo, uma operação elementar pode ser uma operação aritmética, como uma soma ou uma subtração. Ou também pode ser uma comparação ou o acesso a um elemento de um array.
Não é preciso contar todas as operações. Basta focar em uma operação de modo que o consumo de tempo do algoritmo seja proporcional ao número de vezes que ela é executada. Por exemplo, ao ordenar um array, a comparação entre elementos é crucial. Por outro lado, para resolver uma equação quadrática, todas as operações aritméticas com ‘a’, ‘b’ e ‘c’ são importantes.
Que tal um exemplo?
Imagine que você escreveu um algoritmo para encontrar o maior e o menor elemento de uma lista de números.
static void findMaxMin(int[] array)
{
int max = array[0]; // 1
int min = array[0]; // 1
for (int i = 1; i < array.Length; i++) // 1 + 2(n-1) + 1
{
if (array[i] > max) // n - 1
max = array[i]; // 1
if (array[i] < min) // n - 1
min = array[i]; // 1
}
Console.WriteLine($"Max: {max}");
Console.WriteLine($"Min: {min}");
}Neste algoritmo, vamos considerar como operação crucial a comparação do elemento atual com o valor máximo e mínimo. Ao lado de cada linha, coloquei a quantidade de operações elementares realizadas.
Podemos observar que independente do tamanho de n, para esse algoritmo, a comparação sempre ocorre. Como começamos um índice à frente no nosso array, então, nossas operações elementares acontecem ( n – 1 ) vezes, como temos duas comparações, então, a complexidade de tempo do nosso algoritmo, no melhor e no pior caso, equivale a: T(n) = 2( n – 1 ).
Como você melhoraria esse algoritmo?
Colocando um else, conseguimos melhorar a complexidade deste algoritmo, você consegue imaginar o por que?
static void findMaxMin(int[] array)
{
...
for (int i = 1; i < array.Length; i++)
{
if (array[i] > max)
max = array[i];
else if (array[i] < min)
min = array[i];
}
...
}Neste caso, precisamos mudar nossa análise, pois, no melhor e no pior caso, nossa complexidade não será mais a mesma! No melhor caso, o nosso array estará em ordem crescente, desta forma, o maior elemento sempre será o elemento contido em array[i], desta forma, não executaremos nenhuma vez nosso else, ficando com uma complexidade igual a: T(n) = n – 1.
Já no pior caso, teríamos um array em ordem decrescente, desta forma, executaremos sempre a cláusula if, e sempre a cláusula else, retornando a complexidade inicial de T(n) = 2( n – 1).
Simples, mas assustador…
Por fim, como prometido, um algoritmo simples, mas que, dado sua entrada (quantidade de discos), pode ter um tempo de processamento monstruoso dado sua eficiência, é o algoritmo da Torre de Hanói na sua versão recursiva
Por hoje é só pessoal! Essa foi apenas uma introdução ao assunto, algoritmos mais complexos, que possuem recursividade ou laços internos condicionais aumentam drasticamente a dificuldade de realizarmos as nossas análises. Deixei abaixo algumas referências para maior aprofundamento no assunto.
referencias:
Aulas de Análise de Algoritmos – USP
Aula 02: Introdução a Projeto e Análise de Algoritmos – IFSP
Como resolver o problema da Torre de Hanói – um guia ilustrativo do algoritmo
Seja o primeiro a comentar