Aula2-Complexidade de Algoritmos e Problemas

Departamento de Ciências e Tecnologias da Informação Filipe Santos

Algoritmos e Complexidade 1

Departamento de Ciências e Tecnologias da Informação

1

ALGORITMOS E COMPLEXIDADE

COMPLEXIDADE DE ALGORITMOS E PROBLEMAS



Plano

Eficiência de algoritmos. Eficiência no melhor caso, pior caso e em média. Ordem de complexidade. Melhoramentos de pequena e grande magnitude na eficiência de algoritmos. Exemplos de diferentes algoritmos com diferentes eficiências para o mesmo problema. Complexidade de um problema. Problemas fechados e abertos.

Algoritmos: Insert sort; Pesquisa Linear; Pesquisa Binária; Bubblesort; Barricada dos tigres adormecidos.



Eficiência de algoritmosQue recursos computacionais são necessários para executar um algoritmo?

C tempo de execução Complexidade TemporalC espaço de memória Complexidade Espacial

Cespaço e tempo dependem da dimensão dos dados. Podemos portanto representar a eficiência por funções!

S(n) memória utilizada pelo algoritmo em função do tamanho n do inputT(n) tempo de execução do algoritmo em função do tamanho n do input

n - dimensão dos dados

espaço

S(n)



Eficiência de algoritmos

L Na prática é muito difícil calcular com rigor o tempo de execução de um algoritmo!

☺ Identificar no algoritmo as operações elementares e determinar o número de vezes que são executadas. O tempo real de execução de cada operação elementar será uma constante multiplicativa!

A Independentemente do computador!

$ Dados vários algoritmos para solucionar um mesmo problema, devemos escolher aquele que nos permite resolver o problema mais rapidamente e utilizando o menor espaço possível para representar os dados do problema! Mas …



Eficiência de algoritmos

C um algoritmo pode ser mais eficiente que outro para inputs de “pequena”dimensão e deixar de o ser para inputs de “grande” dimensão. E.g. insertsort vs treesort

C um algoritmo pode ser mais eficiente que outro em tempo e não o ser em espaço. E.g. bublesort vs treesort

C Mais ainda, diferentes amostras com a mesma dimensão podem ser processadas em tempos diferentes, podendo-se falar de eficiência temporal mínima (melhor caso), máxima (pior caso) e média.


tempo

T1(n)

T2(n)

k

S1(n)

S2(n)


espaço

m



Eficiência no melhor caso, pior caso e em médiaExemplo: Dado um array de n∈N empregados, ordenar os empregados por nome.

Empregado[] insertsort(Empregado[] empregados, int n){ for(int i = 2; i < n+1; i = i +1){

int pos = i; empregados[0] = empregados[i];while( empregados[pos-1].nome “>”x.nome){

empregados[pos] = empregados[pos-1];pos = pos-1

}empregados[pos] = empregados[0];

} return empregados;}Tmin(n) = i=2..n 3 = 3(n – 1)(ocorre quando o array a ordenar já está ordenada)Tmax(n) = i=2..n (2i+1) = n2 + 2n – 3(ocorre quando o array a ordenar está pela ordem inversa)Tmed(n) = i=2..n (2i+1) = (n2 + 5n – 6)/2, para amostras equiprováveis.



Ordem de ComplexidadeC Normalmente a análise de algoritmos é simplificada se nos concentrarmos na sua eficiência assimptótica, i.e. análise da taxa de crescimento do pior caso.

Notação O: Sejam f: N R e g: N R funções. f(n) = O(g(n)) sse∃c∈R+ ∃n0∈N : |f(n)| c|g(n)|, ∀n n0

Exemplos:(n+1)/2 = O(n)2n3+2n -7 = O(n3)(n2+5)(n-3) = O(n3)ln n = O(log2 n)25 = O(n0) = O(1)

n0

f(n)

f(n) = O(g(n))

c g(n)

n



Classes de Complexidade AlgorítmicaClasses de Complexidade Algorítmica

