Análise e Técnicas de Algoritmos

Análise de Algoritmos

Análise de Algoritmos

Introdução

• Dois aspectos importantes:
  • Um problema pode, geralmente, ser resolvido por diferentes algoritmos.
  • A existência de um algoritmo para resolver um determinado problema não implica, necessariamente, que este problema possa ser realmente resolvido na prática. Há restrições de tempo e espaço.
• A análise de algoritmos pode ser definida como o estudo da estimativa de tempo de execução de algoritmos.
• O tempo de execução de um programa é uma grandeza física que é determinado pelos seguintes aspectos:
  • Tempo que a máquina leva para executar uma instrução ou paaso de um programa.
  • A natureza do algoritmo, ou seja, de quantos passos são necessários para se resolver o problema para um dado.
  • O tamanho do conjunto de dados que constitui o problema.
• É necessário ter uma forma de criar medidas de comparação entre algoritmos que resolvem um mesmo problema. Desta forma, é possível determinar:
  • A viabilidade de um algoritmo.
  • Qual é o melhor algoritmo para a solução de um problema.
• O interessante é ter uma comparação relativa entre algoritmos.
  • Assumir que a execução de todo e qualquer passo de um algoritmo leva uma um tempo fixo e igual a uma unidade de tempo.
  • O tempo de execução de um computador particular não é interessante.

Análise Assintótica

• Para analisar estruturas de dados e algoritmos, utilizamos uma estrutura matemática que possui terminologia própria. Antes de efetuarmos a análise dos algoritmos apresentados na seção anterior, vamos introduzir algumas definições:

Big Oh

• $T(n) = O(f(n))$ se existem constantes $c$ e $n_0$ tais que $T(n) \leq c f(n)$ quando $n \geq n_0$.
• Esta Definição indica que eventualmente existe algum ponto $n_0$ onde $c f(n)$ é sempre pelo menos tão grande quanto $T(n)$.

Big Omega

• $T(n) = \Omega(g(n))$ se existem constantes $c$ e $n_0$ tais que $T(n) \geq c g(n)$ quando $n \geq n_0$.
• Esta definição indica que a taxa de crescimento de $T(n)$ é maior ou igual a taxa de crescimento de $g(n)$.

Big Theta

• $T(n) = \Theta(h(n))$ se e somente se $T(n) = O(h(n))$ e $T(n) = \Omega(h(n))$.
• Esta definição indica que a taxa de crescimento de $T(n)$ é igual a taxa de crescimento de $h(n)$.

• A análise assintótica é baseada nessas definições e estabelece uma ordem relativa entre funções. Na verdade, o que é observado e comparado são as taxas relativas de crescimento das funções.

• Quando dizemos que $T(n) = O(f(n))$, asseguramos que $f(n)$ é um limite superior sobre $T(n)$. Da mesma forma, para $f(n) = \Omega(T(n))$, dizemos que $T(n)$ é um limite inferior sobre $f(n)$.

• Como exemplo, vamos considerarduas funções: $f(n) = n$ e $g(n) = n^2$. Para $0 \leq n \leq 1$, $f(n) \geq g(n)$. Quando $n > 1$, $g(n)$ é sempre maior do que $f(n)$. Logo, dizemos que $f(n) = O(g(n))$.

Taxas de Crescimento Mais Comuns

Função	Nome
$1$	constante
$log$ $n$	logaritmico
$log^2$ $n$	log-quadrático
$n$	linear
$n$ $log$ $n$	$n$ $log$ $n$
$n^2$	quadrático
$n^3$	cúbico
$2^n$	exponencial

Complexidade de Tempo

• Os algoritmos podem ser avaliados por uma variadade de critérios como, por exemplo, a quantidade de dados de entrada (complexidade de tamanho) ou o tempo necessário para o algoritmo, expresso como uma função do tamanho do problema (complexidade de tempo).
• Para determinar o tempo de execução de um determinado algoritmo, temos que descobrir a forma geral da curva que caracteriza seu tempo de execução em função do tamanho do problema.

• Para simplificarmos a análise de complexidade de tempo, nós adotamos a não existência de unidades de tempo particulares. Por outro lado, não consideramos também os termos de ordem inferior, isto é, nós computamos a complexidade de tempo baseado no Big-Oh.

• A complexidade de tempo para diferentes algoritmos pode indicar diferentes classes de complexidade. Cada classe é caracterizada por uma família diferente de curva.

• Informalmente, para se determinar a ordem de complexidade de uma determinada função $f(n)$, podemos efetuar as seguintes etapas:
  1. separar $f(n)$ em duas partes: termo dominante e termos de ordem inferior.
  2. ignorar os termos de ordem inferior.
  3. ignorar as constantes de proporcionalidade.

• Lembrar que:
  • $O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2^n)$.

