AlgoritmoseEstruturasdeDados

1、Estruturas de Dados e Algoritmos 2001, Claudio Esperana1IntroduoO que um algoritmo?Processo sistemtico para computar um resultado a partir de dados de entrada O que so estruturas de dados?Maneira de organizar dados e operar sobre elesAlgoritmos + estruturas de dados = programasUm programa a expresso

2、 em linguagem formal (inteligvel por um computador) de um algoritmo.2Projeto de AlgoritmosEntender a entradaEntender o que se espera na sadaRepetir:Bolar um mtodo,Se o mtodo correto, entoAnalisar a complexidade do mtodo,Se complexidade aceitvel, terminar.Implementar (programar)3Projeto de Estruturas

3、 de DadosUma modelagem abstrata dos objetos a serem manipulados e das operaes sobre elesTipo de Dados Abstrato (“Abstract Data Type”)Ex.: Uma “pilha”, com operaes “push”, “pop” etc.Uma modelagem concreta do TDA, isto , como armazenar o TDA em memria/disco e que algoritmos devem ser usados para imple

4、mentar as operaes Ex.: Pilha armazenada como lista encadeada ou vetor . 4Projeto versus ImplementaoUm bom projeto leva a uma boa implementaoTodas as idias principais j foram estudadasA traduo do projeto em programa quase mecnica(ou no)Programar uma arteUm algoritmo inferior bem programado pode ser m

5、ais til que um algoritmo eficiente mal programadoH consideraes prticas quase to importantes quanto um bom projeto, como por exemplo,Interfaces ManutenibilidadeDocumentao5Algoritmos e ComplexidadeEficincia de um algoritmo Complexidade de tempo: quanto “tempo” necessrio para computar o resultado para

6、uma instncia do problema de tamanho nPior caso: Considera-se a instncia que faz o algoritmo funcionar mais lentamenteCaso mdio: Considera-se todas as possveis instncias e mede-se o tempo mdioEficincia de uma estrutura de dadosComplexidade de espao: quanto “espao de memria/disco” preciso para armazen

7、ar a estrutura (pior caso e caso mdio)Complexidade de espao e tempo esto freqentemente relacionadas6Algoritmos e ComplexidadeEficincia medida objetivamente depende de:Como o programador implementou o algoritmo/EDCaractersticas do computador usado para fazer experimentos:Velocidade da CPUCapacidade e

8、 velocidade de acesso memria primria / secundriaEtcLinguagem / Compilador / Sistema Operacional / etcPortanto, a medio formal de complexidade tem que ser subjetiva, porm matematicamente consistente Complexidade assinttica 7Complexidade AssintticaTempo / espao medidos em nmero de “passos” do algoritm

9、o / “palavras” de memria ao invs de segundos ou bytesAnlise do algoritmo / e.d. permite estimar uma funo que depende do tamanho da entrada / nmero de dados armazenados (n).Ex.: Percebe-se que medida que n aumenta, o termo cbico comea a dominarA constante que multiplica o termo cbico tem relativament