O(1) Complexidade ConstanteO(log n) Complexidade LogarítmicaO(n) Complexidade LinearO(n log n) Complexidade Log-LinearO(n2) Complexidade QuadráticaO(n3) Complexidade CúbicaO(nk) Complexidade PolinomialO(an) Complexidade ExponencialO(n!) Complexidade Factorial

2n

n2

n

log n



Classes de Complexidade Algorítmica

Com 210 103 M número grande inimaginável

1 dia 24 X 60 X 60 = 86400 9 X 1010 microsegundos1 ano = 365 X 24 X 60 X 60 3 X 107 segundos 3 X 1013 microsegundos1 século 3 X 109 segundos 3 X 1015 microsegundos1 milénio 3 X 1010 segundos 3 X 1016 microsegundosBig Bang 15 X 109 anos 45 X 1016 segundos 45 X 1022 microsegundos

CAlgoritmos de complexidade constante e logaritmica são os mais eficientes

C Algoritmos de complexidade exponencial geram tempos de execução incomportáveis

10 50 100 1000 104 105 106

log2 n 3 5 6 9 13 16 19

n 10 50 100 1000 104 105 106

n log2 n 30 282 664 9965 105 106 107

n2 100 2500 104 106 108 1010 1012

n3 1000 125000 106 109 1012 1015 1018

2n 1000 1016 1030 10300 103000 1030000 10300000

n! 106 1065 10160 M M M M

nn 1010 1085 10200 M M M M



Melhoramentos de pequena e grande magnitudeC Pequenos melhoramentos não mudam a classe de complexidade!

boolean pesquisalinear(Empregado[] empregados, int n, String nome){ int i = 0; boolean sim = false;while(i < n){

if( empregados[i].nome “==” nome) sim = true; i = i +1;} return sim;

}

C O(n)

boolean pesquisalinear(Empregado[] empregados, int n, String nome){ int i = 0; boolean sim = false;while(!sim && i < n){

if( empregados[i].nome “==” nome) sim = true; i = i +1;} return sim;

}

C O(n)



Melhoramentos de pequena e grande magnitude

boolean pesquisalinear(Empregado[] empregados, int n, String nome){ int i = 0;empregados[n] = new Empregado(nome, 0.0);while(empregados[i].nome “==” nome) i = i +1;return i != n;

}

C O(n)

C Mudar a classe de complexidade exige uma reformulação mais profunda do algoritmo!



Melhoramentos de pequena e grande magnitudeProblema: Dado um array de n∈N empregados ordenados por nome e um nome (input), saber se existe um empregado com esse nome (output)

boolean pesquisabinária(Empregado[] empregados, int n, String nome){ return pesquisa(empregados, 0, n-1, nome);

}

boolean pesquisa (Empregado[] empregados, int a, int b, String nome){int meio = (a+b)/2;if( empregados[meio].nome “==” nome) return true;else{

if( nome “<” empregados[meio].nome){if(a<meio) return pesquisa(empregados, a, meio-1, nome);

else return false;} else{ if (meio<b) return pesquisa(empregados, meio+1, b, nome);

else return false;}

}}



Melhoramentos de pequena e grande magnitudeanálise de complexidade:Considere-se um array com n = 24-1 = 15 elementos e a seguinte árvore. Cada nó da árvore representa uma operação de comparação. Cada ramo a partir do nó raiz até outro nó da árvore representa uma execução possível do algoritmo.

Melhor caso: 1 operação (não passa do 1º nível da árvore)Pior caso: 4 comparações (tantas comparações quantos os níveis da árvore)

C Uma árvore binária completa com k níveis tem n=2k-1 elementos! k log2nC O(log n)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15



Eficiência de algoritmos recursivosProblema Torres de Hannoi

void Hanoi(int n, char posteInicial, char posteFinal, char posteAuxiliar){if(n == 1) System.out.println(posteInicial + “ ” + posteFinal);else{

Hanoi(n-1, posteInicial, posteAuxiliar, posteFinal);System.out.println(posteInicial + “ ” + posteFinal); Hanoi(n-1, posteAuxiliar, posteFinal, posteInicial);

}}

