Tema 1 - Complexidade de Algoritmos

Prévia do material em texto

Soler 
 A avaliação de desempenho de um algoritmo 
quanto executado por um computador pode 
ser feita a posteriori ou a priori. 
◦ A posteriori: mede o tempo de execução 
propriamente dito. 
 Arquitetura 
 Linguagem 
 Código 
◦ Benchmarks 
◦ A priori: feita sem sua execução. 
 Considera itens de entrada 
 Número de instruções executadas 
 O aspecto importante da entrada é seu 
“tamanho”, que pode ser dado como 
número de valores num vetor, o número de 
registros num arquivo, etc. 
◦ O tempo de execução de um algoritmo pode ser 
dado como uma função T(n) do tamanho n da sua 
entrada. 
 Por exemplo, um programa pode ter tempo 
de execução T(n) = n. 
 A unidade de T(n) é em principio instrução 
executada. 
 Uma instrução neste contexto é uma 
seqüência de operações cujo tempo de 
execução pode ser considerado constante 
(de certa forma, cada “passo” do algoritmo). 
 Por exemplo, o algoritmo a abaixo: 
 
 public void somavetor (int v[n]) { 
int k=0; 
for (int i=0; i<v.length; i++) 
 k = k + v[i]; 
 } 
 
 Sendo v a entrada, de tamanho n, pode-se 
ver facilmente que a soma k+v[i] será 
efetuada n vezes. 
 
 Conseqüentemente, T(n) = n, incluindo o 
passo de inicialização. O tempo de 
execução (em instruções) variará conforme 
variar n, numa proporção linear. 
 
 No entanto o tempo de execução também 
irá variar de acordo com outros fatores. 
public int localiza (int v[n], int x){ 
 
for (int i=0; i<v.length; i++){ 
 if (x==v[i]) 
 return i; 
} 
return -1; 
} 
 
 T(n) = n + 1 
 O teste pode ser executado apenas uma 
vez, se o valor procurado estiver no 
primeiro elemento do vetor. 
 
 É executado no máximo n vezes. 
 
 Pode-se cogitar, então, de tempos 
mínimos, médios e máximos. 
 Acontece que, em geral: 
◦ tempos mínimos são de pouca utilidade 
◦ tempos médios são difíceis de calcular 
(dependem de se conhecer a probabilidade de 
ocorrência das diferentes entradas para o 
algoritmo). 
 
 Considera-se assim T(n) como uma medida 
assintótica máxima, ou seja, uma medida 
do pior caso de desempenho, que ocorre 
com a entrada mais desfavorável possível. 
public int localiza (int v[n], int x){ 
for (int i=0; i<v.length; i++){ 
 if (x==v[i]) 
 return i; 
} 
return -1; 
} 
 No caso anterior, T(n) = n + 1, incluindo o 
passo de retorno, que sempre acontece 
uma vez. 
 
 A avaliação analítica de uma algoritmo pode 
ser feita com vistas a se obter uma 
estimativa do esforço de computação. 
 
 Não em termos de unidade de tempo 
propriamente, mais em termos de uma taxa 
de crescimento do tempo de execução em 
função do “tamanho do problema”, i.e., do 
tamanho da entrada. 
 
◦ Ex: algoritmos de ordenação 
 Pode se considerar o comportamento de dois 
algoritmos, A1 e A2, que realizam a mesma tarefa 
em tempos TA1 e TA2, para uma entrada de 
tamanho n. observemos os tempos de execução 
para diferentes tamanhos da entrada: 
 Conclusão: ao se multiplicar o tamanho da entrada 
por k, o tempo de A1 cresceu segundo k e o de A2 
segundo k². 
 
 Ou seja, a taxa de crescimento do tempo de 
execução de A1 é proporcional a n, e a de A2, 
proporcional a n². 
 Essa taxa de crescimento proporcional é chamada 
complexidade do algoritmo. 
 
 Ela permite uma classificação dos algoritmos 
segundo sua categoria de complexidade e permite 
também comparar qualitativamente algoritmos 
diferentes que realizam a mesma tarefa. 
 
 Pode ser considerada em termos de tempo de 
execução (complexidade de tempo) ou termos de 
espaço de memória utilizado (complexidade de 
espaço). 
 Como já se discutiu para o tempo de execução, 
pode-se ter complexidade de melhor, médio e pior 
caso. 
 
 Em nosso estudo, a necessidade de espaço em 
memória será considerada constante e o termo 
complexidade designará complexidade de tempo 
de pior caso. 
 A expressão da complexidade de um algoritmo 
busca refletir suas condições intrínsecas, 
abstraindo aspectos ligados aos ambientes 
específicos de execução. 
 
 Assim, não são consideradas constantes de soma 