10、e a mesma importncia que a velocidade da CPU / memria Diz-se que T(n) O(n3)8Complexidade AssintticaDefinio:T(n) O( f (n) se existem constantes c e n0 tais que T(n) c f (n) para todo n n0Alternativamente, T(n) O( f (n) se lim n T(n) / f (n) constante (mas no infinito)Exemplo:9Limite Superior e Limite

11、 InferiorNotao O usada para estabelecer limites superiores de complexidadePara estabelecer limites inferiores de complexidade usa-se a notao DefinioT(n) ( f (n) se existem constantes c e n0 tais que c f (n) T(n) para todo n n0Alternativamente, T(n) ( f (n) se lim n T(n) / f (n) 0 para todo n n0(pode

12、 ser, inclusive, infinito) 10Limites JustosObserve que se T (n) O (n3) ento, T (n) O (n4), T (n) O (n5), etc Analogamente, se T (n) (n3) ento, T (n) (n2), T (n) (n), etcSe uma funo T (n) tem como limites superior e inferior a mesma funo f (n), ento diz-se que f (n) um limite justo de T (n), ou T (n)

13、 (f (n)DefinioT (n) (f (n) T (n) O (f (n) T (n) (f (n) 11Inventrio de funes de complexidadeT (n) O (1) : constante mais rpido, impossvelT (n) O (log log n) : super-rpidoT (n) O (log n) : logartmico muito bom T (n) O (n) : linear o melhor que se pode esperar se algo no pode ser determinado sem examin

14、ar toda a entradaT (n) O (n log n) : limite de muitos problemas prticos, ex.: ordenar uma coleo de nmerosT (n) O (n2) : quadrtico T (n) O (nk) : polinomial ok para n pequenoT (n) O (kn), O (n!), O (nn) : exponencial evite! 12Exemplo: Pontos mximos em 2DUm ponto mximo de uma coleo um que no dominado

15、por nenhum outro (da coleo)Diz-se que um ponto (x1, y1) domina um ponto (x2, y2) se x1 x2 e y1 y213Exemplo Algoritmo Fora BrutaBasta testar todos os pontos e verificar se so mximos:proc maximos (Inteiro n, Ponto p 1.n) para i desde 1 at n fazer dominado falso j 1 enquanto dominado jn fazer se ij dom

16、ina (pj,pi) ento dominado verdadeiro j j + 1 se dominado ento reportar (pi) 14Observaes sobre pseudo-cdigo uma descrio do algoritmo para humanos No precisa conter detalhes desnecessrios Ex.: Assumimos que p no contm pontos duplicados, mas este pode ser um detalhe importante para o implementadorPreci

17、sa ser inteligvelSe o algoritmo usa outro algoritmo, este deve ser bvio ou deve ser explicitado. Ex.: funo domina deve ser explicitada? proc domina (Ponto p, Ponto q) retornar p.x q.x p.y q.y 15Correo do algoritmoSe o algoritmo no bvio, deve-se dar uma justificativa de sua correoEm particular:Enumer

18、e restries sobre a entrada admitida pelo algoritmoDiga porque cada resultado computado satisfaz o que pedidoDiga porque nenhum resultado correto omitido16Anlise de complexidade (pior caso)O pior caso acontece quando todos os pontos so mximosO interior do lao mais interno tem complexidade constante,

19、digamos 2 (o comando “se” e a atribuio a “j”)O lao mais interno tem complexidadeO interior do lao mais externo tem complexidadeO algoritmo tem complexidade 17SomatriosPropriedades18Alguns somatrios notveis19Resolvendo somatriosO que faramos se no soubssemos queUsar limites aproximadosAproximar por i

20、ntegrais20Justificando a aproximao por integral21Resolvendo somatrios por induoFormula-se um palpite e tenta-se prov-lo. Ex.:Prova do caso base:Para n = 0, o somatrio 0Trivialmente verdadeiro se admitirmos d = 0Prova do caso genrico22Resolvendo somatrios por induoProva do caso genrico:Coeficientes d

21、e potncias iguais tm “bater”Resolvendo temos a = 1/3, b = 1/2 e c = 1/6 23Organiza dados de mesma natureza (mesmo tamanho) em posies sucessivas da memriaCada dado identificado por um ndiceDado um ndice i possvel computar o endereo de memria correspondente em tempo constanteSe o array alocado a parti

22、r do endereo A0 e cada dado ocupa k posies, ento o i-simo elemento est no endereo Ai= A0 + i.kMatrizes so construdas analogamente como vetores de vetoresArray (vetores, matrizes)D0D1D2D3DNA0A1A2A3AN24ArrayEstrutura de dados fundamentalDiversas outras estruturas so implementadas usando arraysEm ltima

23、 anlise, a prpria memria um arrayProblemas:Alocao de memriaQuantas posies deve ter o array para uma dada aplicao?O que fazer se precisarmos mais?Como inserir um novo dado entre o k-simo e o (k+1)-simo elemento?Como remover o k-simo elemento?25Busca em ArraysDado um array A contendo n valores nas pos

24、ies A0 . An-1 e um valor v, descobrir:Se v pertence ao array (problema + simples)Qual ou quais posies de A contm v (normalmente assume-se que todos os dados em A so distintos)Algoritmo trivial: busca sequencialproc buscasequencial (v, n, A0.n-1) achei falso i 0 enquanto i n e no achei fazer se Ai =

25、v ento achei verdadeiro seno i i + 1 se achei ento reportar (i) seno reportar(-1)26Busca em ArraysBusca seqencial simples testa trs condies dentro do lao. possvel alterar o algoritmo para empregar apenas um teste no lao de repetioBusca com Sentinela:Usa-se uma posio a mais no final do array (An) que

26、 carregada com uma cpia do dado sendo buscado (v)Como garantido que v ser encontrado, no preciso se precaver contra o acesso de uma posio i no existente 27Busca Seqencial com Sentinelaproc busca_com_sentinela (v, n, A0.n) An v i 0 enquanto A i v fazer i i + 1 se i n ento reportar (i) % encontrado se

27、no reportar(-1) % no encontrado28Busca Seqencial Anlise A anlise de pior caso de ambos os algoritmos para busca seqencial so obviamente O(n), embora a busca com sentinela seja mais rpidaA anlise de caso mdio requer que estipulemos um modelo probabilstico para as entradas. Sejam: E0 , E1 , En-1 as en

28、tradas v correspondentes s situaes onde v=A0, v=A1, v=An-1En entradas v tais que v no pertence ao array Ap(Ei) a probabilidade da entrada Ei ocorrert (Ei) a complexidade do algoritmo quando recebe a entrada Ei Assumimos: p(Ei) = q/n para i np(En) = 1-q29Busca Seqencial Anlise de Caso MdioSe admitirm

29、os t (Ei) = i+1, ento temos como complexidade mdia:Para q=1/2, temos complexidade mdia 3n/4Para q=0, temos complexidade mdia nPara q=1, temos complexidade mdia n/230Arrays OrdenadosSe os dados se encontram ordenados (em ordem crescente ou decrescente), a busca pode ser feita mais eficientementeOrden

30、ao toma tempo (n log n)til se a coleo no alterada ou se alterada pouco freqentemente Busca seqencial ordenada tem complexidade mdia = n/2Busca binria tem complexidade pior caso O(log n) 31Busca Seqencial Ordenadaproc busca_ordenada (v, n, A 0 . n) An v i 0 enquanto A i v fazer i i + 1 se i n e A i =

31、 v ento reportar (i) % encontrado seno reportar (-1) % no encontrado32Busca Binriaproc busca_binria (v, n, A 0 . n1) inf 0 % limite inferior sup n-1 % limite superior enquanto inf sup fazer meio (inf + sup) div 2 se A meio v ento sup meio 1 seno retornar (meio) % Valor encontrado retornar (-1) % Val

32、or no encontrado33Busca Binria - Anlise de ComplexidadeO algoritmo funciona examinando as posies Ainf, Ainf+1, AsupCada iterao do lao elimina aproximadamente metade das posies ainda no examinadas. No pior caso:Inicialmente: nAps a 1a iterao: n/2Aps a 2a iterao: n/4 Aps a k-sima iterao: n/2k = 1Logo,

33、 no pior caso, o algoritmo faz log2 n iteraes, ou seja, o algoritmo tem complexidade O(log n)34Arrays - Insero e Remoo de Elementos preciso empregar algoritmos de busca se:A posio do elemento a ser removido no conhecida O array no pode conter elementos repetidos Se o array ordenado, deseja-se preser

34、var a ordemDeslocar elementos para criar / fechar posiesSe o array no ordenado,Insero: Adicionar elemento no final do arrayRemoo: Utilizar o elemento do final do array para ocupar a posio removida Se todas as posies esto preenchidas, insero ocasiona overflowRealocar o array Reportar erro35Exemplo: I

35、nsero em Array Ordenado Assume-se que o array A pode conter elementos iguaisExpresses lgicas so avaliadas em curto-circuitoproc insero_ordenada (v, n, max, A 0 . max 1) se n 0 e A i1 v fazer A i A i1 i i1 A i v n n + 1 seno reportar (Overflow) 36Exemplo: Remoo em Array Ordenado Algoritmo remove o el

36、emento A iPressupe-se que i foi obtido por uma operao de busca proc remoo_ordenada (i, n, A 0 . n1) se i n ento n n1 enquanto i 0A poltica de insero e remoo maneira de uma pilha tambm conheciada como “LIFO”: Last In, First Out 40Implementando Pilhas com ArraysAssumimos que uma pilha P tem os seguint

37、es campos/componentes:P.max = nmero mximo de dados comportado pela pilhaP.A 0 . P.max 1 = array com P.max elementosP.n = nmero de elementos presentes na pilha (inicialmente 0)Nossa implementao armazena os dados na pilha em P.A 0 . P.n 1, na mesma ordem em que foram empilhados:P.A 0 o dado mais antig

38、oP.A P.n 1 o dado mais recente41Implementando Pilhas com Arrays proc empilha (dado v, pilha P) se P.n 0 ento P.n P.n 1 seno reportar (Underflow)proc altura (pilha P) retornar (P.n)proc topo (pilha P) retornar (P.A P.n 1)42Complexidade da Implementao de PilhaTodas as operaes so O(1)Se for necessrio t

39、ratar overflow com realocao, insero pode ter complexidade de pior caso O(n)Um novo array de comprimento maior (ex.: 2 max) alocadoTodos os elementos so copiados para o novo array43FilasSo comumente definidas as seguintes operaes sobre filas:Enfileira (dado v, fila F) : o dado v posto na fila FDesenf

40、ileira (fila F) : descarta o dado mais antigo (menos recentemente enfileirado) da fila FComprimento (fila F) : retorna o nmero de elementos na fila FPrximo (fila F) : retorna o dado mais antigo da fila FA poltica de insero e remoo de dados maneira de uma fila conhecida como “FIFO” First In First Out

41、44Filas Implementadas com ArraysUma fila F pode ser implementada usando uma estrutura com os seguintes camposF.max = nmero mximo de dadosF.A 0 . F.max1 = array onde os dados so postosF.incio = ndice do 1o elemento da fila (inicialmente 0)F.n = nmero de elementos da filaOs elementos da fila so armaze

42、nados consecutivamente a partir de F.A F.incio podendo “dar a volta” e continuar a partir de F.A 0. Exemplo:0123456789Amax = 10incio = 7 n = 5 Primeiroelementoltimo elemento45Filas Implementadas com Arraysproc enfileira (dado v, fila F) se F.n 0 ento F.incio (F.incio + 1) mod F.max F.n F.n 1 seno re

43、portar (Underflow)proc comprimento (fila F) retornar F.nproc prximo (fila F) retornar F.A F.incio46Ordenao de ArraysOperao de grande importncia terica e prticaMuitos algoritmos conhecidos com complexidade O(n log n):HeapSortQuickSortMergeSortFreqentemente, algoritmos com complexidade assinttica pior

44、 tipicamente O(n2) acabam sendo mais eficientes para n pequeno:BubbleSortInsertionSort47Dividir para ConquistarVamos estudar o MergeSort, um algoritmo sob o princpio “Dividir para Conquistar” ou “Divide and Conquer”Consiste de:Dividir a tarefa em pequenas subtarefas“Conquistar” resolver cada subtare

45、fa aplicando o algoritmo recursivamente a cada umaCombinar as solues das subtarefas construindo assim a soluo do problema como um todoTipicamente, algoritmos do tipo “Dividir para Conquistar” so recursivosNa anlise de algoritmos recursivos os limites de complexidade precisam ser determinados resolve

46、ndo recorrncias48MergeSortConsidere um array A1.n. O algoritmo consiste das seguintes fasesDividir A em 2 sub-colees de tamanho n/2Conquistar: ordenar cada sub-coleo chamando MergeSort recursivamenteCombinar as sub-colees ordenadas formando uma nica coleo ordenadaSe uma sub-coleo tem apenas um eleme

47、nto, ela j est ordenada e configura o caso base do algoritmo49MergeSort7 5 2 4 1 6 3 07 5 2 41 6 3 02 47 51 63 027453106Dividirentrada0 1 2 3 4 5 6 72 4 5 70 1 3 62 45 71 60 327453106Combinarsada50MergeSortA rotina MergeSort abaixo ordena as posies i, i+1, i+n1 do array AA rotina Merge dada a seguir

48、proc MergeSort (A , i, n) se n 1 ento m n div 2 MergeSort (A, i, m) MergeSort (A, i + m, n m) Merge (A, i, i + m, n) 51MergeSortproc Merge (A , i1, i2, n) array B i, j, k i1, i2, i1 enquanto i i2 e j i1 + n fazer se A i Aj ento B k A i k, i k + 1, i + 1 seno B k A j k, j k + 1, j + 1 enquanto i 1, a

49、 rotina chama: a si mesma, recursivamente:Uma vez c/ n valendo n/2Outra vez c/ n valendo n - n/2 = n/2Merge, que executa n operaesPortanto, para n 1, T(n) = T (n/2) + T (n/2) + n56Resolvendo RecorrnciasVimos que a anlise do algoritmo MergeSort resultou numa frmula recorrente:Para resolver tais probl

50、emas, pode-se empregar muitas tcnicas. Vamos ver apenas algumas:“Chute” + verificao por induoIterao57Percebendo padresVejamos como T (n) se comporta para alguns valores de nT(1) = 1T(2) = T(1) + T(1) + 2 = 1 + 1 + 2 = 4T(3) = T(2) + T(1) + 3 = 4 + 1 + 3 = 8T(4) = T(2) + T(2) + 4 = 4 + 4 + 4 = 12T(8)

51、 = T(4) + T(4) + 8 = 12 + 12 + 8 = 32T(16) = T(8) + T(8) + 16 = 32 + 32 + 16 = 80T(32) = T(16) + T(16) + 32 = 80 + 80 + 32 = 19258Percebendo PadresPodemos vislumbrar que como o algoritmo opera dividindo os intervalos sempre por 2, um padro pode emergir para valores de n iguais a potncias de 2De fato

52、 observamos o seguinte quando consideramos o valor de T(n) / n:T(1) / 1=1T(2) / 2=2T(4) / 4=3T(8) / 8=4T(16) / 16=5T(2k) / 2k = k+1Ou seja, para potncias de 2, T(n) / n = (log2 n) + 1, ou T(n) = (n log2 n) + n59Provando o Palpite por InduoPrimeiro vamos nos livrar dos arredondamentos T (n/2) e T (n/

53、2) provando o teorema apenas para valores de n iguais a potncias de 2Esta hiptese simplificadora se justifica pois o algoritmo no se comporta de maneira significativamente diferente quando n no uma potncia de 2Portanto, temosVamos provar por induo que, para n = 1 ou qualquer valor par de n maior que

54、 1, T(n) = (n log2 n) + n60Provando o Palpite por InduoCaso base: n = 1T(1) = (1 log2 1) + 1 = 0 + 1 = 1Caso geral: como n uma potncia de 2, n/2 tambm e podemos admitir que a hiptese verdadeira para qualquer potncia de 2 n bk ento T(n) (nlogba)Caso 2: se a = bk ento T(n) (nk log n)Caso 3: se a bk en

55、to T(n) (nk)(Como antes, assumimos que n uma potncia de b e que o caso base T(1) tem complexidade constante)74Teorema Mestre SimplificadoExemplos:MergeSort: T(n)=2T(n/2)+ na=2, b=2, k=1. caso 2 se aplica e T(n) (n log n)T(n)=3T(n/2)+ n2a=3, b=2, k=2caso 3 se aplica (322) e T(n) (n2)T(n)=2T(n/2)+ n l

56、og nTeorema mestre (simplificado ou completo) no se aplicaPode ser resolvida por iterao75Teorema Mestre e rvores de RecursoOs trs casos do teorema mestre podem ser entendidos como as trs maneiras de distribuir o trabalho na rvore de recurso:Caso 1: O trabalho concentrado nas folhas (ex.: T(n)=4T(n/3

57、)+ n)Caso 2: O trabalho dividido igualmente entre todos os nveis (ex.: MergeSort)Caso 3: O trabalho concentrado nas razes (ex.: 3T(n/2)+ n2)76QuickSortO QuickSort provavelmente o algoritmo mais usado na prtica para ordenar arraysSua complexidade de caso mdio (n log n) Sua complexidade de pior caso (

58、n2) mas a probabilidade do pior caso acontecer fica menor medida que n cresce (caindo para 0 medida que n tende a infinito)O passo crucial do algoritmo escolher um elemento do array para servir de pivO QuickSort pode se tornar um algoritmo de complexidade de pior caso (n log n) se escolhermos sempre

59、 a mediana como piv. Usando um algoritmo que seleciona a mediana dos elementos em (n), mas na prtica o algoritmo acaba tendo um desempenho ruim77QuickSort: Partio O QuickSort utiliza como base um algoritmo de particionamentoParticionar um array em torno de um piv x significa dividi-lo em trs segment

60、os contguos contendo, respectivamente, todos os elementos menores que x, iguais a x, e maiores que x.Vamos definir uma funo partio que divide um array A de n elementos indexados a partir do ndice i, isto , Ai, Ai+1 Ai + n 1Como piv, escolheremos x = valor inicial de AiA rotina retorna m, o nmero de