Neste caso é fácil obter a seguinte fórmula recorrente:

1 , n=1T(n) =

2T(n-1) +1, n>1

Que explicitando dá: T(n) = 2n-1 , n 1

C O(2n)



Complexidade de um problemaC A complexidade de um problema é a complexidade do melhor algoritmo que o resolve.

C O melhor algoritmo que resolve um problema pode não ser conhecido.

Problema “Pesquisa em listas ordenadas”: Dado um array de n∈N empregados ordenados por nome e um nome (input), saber se existe um empregado com esse nome (output)

pesquisa linear O(n)pesquisa binária O(log n)será que podemos fazer melhor?

Limites superior e inferior de um problema

C A complexidade de um problema pode não ser conhecida, mas pode ser delimitada superiormente e inferiormente

C O limite superior indica que não é necessário gastar mais para resolver o problema

C O limite inferior indica que não se pode gastar menos para resolver o problema



Complexidade de um problema

C O limite superior é estabelecido pelo melhor algoritmo, entre os algoritmos conhecidos. A descoberta de um novo algoritmo mais eficiente faz descer o limite superior.

C O limite inferior é estabelecido por técnicas de prova que comprovem que não existem algoritmos mais eficientes. Qualquer algoritmo, conhecido ou desconhecido, deverá ser mais complexo do que esse limite.



Complexidade de um problemaExemplo de prova de que algoritmos de pesquisa em listas têm limite inferior log n

C O pior caso está associado aos caminhos mais longos na árvore a partir da raizC Os algoritmos melhores são portanto aqueles que são representados por árvores de profundidade menor.C Árvores com n folhas com menos níveis são as árvores binárias completas, que têm log2n níveis. C limite inferior O(log n)



Problemas fechados e abertosC Um problema diz-se fechado quando o seu limite superior e inferior coincidem.

C Um problema diz-se aberto quando o seu limite superior e inferior não coincidem.

Nesse caso:1. existe um algoritmo melhor para o problema e ainda não o descobrimos; ou 2. não conseguimos provar que não existem algoritmos melhor; ou 3. 1 e 2.

Exemplos de problemas fechados

pesquisa em listas ordenadas O(log n)pesquisa em listas não ordenadas O(n) (soma salários, …)ordenação O(n log n) (barricada dos tigres)torres de Hanoi O(2n)

Exemplos de problemas abertos

rodovia mais barata limite superior O(n log n)limite inferior O(n)…



Um exemplo adicional para terminarProblema “barricada dos tigres/ convex hull”: Dados n∈N tigres posicionados num campo (input), qual o menor polígono que os cerca (output)

$ Um segmento faz parte da cerca sse todos os restantes pontos estão no mesmo lado desse segmento.

Algoritmo1: Testar para cada um dos n2 segmentos se os restantes n-2 pontos estão do mesmo lado.

C O(n3)



Um exemplo adicional para terminar

Algoritmo2:

1. Procurar o ponto mais baixo; C O(n)2. Ordenar os restantes pontos por ordem crescente de ângulos; C O(n log n)3. Considerar que o segmento P1 P2 faz parte da cerca; C O(1)4. Para cada um dos restantes pontos PI C O(n) *

4.1 Adicionar PI à cerca4.2 Verificar todos os pontos PJ anteriores da cerca (por ordem inversa) e eliminá-los caso

P1 e PI estejam em lados diferentes do segmento com os pontos PJ e PJ-1. Parar este processo quando um PJ não for eliminado.

* $ à medida que são eliminados não voltam a ser comparados

C O(n log n)




P1

P2

P3

P4

P5

P6

P7

P1

P2

P3

P4

P5

P6

P7

P1

P2

P3

P4

P5

P6

P7

…




…

P1

P2

P3

P4

P5

P6

P7

P1

P2

P3

P4

P5

P6

P7

P1

P2

P3

P4

P5

P6

P7

…

Documents

Aula2-Complexidade de Algoritmos e Problemas