ou multiplicação. 
 
 Uma expressão como kn + c deve ser simplificada 
para n. 
 Outra condição que se assume é de que se está 
considerando o comportamento assintótico do 
algoritmo, ou seja: a complexidade expressa uma 
tendência a um limite à medida que cresce o 
tamanho do problema. 
 
 Supõe-se que a quantidade de dados a ser 
processada é suficientemente grande para essa 
tendência se evidenciar 
 Isto leva a outra simplificação: ao se ter uma 
expressão polinomial P(n), como os termos de 
menor grau podem ser desprezados (quando n é 
grande) diante do termo de maior grau, este é que 
será adotado como aproximação. 
 
 Exemplo: an³ + bn² - cn + d será reduzido a n³. 
 “A Complexidade de um Algoritmo 
consiste na quantidade de “trabalho” 
necessária para a sua execução, expressa 
em função das operações fundamentais, 
as quais variam de acordo com o 
algoritmo, e em função do volume de 
dados.” 
 Existem três escalas de complexidade: 
◦ Melhor Caso 
◦ Caso Médio 
◦ Pior Caso 
 
 Nas três escalas, a função f(N) retorna a 
complexidade de um algoritmo com entrada 
de N elementos 
 Definido pela letra grega Ω (Ômega) 
 
 É o menor tempo de execução em uma entrada 
de tamanho N 
 
 É pouco usado, por ter aplicação em poucos 
casos. 
 
 Ex: Se tivermos uma lista de N números e quisermos encontrar 
