Complexidade Algoritmica e Recursividade

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

1
Complexidade de Algoritmos
1
2
Complexidade de Algoritmos
Uma característica importante de qualquer algoritmo é seu tempo de execução
é possível determiná-lo através de métodos empíricos, considerando-se entradas diversas
é também possível obter este tempo a partir de métodos analíticos
A análise dos algoritmos de ordenação e a busca encontra-se entre as mais conhecidas e utilizadas nos sistemas de computação
2
242
3
Complexidade de Algoritmos
Devido à relação entre ordenação e busca, deve-se verificar, para qualquer aplicação, se o conjunto de dados deve ser ordenado ou não
Ocasionalmente dá menos trabalho procurar determinado elemento em um conjunto de dados do que ordená-los primeiro e depois obter o elemento desejado
Por outro lado, se a busca for freqüente, talvez seja mais eficiente ordenar o conjunto antes.
Decisão deve ser tomada com base em circunstância individuais
Não existe um método de ordenação considerado universalmente superior aos outros; será preciso analisar o problema e os resultados desejados.
3
242
4
Complexidade de Algoritmos
Existe uma grande variedade de métodos de ordenação; deve-se dar atenção aos vários aspectos de eficiência, normalmente conflitantes:
Tempo gasto para codificar o programa de ordenação
Tempo de máquina necessário para executar o programa
Espaço necessário para armazenar o programa
Se o conjunto é pequeno, técnicas sofisticadas para reduzir exigências de espaço e tempo de execução em geral são equivalentes aos métodos mais simples ou piores, em termos de eficiência.
4
242
5
Complexidade de Algoritmos
Com freqüência, não se avalia a eficiência de tempo de uma ordenação por unidades de tempo, mas sim pelo número de operações críticas efetuadas:
comparação de chaves
movimentação de elementos
troca de elementos
As operações críticas escolhidas são as que consomem mais tempo
5
243
6
Complexidade de Algoritmos
Métodos empíricos
objetivo: executar o programa e avaliar sua eficiência.
o resultado é a medida de unidades de tempo absoluto ou de número de operações efetuadas.
são necessários diversos testes com grupos variados de elementos
mesmo fazendo-se uma média estatística, a aplicação de uma ordenação em um conjunto particular pode não apresentar resultados que sigam os padrões gerais
6
243
7
Complexidade de Algoritmos
Métodos analíticos
objetivo: determinar uma expressão matemática que traduz o comportamento de tempo de um algoritmo.
o resultado é uma fórmula dando o tempo médio (ou o número de operações) para ordenar um conjunto de tamanho n.
o tempo de execução independente:
do computador utilizado
da linguagem e compiladores empregados 
e das condições locais de processamento
7
243
8
Complexidade de Algoritmos
Métodos analíticos 
Obter uma expressão matemática não é simples, mesmo considerando uma expressão aproximada
Várias simplificações são introduzidas
quantidade de dados a serem manipulados pelo algoritmo é suficientemente grande
quantidade de dados de entrada reduzida não serão considerados
8
244
9
Complexidade de Algoritmos
Exemplo: Inversão de uma seqüência
	
	fim = n/2;
	for (i=0; i<fim; i++)
	{	temp = S[i];
		S[i] = S[n-1-i];
		S[n-1-i] = temp;
	}		
9
252
10
Complexidade de Algoritmos
n = 5  troca S[i] por S[n-1-i]
fim = 2
i = 0  troca S[0] por S[5-1-0] (S[4])
i = 1  troca S[1] por S[5-1-1] (S[3])
	inicial final
M
A
A
R
 I
0
4
1
2
3
A
M
I 
R
 A
0
4
1
2
3
10
253
11
Complexidade de Algoritmos
n = 6  troca S[i] por S[n-1-i]
fim = 3
i = 0  troca S[0] por S[6-1-0] (S[5])
i = 1  troca S[1] por S[6-1-1] (S[4])
i = 2  troca S[2] por S[6-1-2] (S[3])
	inicial final
E
D
S
T
A
0
4
1
2
3
O
S
D 
A
 T
