Click here to load reader

Complexidade de Algoritmos, Notação assintótica, Algoritmos polinomiais e intratáveis

  • View
    621

  • Download
    2

Embed Size (px)

DESCRIPTION

Complexidade de Algoritmos;Notação assintótica; Algoritmos polinomiais e intratáveis

Text of Complexidade de Algoritmos, Notação assintótica, Algoritmos polinomiais e intratáveis

  • 1. Complexidade de Algoritmos:Tempo e espao; Notaoassinttica; Algoritmospolinomiais e intratveisProfessor: Jos Fernando Rodrigues JniorUniversidade de So Paulohttp://www.icmc.usp.br/pessoas/junio

2. Introduo Algoritmos e funes Notao Assinttica Interpretaomatemtica Notao Assinttica Aplicao a algoritmos Notao Assinttica Interpretaoalgortmica Notao Assinttica Limitaes Notao Assinttica Um indicador geral Algoritmos Polinomiais e Exponenciais Concluseshttp://www.icmc.usp.br/pessoas/junio 3. http://www.icmc.usp.br/pessoas/junioIntroduoPorqu o estudo da Complexidade? Escolher entre vrios algoritmos o mais eficiente; Desenvolver algoritmos mais eficientes; Complexidade Computacional - torna possveldeterminar se a definio de determinado algoritmo vivel. 4. Algoritmos e FunesTodo algoritmo define uma funo matemticaf(n)= # de instruesEx.:void Algoritmo1(int n){int contador = 0;for(int i = 0; I < n; I++){http://www.icmc.usp.br/pessoas/juniocontador++;}} n passos para terminar 5. Algoritmos e FunesTodo algoritmo define uma funo matemticaf(n)= # de instruesEx.:void Algoritmo2(int n){int contador = 0;for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){contador++;http://www.icmc.usp.br/pessoas/junio}}} n*n passos para terminar 6. Algoritmos e FunesTodo algoritmo define uma funo matemticaf(n)= # de instruesEx.:void Algoritmo3(int n){int contador = 0;for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){for(int k = 0; k < n; k++){contador++;http://www.icmc.usp.br/pessoas/junio}}}} n*n*n passos para terminar 7. Algoritmos e FunesAlgoritmo1 Algoritmo2 Algoritmo3n = 1 1 1 1n = 10 10 102 103n = 1000 103 106 109n = 106 106 1012 1018f(n) = n f(n) = n2 f(n) = n3http://www.icmc.usp.br/pessoas/junio 8. Algoritmos e FunesQual algoritmo voc escolheria?R.: basta olhar na funo definida por cadaalgoritmoA funo de um algoritmo melhor algoritmo paraum dado problemaFatores: tempo de processamento, memria,acessos a disco, largura de banda, entre outroshttp://www.icmc.usp.br/pessoas/junio 9. Algoritmos e FunesA prtica de se reduzir um algoritmo a uma funomatemtica denomina-seAnlise de complexidade de algoritmoshttp://www.icmc.usp.br/pessoas/junio 10. Algoritmos e FunesMas como se faz a anlise de um algoritmo,matematicamente falando?R.: Notao Assinttica: como estabelecer umarelao de ordem entre funes matemticas?Funes no so nmeros!http://www.icmc.usp.br/pessoas/junio 11. Notao Assinttica Interpretaomatemtica Caracterizao de funes de 3 maneiras: limites assintticos superior, inferior e estritohttp://www.icmc.usp.br/pessoas/junio 12. Notao Assinttica Interpretaomatemtica1) Limite assinttico superior: O(g(n))Uma funo f(n) = O(g(n)), se f(n) c1*g(n) para umaconstante c1 > 0 e para n n0n0http://www.icmc.usp.br/pessoas/junio 13. Notao Assinttica Interpretaomatemtica2) Limite assinttico inferior: W(g(n))Uma funo f(n) = W(g(n)), se f(n) c1*g(n) para umaconstante c1 > 0 e para n n0http://www.icmc.usp.br/pessoas/junio 14. Notao Assinttica Interpretaomatemtica3) Limite assinttico estrito: q(g(n))Uma funo f(n) = q(g(n)), se c1*g(n) f(n) c2*g(n)para um constantes c1 e c2 > 0 e para n n0http://www.icmc.usp.br/pessoas/junio 15. Notao Assinttica InterpretaomatemticaPrincipais limites assintticos:O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(2n)http://www.icmc.usp.br/pessoas/junio 16. Notao AssintticaAplicao a algoritmosExemplo: suponha um algoritmo para calcular asoma de uma seqncia de nmeroshttp://www.icmc.usp.br/pessoas/junio 17. Notao AssintticaAplicao a algoritmosAlgForcaBruta(int n){soma = 0for(i = 1 to n)soma = soma + ihttp://www.icmc.usp.br/pessoas/junio} 1 n n Custo total: 1 + n + n = 2n + 1 f(n) = 2n + 1 18. Notao AssintticaAplicao a algoritmosAlgInstataneo(int n){soma = n*(n+1)/2 4}http://www.icmc.usp.br/pessoas/junio Custo total: 4 f(n) = 4 19. Notao AssintticaAplicao a algoritmosAlgBobo(int n){soma = 0for(i = 0 to n){for(j = 1 to i){soma = soma + 1}}} 1 n n((n+1)/2) n((n+1)/2) Custo total: 1 + n + n((n+1)/2) + n((n+1)/2) f(n) = n2 + n +1http://www.icmc.usp.br/pessoas/junio 20. Notao AssintticaAplicao a algoritmosO que temos ento: AlgForcaBruta: f(n) = 2n + 1 AlgInstantaneo: f(n) = 4 AlgBobo: f(n) = n2 + n +1http://www.icmc.usp.br/pessoas/junio 21. Notao AssintticaAplicao a algoritmosO AlgForcaBruta tem complexidadef(n) = q(g(n))= q(n) , isto , g(n) = nMas por qu, se f(n) = 2n + 1?R.: segundo a definio de limite assinttico estritoc1*g(n) f(n) c2*g(n) temos:1*n f(n) = 2n + 1 3*nhttp://www.icmc.usp.br/pessoas/junio 22. Notao AssintticaAplicao a algoritmosO AlgInstantaneo tem complexidadef(n) = q(g(n))= q(1) , isto , g(n) = 1Mas por qu, se f(n) = 4?R.: segundo a definio de limite assinttico estritoc1*g(n) f(n) c2*g(n) temos:3*1 f(n) = 4 5*1http://www.icmc.usp.br/pessoas/junio 23. Notao AssintticaAplicao a algoritmosO AlgBobo tem complexidadef(n) = q(g(n))= q(n2) , isto , g(n) = n2Mas por qu, se f(n) = n2 + n + 1?R.: segundo a definio de limite assinttico estritoc1*g(n) f(n) c2*g(n) temos:1* n2 f(n) = n2 + n + 1 2* n2http://www.icmc.usp.br/pessoas/junio 24. Notao AssintticaAplicao a algoritmosO que temos ento:AlgForcaBruta: f(n) = 2n + 1 = q(n)AlgInstantaneo: f(n) = 4 = q(1)AlgBobo: f(n) = n2 + n +1 = q(n2)Analisando-se o que a notao assinttica define,verificam-se dois fatos:http://www.icmc.usp.br/pessoas/junio 25. Notao AssintticaAplicao a algoritmosAnalisando-se o que a notao assinttica define,verificam-se dois fatos:1) A notao assinttica no est interessada nafuno especfica f(n), mas na sua taxa decrescimento com relao a n. As constantes dafuno f(n) so ignoradas.2) Os termos de mais baixa ordem so ignorados.http://www.icmc.usp.br/pessoas/junio 26. Notao AssintticaAplicao a algoritmosMas por qu os termos de mais baixa ordem soignorados?R.: a notao considera valores de n arbitrariamentegrandes. Se f(n) < h(n), ento f(n)limn = 0http://www.icmc.usp.br/pessoas/junioh(n)Ex.: f(n) = n2 > h(n) = npara n = 1010, temos n = 1010 = 0n2 10100~ 27. Notao AssintticaInterpretao algortmicaOs limites assintticos tm a seguinte interpretaocom relao a algoritmos.Dado um algoritmo com funo f(n)...http://www.icmc.usp.br/pessoas/junio 28. Notao AssintticaInterpretao algortmica Limite assinttico superior: O(g(n))Indica que no importam quais as circunstncias,f(n) g(n) sempreg(n) o pior que o meu algoritmo pode fazerhttp://www.icmc.usp.br/pessoas/junio 29. Notao AssintticaInterpretao algortmicaExemplo: algoritmo de ordenao QuicksortPossveis circunstncias:1) ordenar uma seqncia que j est em ordemo Quicksort tem custo n22) ordenar uma seqncia totalmente embaralhadao Quicksort tem custo n*logn como n2 o pior que o Quicksort pode fazer, eleter sempref(n) n2 O(n2)http://www.icmc.usp.br/pessoas/junio 30. Notao AssintticaInterpretao algortmica Limite assinttico inferior: W(g(n))Indica que no importam quais as circunstncias,f(n) g(n) sempreg(n) o melhor que o meu algoritmo pode fazerhttp://www.icmc.usp.br/pessoas/junio 31. Notao AssintticaInterpretao algortmicaExemplo: algoritmo de ordenao QuicksortPossveis circunstncias:1) ordenar uma seqncia que j est em ordemo Quicksort demora n22) ordenar uma seqncia totalmente embaralhadao Quicksort demora n*logn como n*logn o melhor que o Quicksort podefazer, ele ter sempref(n) n*logn W(n*logn)http://www.icmc.usp.br/pessoas/junio 32. Notao AssintticaInterpretao algortmica Limite assinttico estrito: q(g(n))Indica que no importam quais as circunstncias,c1g(n) f(n) c2g(n) sempremeu algoritmo no faz nem pior, nem melhorque g(n)http://www.icmc.usp.br/pessoas/junio 33. Notao AssintticaInterpretao algortmicaExemplo: algoritmo de ordenao HeapsortPossveis circunstncias:1) seqncia j ordenada custo n*logn2) seqncia em ordem inversa custo n*logn3) seqncia totalmente embaralhada custo n*logn em todos os casos n*logn sempre o que o meualgoritmo fazc1n*logn f(n) c2n*logn q(n*logn)http://www.icmc.usp.br/pessoas/junio 34. Notao AssintticaInterpretao algortmica Pior caso, melhor caso e caso mdioExemplo: algoritmo de ordenao Insertion-sortPossveis circunstncias1) seqncia j ordenada custo n2) seqncia em ordem inversa custo n23) seqncia toda embaralhada custo n + d, talque d o nmero de operaes de rearranjohttp://www.icmc.usp.br/pessoas/junio 35. Notao AssintticaInterpretao algortmica Para o Insertion-sort valem as seguintes afirmaes: ele , ao mesmo tempo, O(n2) e W(n) considerando-se apenas as melhores entradas,pode-se dizer:q(n) no melhor caso considerando-se apenas as piores entradas, pode-sehttp://www.icmc.usp.br/pessoas/juniodizer:q(n2) no pior caso considerando-se apenas as demais entradas, queso a maioria mais provvel, pode-se dizer:q(n + d) no caso mdio 36. Notao AssintticaInterpretao algortmica Para o Insertion-sort valem as seguintes afirmaes: ele , ao mesmo tempo, O(n2) e W(n)1) j ordenada custo n2) em ordem inversa custo n23) toda embaralhada custo n + dhttp://www.icmc.usp.br/pessoas/junio 37. Notao AssintticaInterpretao algortmica Para o Insertion-sort valem as seguintes afirmaes: ele , ao mesmo tempo, O(n2) e W(n) considerando-se apenas as melhores entradas,pode-se dizer:q(n) no melhor caso considerando-se apenas as piores entradas, pode-se1) j ordenada custo n2) em ordem inversa custo n23) toda embaralhada custo n + dhttp://www.icmc.usp.br/pessoas/juniodizer:q(n2) no pior caso considerando-se apenas as demais entradas, queso a maioria mais provvel, pode-se dizer:q(n + d) no caso mdio 38. Notao AssintticaInterpretao algortmica Para o Insertion-sort valem as seguintes afirmaes: ele , ao mesmo tempo, O(n2) e W(n) considerando-se apenas as melhores entradas,pode-se dizer:q(n) no melhor caso considerando-se apenas as piores entradas, pode-se1) j ordenada custo n2) em ordem inversa custo n23) toda embaralhada custo n + dhttp://www.icmc.usp.br/pessoas/juniodizer:q(n2) no pior caso considerando-se apenas as demais entradas, queso a maioria mais provvel, pode-se dizer:q(n + d) no caso mdio 39. Notao AssintticaInterpretao algortmica Para o Insertion-sort valem as seguintes afirmaes: ele , ao mesmo tempo, O(n2) e W(n) considerando-se apenas as melhores entradas,pode-se dizer:q(n) no melhor caso1) j ordenada custo n2) em ordem inversa custo n23) toda embaralhada custo n + d considerando-se apenas as piores entradas, pode-sehttp://www.icmc.usp.br/pessoas/juniodizer:q(n2) no pior caso considerando-se apenas as demais entradas, queso a maioria mais provvel, pode-se dizer:q(n + d) no caso mdio 40. Notao AssintticaInterpretao algortmica Para o Insertion-sort valem as seguintes afirmaes: ele , ao mesmo tempo, O(n2) e W(n) considerando-se apenas as melhores entradas,pode-se dizer:q(n) no melhor caso considerando-se apenas as piores entradas, pode-sehttp://www.icmc.usp.br/pessoas/juniodizer:q(n2) no pior caso considerando-se apenas as demais entradas, queso a maioria mais provvel, pode-se dizer:q(n + d) no caso mdio 41. Notao AssintticaInterpretao algortmica Para o Insertion-sort valem as seguintes afirmaes: ele , ao mesmo tempo, O(n2) e W(n) considerando-se apenas as melhores entradas,pode-se dizer:q(n) no melhor caso considerando-se apenas as piores entradas, pode-sehttp://www.icmc.usp.br/pessoas/juniodizer:q(n2) no pior caso considerando-se apenas as demais entradas, queso a maioria mais provvel, pode-se dizer:q(n + d) no caso mdio 42. Notao AssintticaInterpretao algortmica Para o Insertion-sort valem as seguintes afirmaes:Intuio geral: ele , ao mesmo tempo, O(n2) e W(n) considerando-se apenas as melhores entradas,pode-se dizer:q(n) no melhor caso considerando-se apenas as piores entradas, pode-sehttp://www.icmc.usp.br/pessoas/juniodizer:q(n2) no pior caso considerando-se apenas as demais entradas, queso a maioria mais provvel, pode-se dizer:q(n + d) no caso mdio quando se diz:um algoritmo tem complexidade xisso vlido para TODAS as entradas quando se diz:um algoritmo tem complexidade x em tal casoisso vlido para TODAS as entradas que constituemaquele caso 43. Notao AssintticaLimitaes Como se pode ver, a notao assinttica temexpressividade limitada1) por si s, ela no apresenta dados a respeito daqualidade da entrada2) a notao oculta fatores importantes que podemfazer diferena na escolha de um algoritmoPor exemplo:se um algoritmo tem complexidade n2 = q(n2)e outro algoritmo tem complexidade 100n = q(n) entradas de tamanho at 100, melhor usar oprimeiro algoritmo, pois n2 100n, para n 100http://www.icmc.usp.br/pessoas/junio 44. Notao AssintticaLimitaes Como se pode ver, a notao assinttica temexpressividade limitada1) por si s, ela no apresenta dados a respeito daqualidade da entrada2) a notao oculta fatores importantes que podemfazer diferena na escolha de um algoritmoPor exemplo:se um algoritmo tem complexidade n2 = q(n2)e outro algoritmo tem complexidade 100n = q(n) entradas de tamanho at 100, melhor usar oprimeiro algoritmo, pois n2 100n, para n 100http://www.icmc.usp.br/pessoas/junio 45. Notao AssintticaLimitaes Como se pode ver, a notao assinttica temexpressividade limitada1) por si s, ela no apresenta dados a respeito daqualidade da entrada2) a notao oculta fatores importantes que podemfazer diferena na escolha de um algoritmoPor exemplo:se um algoritmo tem complexidade n2 = q(n2)e outro algoritmo tem complexidade 100n = q(n) entradas de tamanho at 100, melhor usar oprimeiro algoritmo, pois n2 100n, para n 100http://www.icmc.usp.br/pessoas/junio 46. Notao AssintticaLimitaes Como se pode ver, a notao assinttica temexpressividade limitada1) por si s, ela no apresenta dados a respeito daqualidade da entrada2) a notao preciso oculta conhecer fatores bem o importantes problema que que sepodemfazer tem, diferena para que na se escolha possa fazer de um uma algoritmoboaPor exemplo:escolha.se um algoritmo tem complexidade n2 = q(n2)e outro algoritmo tem complexidade 100n = q(n) entradas de tamanho at 100, melhor usar oprimeiro algoritmo, pois n2 100n, para n 100http://www.icmc.usp.br/pessoas/junio 47. Notao AssintticaUm indicador geral Usada para indicar os requisitos de qualquer fatorque crea como uma funo de n. Os principaisso: tempo, como j visto o espao de memria o nmero de acessos a disco a largura de bandahttp://www.icmc.usp.br/pessoas/junio 48. Algoritmos Polinomiais eExponenciaishttp://www.icmc.usp.br/pessoas/junio 49. Algoritmos Polinomiais eExponenciaisSuponha-se um algoritmo com ordem O(2n) para n = 100 um computador que realiza 212 operaes/segundo tempo total: 4*1010 anos!!!http://www.icmc.usp.br/pessoas/junio 50. http://www.icmc.usp.br/pessoas/junioConcluses A anlise de complexidade depende dacompreenso de dois fatores: interpretao matemtica interpretao algortmica Deve-se sempre lembrar que existem outrasdimenses envolvidas na anlise, como qualidadeda entrada e arquitetura computacional A anlise assinttica fornece um bom parmetro,mas no deve ser o nico a ser considerado