• Para ilustrar, vamos considerar que o tempo de execução de um determinado algoritmo é caracterizado pela função $f(n) = a n^2 + b n + c$. Qual seria a complexidade deste algoritmo?
  • O termo $a n^2$ é dominante (maior ordem) sobre os demais. Os termos de ordem inferior podem ser desprezados.
  • Uma vez que o objetivo é descobrir a família da curva que caracteriza o tempo de execução do algoritmo, a constante de proporcionalidade no termo $a n^2$ pode ser desprezada.
  • Conclui-se que $f(n) = O(n^2)$, isto é, a complexidade do algoritmo é de ordem quadrática.

Análise de Algoritmos Simples

• Para analisar algoritmos através da análise assintótica é necessário definir um modelo de computação.
• Em nosso modelo consideramos que as instruções são executadas sequencialmente e que o conjunto de instruções simples (adição, comparação, atribuição, etc) tomam exatamente uma unidade de tempo para serem executadas.

• Como o objetivo é determinar a forma da curva que caracteriza o algoritmo, vamos definir algumas regras que podem ser utilizadas:
  • Laços: O tempo de execução de um laço é no máximo o tempo de execução das instruções dentro do laço (incluindo os testes) vezes o número de iterações.
  • Aninhamento de Laços: Analisar os mais internos. O tempo total de execução de uma instrução dentro de um grupo de laços aninhados é o tempo de execução da instrução multiplicado pelo produto dos tamanhos de todos os laços.
  • Instruções Consecutivas: Apenas efetuar a soma.
  • If/Else: o tempo de execução de uma instrução if/else nunca é maior do que o tempo de execução do teste mais o maior dos tempos de execução de S1 e S2. S1 e S2 representam as instruções do then e else, respectivamente.
  • Chamada de Funções: A análise é feita como no caso de laços aninhados. Para calcular a complexidade de um programa com várias funções, determina-se primeiro a complexidade de cada uma das funções. Desta forma, na análise, cada uma das funções é vista como uma instrução com a complexidade que foi calculada.
  • Recursão: É a parte mais difícil da análise de complexidade. Em muitos casos, pode-se fazer a linearização através da substituição da chamada recursiva por alguns laços aninhados, por exemplo. Entretanto, existem algoritmos que não possibilitam a linearização. Nestes caso, é necessário usar uma relação de recorrência que tem que ser resolvida.
• Tipos de análise:
  • Pior caso: indica o maior tempo obtido, levando em consideração todas as entradas possíveis.
  • Melhor caso: indica o menor tempo obtido, levando em consideração todas as entradas possíveis.
  • Média: indica o tempo médio obtido, considerando todas as entradas possíveis.

Exemplo: Algoritmo para calcular $x^n$

• Linhas (1), (2) e (6) são executadas uma única vez (3 unidades de tempo).
• O laço das linhas (3) a (5) é executado $n$ vezes (2.n unidades de tempo).
• O tempo de execução é $2.n + 3$ que é $O(n)$.

Com relação a análise assintótica de algoritmos temos que fazer algumas considerações:

• A complexidade de tempo de um algoritmo é apenas um fato sobre ele. Um algoritmo assintoticamente mais barato pode ser muito mais difícil de ser implementado do que um outro algoritmo com complexidade de tempo maior.
• A superioridade assintotica só é evidente quando os problemas são suficientemente grandes.

Funções de Complexidade	Tamanho da Entrada $n$
	10	20	30	40	50	60
$n$	.00001 seg	.00002 seg	.00003 seg	.00004 seg	.00005 seg	.00006 seg
$n^2$	.0001 seg	.0004 seg	.0009 seg	.0016 seg	.0025 seg	.0036 seg
$n^3$	.001 seg	.008 seg	.027 seg	.064 seg	.125 seg	.216 seg
$n^5$	.1 seg	3.2 seg	24.3 seg	1.7 min	5.2 min	13.0 min
$2^n$	.001 seg	1.0 seg	17.9 min	12.7 dias	35.7 anos	366 sec.
$3^n$	.059 seg	58 min	6.5 anos	3855 sec.	$2x10^8$ sec.	$1.3x10^13$ sec.

Algumas Dicas de Análise

• Identificar a operação fundamental usada no algoritmo. A análise dessa operação fundamental identifica o tempo de execução. Isso pode evitar a análise linha-por-linha do algoritmo.
• Quando um algoritmo, em uma passada de uma iteração, divide o conjunto de dados de entrada em uma ou mais partes, tomado cada uma dessas partes e processando separada e recursivamente, e depois juntando os resultados, este algoritmo é possivelmente $nlog(n)$.
• Um algoritmo é $log(n)$ se ele leva tempo constante $O(1)$ para dividir o tamanho do problema, geralmente pela metade. Por exemplo, a pesquisa binária.
• Se o algoritmo leva tempo constante para reduzir o tamanho do problema em um tamanho constante, ele será $O(n)$.
• Algoritmos combinatoriais são exponenciais. Por exemplo, o problema do caixeiro viajante.