0
4
1
2
3
O
5
E
5
11
254
12
Complexidade de Algoritmos
n = 50  troca S[i] por S[n-1-i]
fim = 25
i = 0  troca S[0] por S[50-1-0] (S[49])
i = 1  troca S[1] por S[50-1-1] (S[48])
i = 2  troca S[2] por S[50-1-2] (S[47])
.........
i = 23  troca S[23] por S[50-1-23] (S[26])
i = 24  troca S[24] por S[50-1-24] (S[25])
12
255
13
Complexidade de Algoritmos
O algoritmo executa exatamente as mesmas operações para seqüências de tamanho n
cada passo corresponde à troca de posição entre dois elementos da seqüência
a execução das três atribuições
o número de passos é igual ao número de vezes que executa o bloco for  n/2, n>1
Função: f(n) = 1 + 3(n)
13
256
14
Notações Ω, θ
Melhor Caso - Ω (Ômega)
É o menor tempo de execução em uma entrada de tamanho N
É pouco usado, por ter aplicação em poucos casos.
Caso Médio - θ (Theta)
Dos três, é o mais difícil de se determinar
Deve-se obter a média dos tempos de execução de todas as entradas de tamanho N, ou baseado em probabilidade de determinada condição ocorrer
14
268
15
Notação O
Pior Caso - O (Grande)
É o maior tempo de execução em uma entrada de tamanho N
É a notação mais usada.
15
268
Independe do tamanho de N (entradas)
É Executado em um número fixo de vezes
Function Inicializa( tp_pilha *pilha) {
	pilha->topo = -1;
}
16
Complexidade Constante - O(1)
Um número de operações será executado para cada N (entradas)
function display(int X) {
 int i = 1;
Int mult;
 while (i<=X) {
 mult = i * 5;
 printf(“%d”, mult); 
 i++;}
 }
17
Complexidade Linear - O(n)
Itens são processados aos pares, geralmente com um loop dentro do outro
function display(int X, int Y) {
 int i, j;
for (i=1; i<=X;i++) 
 for (j=1; j<= Y; j++){
 printf(“%d”, i+j); }
 }
18
Complexidade Quadrática - O(n2)
19
A notação O
Complexidade
desprezar algumas operações
interesse assintótico - termos de menor grau podem ser desprezados: n2 + n será aproximado para n2
6n3 + 4n - 9 será aproximado para n3
A função O atua como um limite superior assintótico da função f:
f = n2 -1 	 		Þ 	f = O(n2)
f = 403 	 		Þ 	f = O(1)
f = 5+2logn +3log2n 	Þ 	f = O(log2n)
f = 5*2n +5*n10 	 	Þ 	f = O(2n)
19
267
20
A notação O
Algoritmo de inversão de seqüência:
o número de passos se mantém o mesmo para o mesmo valor de n
variável independente é n
efetua sempre n/2 passos
complexidade é O(n)
20
271
21
Alguns conceitos
T (n) = O (1) : constante 
T (n) = O (log log n) : super-rápido
T (n) = O (log n) : logarítmico – muito bom 
T (n) = O (n) : linear – toda a entrada é visitada
T (n) = O (n log n) : limite de muitos problemas
T (n) = O (n2) : quadrático 
T (n) = O (nk) : polinomial no tamanho da entrada
T (n) = O (kn), O (n!), O (nn) : exponencial – ruim! 
22
Gráfico comparativo
23
Recursividade
23
24
Recursividade
Um módulo recursivo é aquele que contém uma ou mais chamadas a si mesmo
Programas recursivos:
 são mais concisos e normalmente menores
podem ficar mais lentos por usar muitas posições de memória
principal vantagem: poder utilizar funções recursivas para criar versões mais claras e simples, principalmente buscas e ordenações
24
232
25
Recursividade
Todo processo recursivo consiste de duas partes:
Solução Trivial: é conseguida por definição, ou seja, não é necessário fazer uso de recursividade para obtê-la
Solução Geral: solução genérica que funciona em uma parte menor do problema original, mas que pode ser aplicada integralmente ao problema original
25
232
26
Recursividade
Exemplo: Fatorial
			1, se n=0 (solução trivial)
n! =
			n * (n-1)!, se n>0 (solução geral)
4! = 4 * 3!		recursão
3! = 3 * 2!		recursão
2! = 2 * 1!		recursão
1! = 1 * 0!		não recursão
0! = 1		não recursão
26
232
27
Exemplo - Fatorial
#include <stdio.h>
int fat (int n);
main( ) {
		int n, res;
		scanf("%d", &n);
		res=fat(n);
		printf("Fatorial: %d\n", res);
}
int fat (int n) {
		if (n)	 /* (n != 0) */
			return n * fat(n-1);
		else
			return 1;
}
(1) res
?
?
3
fat
n
(2) res
?
?
?
?
?
0
1
2
3
fat
n
(3) res
?
1
?
?
?
0
1
2
3
fat
n
(4) res
?
1
1
2
6
0
1
2
3
fat
n
(5) res
6
27
232