algum deles assume-se que a complexidade no melhor caso é 
f(N) = Ω (1), pois assume-se que o número estaria logo na 
cabeça da lista. 
 
 
◦ Definido pela letra grega θ (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. 
◦ No exemplo anterior: 
 A complexidade média é P(1) + P(2) + ... + P(N) 
 Para calcular a complexidade média, basta conhecer as 
probabilidades de Pi; 
 Pi = 1/N, 1 <= i <= N 
 Isso resulta em P(1/N) + P(2/N) + ... + P(N/N) 
 Que resulta em 1/N(1+2+...+N) 
 Que resulta em 1 N(N+1) 
 N 2 
 Que resulta em f(N) = θ (N+1) 
 2 
 
Que Complicação!!! 
 Será o caso utilizado durante as aulas e é 
representado pela letra grega 
 
 O (O maiúsculo  ômicron maiúscula). 
 
 É o método mais fácil de se obter. Baseia-
se no maior tempo de execução sobre 
todas as entradas de tamanho N 
 
 Ex: Se tivermos uma lista de N números e quisermos 
encontrar algum deles, assume-se que a complexidade 
no pior caso é O (N), pois assume-se que o número 
estaria, no pior caso, no final da lista. 
 Exemplo: Busca seqüencial de um dado 
elemento em um vetor armazenando n 
elementos de forma aleatória. 
◦ Pior caso? 
◦ Melhor caso? 
◦ Caso médio? Supondo a distribuição uniforme e 
que o dado buscado está dentro do vetor. 
◦ Como muda o caso médio se o dado em geral 
não está presente? 
 Como exemplo, considere o número de 
operações de cada um dos dois algoritmos que 
resolvem o mesmo problema, como função de 
n. 
◦ Algoritmo 1: f1(n) = 2n² + 5n operações 
◦ Algoritmo 2: f2(n) = 500n + 4000 operações 
 
 Dependendo do valor de n, o Algoritmo 1 pode 
requerer mais ou menos operações que o 
Algoritmo 2. 
 (Compare as funções para n=10 e n=1000) 
◦ Algoritmo 1: f1(n) = 2n² + 5n operações 
◦ Algoritmo 2: f2(n) = 500n + 4000 operações 
 
 Um caso de particular interesse é quando n 
tem valor muito grande (n  ∞), 
denominado comportamento assintótico. 
 Os termos inferiores e as constantes 
multiplicativas contribuem pouco na 
comparação e podem ser descartados. 
◦ Algoritmo 1: f1(n) = 2n² + 5n operações 
◦ Algoritmo 2: f2(n) = 500n + 4000 operações 
 
 O importante é observar que f1(n) cresce 
com n² ao passo que f2(n) cresce com n. 
 Um crescimento quadrático é considerado 
pior que um crescimento linear. 
 Vamos preferir sendo assim o Algoritmo 2 
ao Algoritmo 1. Existem algoritmos com complexidade 
diversas. 
 
 Mas como saber qual é a complexidade de 
um determinado algoritmo implementado? 
 
 Para resolver esse problema, dividiu-se os 
algoritmos em “Classes de Problemas”, de 
acordo com o parâmetro que afeta o 
algoritmo de forma mais significativa 
1. Complexidade Constante 
 
2. Complexidade Linear 
 
3. Complexidade Logarítmica 
 
4. Complexidade n log n 
 
5. Complexidade Quadrática 
 
6. Complexidade Cúbica 
 
7. Complexidade Exponencial 
log n 
n 
n2 
2n 
n 
f 
n log n 
1 
(linear) 
(quadrática) 
(exponencial) 
(logarítmica) 
(constante) 
 São os algoritmos de complexidade O(1) 
 Independe do tamanho N de entradas 
 É o único em que as instruções dos 
algoritmos são executadas num tamanho 
fixo de vezes 
 Ex.: 
public void esvaziarVetor(int meuVetor[ ]){ 
 meuVetor = null; 
} 
 São os algoritmos de complexidade O(N) 
 Uma operação é realizada em cada elemento de 
entrada, ex.: pesquisa de elementos em uma lista 
public int imprimeVetor(int lista[ ]){ 
 for(int i=0; i < lista.length; i++){ 
 System.out.println(“valor: ”+lista[i]); 
 } 
} 
public int posicaoElemento(int lista[ ], int elemento){ 
 int posicao = -1; 
 boolean achou = false; 
 int tamanhoLista = lista.length; 
 int i = 0; 
 while(i < tamanhoLista && !achou){ 
 if (lista[i] == elemento){ 
 achou = true; 
 posicao = i; 
 } 
 i++; 
 } 
 return posicao; 
} 
O(N) 
O(1) 
O(1) 
O(1) 
O(1) 
O(1) 
O(1) 
O(1) 
f(N) = O(9 * O(1) + O(N)  O(O(1) + O(N))  O(N) 
 São os algoritmos de complexidade O(log n) 
 
 Ocorre tipicamente em algoritmos que 
dividem o problema em problemas menores 
 
 Ex.: O algoritmo de Busca Binária (estudados 
futuramente) 
 Como o próprio nome diz, são algoritmos 
que têm complexidade O(n log n) 
 
 Ocorre tipicamente em algoritmos que 
dividem o problema em problemas menores, 
porém juntando posteriormente a solução 
dos problemas menores 
A maioria dos algoritmos de ordenação externa são 
de complexidade logarítmica ou n log n 
 São os algoritmos de complexidade O(N²) 
 Itens são processados aos pares, geralmente 
com um loop dentro do outro 
public void somaMatriz (int matrizA[ ][ ], int matrizB[ ][ ]){ 
 for (int i=0; i < matrizA.length; i++){ 
 for (int j=0; j < matrizB.length; j++){ 
 matrizSoma[i,j] = matrizA[i][j] + matrizB[i][j]; 
 } 
 } 
} 
 São os algoritmos de complexidade O(N³) 
 Itens são processados três a três, geralmente 
com um loop dentro do outros dois. 
public void soma(int matrizSoma[ ][ ], int vetorB[ ]){ 
 int n = matrizSoma.length; 
 for (int i=0; i < n; i++){ 
 for (int j=0; j < n; j++){ 
 for (int k = 0; k < n; k++) 
 matrizSoma[i][j] = matrizSoma[i][j] + vetorB[k]; 
 } 
 } 
 } 
 São os algoritmos de complexidade O(2N) 
 
 Utilização de “Força Bruta” para resolvê-los 
(abordagem simples para resolver um 
determinado problema, geralmente baseada 
diretamente no enunciado do problema e nas 
definições dos conceitos envolvidos) 
 
 Geralmente não são úteis sob o ponto de 
vista prático 
 Exemplo de função exponencial: Fibonacci recursivo 
 Experimente rodar este algoritmo para: 
 n = 100. 
 
 A complexidade é O(2n). 
 
 Mesmo se uma operação levasse um 
picosegundo, 2100 operações levariam: 
 
 3x1013 anos = 30.000.000.000.000 anos!! 
 Faça a função de complexidade para 
os exercícios de vetores previamente 
passados em sala. 
 GOODRICH, Michael T; TAMASSIA, Robert. Estruturas de 
dados e algoritmos em JAVA. Porto Alegre: Bookman, 2002. 
 
 SZWARCFITER, Jayme Luiz; MARKENZON, Lílian. Estruturas de 
Dados e seus Algoritmos. Rio de Janeiro: LTC, 1994. 
 
 TOSCANI, Laira Vieira; VELOSO, Paulo A. S. Complexidade de 
Algoritmos. Porto Alegre: Sagra Luzzato, 2001. 
 
 TENENBAUM, Aaron M.; LANGSAM, Y. AUGENSTEIN, M. J. 
Estruturas de Dados Usando C. São Paulo: Makron Books, 
1995. 
 
 DEITEL, Harvey M.; DEITEL, Paul J. Java : como programar. 4. 
ed. Porto Alegre: Bookman, 2003.