01 - Complexidade de Algoritmos

Estruturas de Dados (Ordenao e Pesquisa)Prof. Dr. Lus Carlos Costa Fonseca

Objetivosy Familiarizar o aluno com diversos mtodos de ordenao de

dados e com diferentes formas de armazenar e pesquisar dados, discutindo a aplicabilidade e complexidade de cada um deles; y Ao final da disciplina o aluno estar capacitado a identificar qual o mtodo de ordenao mais recomendado para uso em uma dada aplicao, bem como a forma mais eficiente de armazenar dados com vistas a uma recuperao rpida.

2

Prof. Dr. Lus Carlos Costa Fonseca

28 de julho de 2011

Ementay Mtodos de ordenao:y seleo, troca, distribuio, insero, intercalao e clculo de

endereos;

y Pesquisa de dados:y seqencial, binria, hashing, rvores de pesquisa, rvores

binrias de pesquisa, rvores AVL, B-Trees.

y Organizao de arquivos em rvore. y Organizao de arquivos de dados multimdia. y Estudo da complexidade dos mtodos apresentados. y Algoritmos Genticos de busca e recuperao. y Conceitos de Data mining.3 Prof. Dr. Lus Carlos Costa Fonseca 28 de julho de 2011

Bibliografia Sugeriday ZIVIANI, N. Projeto de Algoritmos - Com Implementaes

em PASCAL e C. So Paulo: Editora Pioneira, 1999. y DA SILVA, Osmar Quirino. Estrutura de Dados e Algoritmos Usando C - Fundamentos e Aplicaes. 472 pginas - 1 edio 2007. ISBN: 9788573936117;

4


28 de julho de 2011

Roteiro Geral da Disciplinay Parte 1: Conceitos Introdutrios; y Parte 2: Complexidade de Algoritmos; y Parte 3: Mtodos de ordenao; y Parte 4: Pesquisa de dados; y Parte 5: Organizao de arquivos em rvores; y Parte 6: Organizao de arquivos de dados multimdia; y Parte 7: Algoritmos Genticos de busca e recuperao; y Parte 8: Conceitos de Data mining.

5


28 de julho de 2011

Parte 1Conceitos Introdutrios

6


28 de julho de 2011

Roteiroy Conceitos Introdutrios

7


28 de julho de 2011

Algoritmos Estruturas de Dados e Programasy Os algoritmos fazem parte do dia-a-dia das pessoas.

Exemplos de algoritmos:y instrues para o uso de medicamentos; y indicaes de como montar um aparelho; y uma receita de culinria.

y Seqncia de aes executveis para a obteno de uma

soluo para um determinado tipo de problema.

8


28 de julho de 2011

Algoritmos Estruturas de Dados e Programasy Segundo Dijkstra, um algoritmo corresponde a uma

descrio de um padro de comportamento, expresso em termos de um conjunto finito de aes:y Executando a operao a + b percebemos um padro de

comportamento, mesmo que a operao seja realizada para valores diferentes de a e b;

9


28 de julho de 2011

Estruturas de Dadosy Estruturas de dados e algoritmos esto intimamente ligados:y no se pode estudar estruturas de dados sem considerar os

algoritmos associados a elas; y assim como a escolha dos algoritmos em geral depende da representao e da estrutura dos dados.y Para resolver um problema necessrio escolher uma

abstrao da realidade, em geral mediante a denio de um conjunto de dados que representa a situao real; y A seguir, deve ser escolhida a forma de representar esses dados.10 Prof. Dr. Lus Carlos Costa Fonseca 28 de julho de 2011

Escolha da Representao dos Dadosy A escolha da representao dos dados determinada, entre

outras, pelas operaes a serem realizadas sobre os dados; y Considere a operao de adio:y Para pequenos nmeros, uma boa representao por meio de

barras verticais (caso em que a operao de adio bastante simples); y J a representao por dgitos decimais requer regras relativamente complicadas, as quais devem ser memorizadas; y Entretanto, quando consideramos a adio de grandes nmeros mais fcil a representao por dgitos decimais (devido ao princpio baseado no peso relativo da posio de cada dgito);11 Prof. Dr. Lus Carlos Costa Fonseca 28 de julho de 2011

Programasy Programar basicamente estruturar dados e construir

algoritmos; y Programas so formulaes concretas de algoritmos abstratos, baseados em representaes e estruturas especficas de dados; y Programas representam uma classe especial de algoritmos capazes de serem seguidos por computadores; y Um computador s capaz de seguir programas em linguagem de mquina (seqncia de instrues obscuras e desconfortveis).12 Prof. Dr. Lus Carlos Costa Fonseca 28 de julho de 2011

Programasy necessrio construir linguagens mais adequadas, que

facilitem a tarefa de programar um computador; y Uma linguagem de programao uma tcnica de notao para programar, com a inteno de servir de veculo tanto para a expresso do raciocnio algortmico quanto para a execuo automtica de um algoritmo por um computador.

13


28 de julho de 2011

Tipos de Dadosy Caracteriza o conjunto de valores a que uma constante

pertence, ou que podem ser assumidos por uma varivel ou expresso, ou que podem ser gerados por uma funo. y Tipos simples de dados so grupos de valores indivisveis (como os tipos bsicos integer, boolean, char e real do Pascal).y Exemplo: uma varivel do tipo boolean pode assumir o valor

verdadeiro ou o valor falso, e nenhum outro valor.

y Os tipos estruturados em geral definem uma coleo de

valores simples, ou um agregado de valores de tipos diferentes

14


28 de julho de 2011

Tipos Abstratos de Dados (TADs)y Modelo matemtico, acompanhado das operaes denidas

sobre o modelo;y Exemplo: o conjunto dos inteiros acompanhado das operaes

de adio, subtrao e multiplicao.y TADs so utilizados extensivamente como base para o

projeto de algoritmos; y A implementao do algoritmo em uma linguagem de programao especfica exige a representao do TAD em termos dos tipos de dados e dos operadores suportados;

15


28 de julho de 2011

Tipos Abstratos de Dados (TADs)y A representao do modelo matemtico por trs do tipo

abstrato de dados realizada mediante uma estrutura de dados; y Podemos considerar TADs como generalizaes de tipos primitivos e procedimentos como generalizaes de operaes primitivas; y O TAD encapsula tipos de dados. A definio do tipo e todas as operaes ficam localizadas numa seo do programa.

16


28 de julho de 2011

Implementao de TADsy Considere uma aplicao que utilize uma lista de inteiros.

Poderamos definir TAD Lista, com as seguintes operaes:faa a lista vazia; 2. obtenha o primeiro elemento da lista; se a lista estiver vazia, ento retorne nulo; 3. insira um elemento na lista.1.

y

H vrias opes de estruturas de dados que permitem uma implementao eficiente para listas (por ex., o tipo estruturado arranjo);

17


28 de julho de 2011

Implementao de TADsy Cada operao do tipo abstrato de dados implementada

como um procedimento na linguagem de programao escolhida; y Qualquer alterao na implementao do TAD ca restrita parte encapsulada, sem causar impactos em outras partes do cdigo; y Cada conjunto diferente de operaes define um TAD diferente, mesmo atuem sob um mesmo modelo matemtico; y A escolha adequada de uma implementao depende fortemente das operaes a serem realizadas sobre o modelo.18 Prof. Dr. Lus Carlos Costa Fonseca 28 de julho de 2011

Medida do Tempo de Execuo de um Programay O projeto de algoritmos fortemente influenciado pelo

estudo de seus comportamentos; y Depois que um problema analisado e decises de projeto so finalizadas, necessrio estudar as vrias opes de algoritmos a serem utilizados, considerando os aspectos de tempo de execuo e espao ocupado; y Muitos desses algoritmos so encontrados em reas como pesquisa operacional, otimizao, teoria dos grafos, estatstica, probabilidades, entre outras.

19


28 de julho de 2011

Tipos de Problemas na Anlise de Algoritmosy Anlise de um algoritmo particular:y Qual o custo de usar um dado algoritmo para resolver um

problema especfico? y Caractersticas que devem ser investigadas:y anlise do nmero de vezes que cada parte do algoritmo deve ser

executada, y estudo da quantidade de memria necessria.

20


28 de julho de 2011

Tipos de Problemas na Anlise de Algoritmosy Anlise de uma classe de algoritmos:y Qual o algoritmo de menor custo possvel para resolver um

problema particular? y Toda uma famlia de algoritmos investigada; y Procura-se identificar um que seja o melhor possvel; y Coloca-se limites para a complexidade computacional dos algoritmos pertencentes classe;

21


28 de julho de 2011

Custo de um Algoritmoy Determinando o menor custo possvel para resolver

problemas de uma dada classe, temos a medida da dificuldade inerente para resolver o problema; y Quando o custo de um algoritmo igual ao menor custo possvel, o algoritmo timo para a medida de custo considerada; y Podem existir vrios algoritmos para resolver o mesmo problema; y Se a mesma medida de custo aplicada a diferentes algoritmos, ento possvel compar-los e escolher o mais adequado.22 Prof. Dr. Lus Carlos Costa Fonseca 28 de julho de 2011

Medida do Custo pela Execuo do Programay Pode ser feito medindo diretamente o tempo de execuo de

um programa em um computador real; y Tais medidas so bastante inadequadas e os resultados jamais devem ser generalizados:y os resultados so dependentes do compilador que pode

favorecer algumas construes em detrimento de outras; y os resultados dependem do hardware; y quando grandes quantidades de memria so utilizadas, as medidas de tempo podem depender deste aspecto.

23


28 de julho de 2011

Medida do Custo pela Execuo do Programay Apesar disso, h argumentos a favor de se obterem medidas

reais de tempo.y Ex.: quando h vrios algoritmos distintos para resolver um

mesmo tipo de problema, todos com um custo de execuo dentro de uma mesma ordem de grandeza. y Assim, so considerados tanto os custos reais das operaes como os custos no aparentes, tais como alocao de memria, indexao, carga, dentre outros.

24


28 de julho de 2011

Medida do Custo pela Execuo do Programay Usa um modelo matemtico baseado em um computador

idealizado; y Deve ser especificado o conjunto de operaes e seus custos de execues; y mais usual ignorar o custo de algumas das operaes e considerar apenas as operaes mais significativas; y Ex.: algoritmos de ordenao. Consideramos o nmero de comparaes entre os elementos do conjunto a ser ordenado e ignoramos as operaes aritmticas, de atribuio e manipulaes de ndices, caso existam.25 Prof. Dr. Lus Carlos Costa Fonseca 28 de julho de 2011

Funo de Complexidadey Para medir o custo de execuo de um algoritmo comum

definir uma funo de custo ou funo de complexidade f; y f(n) a medida do tempo necessrio para executar um algoritmo para um problema de tamanho n; y Funo de complexidade de tempo: f(n) mede o tempo necessrio para executar um algoritmo em um problema de tamanho n; y Funo de complexidade de espao: f(n) mede a memria necessria para executar um algoritmo em um problema de tamanho n.26 Prof. Dr. Lus Carlos Costa Fonseca 28 de julho de 2011

Funo de Complexidadey Utilizaremos f para denotar uma funo de complexidade de

tempo daqui para a frente; y A complexidade de tempo na realidade no representa tempo diretamente, mas o nmero de vezes que determinada operao considerada relevante executada.

27


28 de julho de 2011

Exemplo: Maior Elementoy Considere o algoritmo para encontrar o maior elemento de

um vetor de inteiros A[1..n], n >= 1.int maior(Vetor A) { int i, Temp; Temp = A[0]; for (i = 1; i < n; i++) if (Temp < A[i]) Temp = A[i]; return Temp; }

28


28 de julho de 2011

Exemplo: Maior Elementoy Seja f uma funo de complexidade tal que f(n) o nmero de

comparaes entre os elementos de A, se A contiver n elementos. y Logo f(n) = n -1, para n > 0; y Vamos provar que o algoritmo apresentado no programa acima timo... y Teorema: Qualquer algoritmo para encontrar o maior elemento de um conjunto com n elementos, n - 1, faz pelo menos n - 1 comparaes;

29


28 de julho de 2011

Exemplo: Maior Elementoy Prova: Cada um dos n - 1 elementos tem de ser mostrado,

por meio de comparaes, que menor do que algum outro elemento; y Logo n - 1 comparaes so necessrias; y O teorema acima nos diz que, se o nmero de comparaes for utilizado como medida de custo, ento a funo Max do programa anterior tima.

30


28 de julho de 2011

Tamanho da Entrada de Dadosy A medida do custo de execuo de um algoritmo depende

principalmente do tamanho da entrada dos dados. y comum considerar o tempo de execuo de um programa como uma funo do tamanho da entrada. y Para alguns algoritmos, o custo de execuo uma funo da entrada particular dos dados, no apenas do tamanho da entrada.

31


28 de julho de 2011

Tamanho da Entrada de Dadosy No caso da funo Max do programa do exemplo, o custo

uniforme sobre todos os problemas de tamanho n. y J para um algoritmo de ordenao isso no ocorre: se os dados de entrada j estiverem quase ordenados, ento o algoritmo pode ter que trabalhar menos.

32


28 de julho de 2011

Melhor Caso, Pior Caso e Caso Mdioy Melhor caso: menor tempo de execuo sobre todas as

entradas de tamanho n. y Pior caso: maior tempo de execuo sobre todas as entradas de tamanho n. y Se f uma funo de complexidade baseada na anlise de pior caso, o custo de aplicar o algoritmo nunca maior do que f(n). y Caso mdio (ou caso esperado): mdia dos tempos de execuo de todas as entradas de tamanho n.

33


28 de julho de 2011

Melhor Caso, Pior Caso e Caso Mdioy Na anlise do caso esperado, supe-se uma distribuio de

probabilidades sobre o conjunto de entradas de tamanho n e o custo mdio obtido com base nessa distribuio. y A analise do caso mdio geralmente muito mais difcil de obter do que as anlises do melhor e do pior caso. y comum supor uma distribuio de probabilidades em que todas as entradas possveis so igualmente provveis. y Na prtica isso nem sempre verdade.

34


28 de julho de 2011

Exemplo Registros de um Arquivoy Considere o problema de acessar os registros de um

arquivo. y Cada registro contm uma chave nica que utilizada para recuperar registros do arquivo. y O problema: dada uma chave qualquer, localize o registro que contenha esta chave. y O algoritmo de pesquisa mais simples o que faz a pesquisa seqencial.

35


28 de julho de 2011

Exemplo Registros de um Arquivoy Seja f uma funo de complexidade tal que f(n) o nmero de

registros consultados no arquivo (nmero de vezes que a chave de consulta comparada com a chave de cada registro).y melhor caso: f(n) = 1 (registro procurado o primeiro

consultado); y pior caso: f(n) = n (registro procurado o ltimo consultado ou no est presente no arquivo); y caso mdio: f(n) = (n + 1)/2.

36


28 de julho de 2011

Exemplo Registros de um Arquivoy No estudo do caso mdio, vamos considerar que toda

pesquisa recupera um registro. y Se pi for a probabilidade de que o i-simo registro seja procurado, e considerando que para recuperar o i-simo registro so necessrias i comparaes, ento y f(n) = 1 x p1 + 2 x p2 + 3 x p3 + ... + n x pn. y Para calcular f(n) basta conhecer a distribuio de probabilidades pi.

37


28 de julho de 2011

Exemplo Registros de um Arquivoy Se cada registro tiver a mesma probabilidade de ser acessado

que todos os outros, ento pi = 1/n; 1 *Max) *Max = A[i]; if (A[i] < *Min) *Min = A[i]; } }

39


28 de julho de 2011

Exemplo - Maior e Menor Elemento (1)y Seja f(n) o nmero de comparaes entre os elementos de A,

se A contiver n elementos. y Logo f(n) = 2(n 1), para n > 0, para o melhor caso, pior caso e caso mdio. y MaxMin1 pode ser facilmente melhorado: a comparao A[i] < Min s necessria quando a comparao A[i] > Max d falso.

40


28 de julho de 2011

Exemplo - Maior e Menor Elemento (2)y Com a implementao da melhoria ficaria:

void maxmin2(Vetor A, int *Max, int *Min) { int i; *Max = A[0]; *Min = A[0]; for (i = 1; i < n; i++) { if (A[i] > *Max) *Max = A[i]; else if (A[i] < *Min) *Min = A[i]; } }

41


28 de julho de 2011

Exemplo - Maior e Menor Elemento (2)y Para a nova implementao temos:y melhor caso: f(n) = n 1 (quando os elementos esto em ordem

crescente); y pior caso: f(n) = 2(n 1) (quando os elementos esto em ordem decrescente); y caso mdio: f(n) = 3n/2 3/2;y No caso mdio, A[i] maior do que Max a metade das vezes; y Logo para n > 0 teremos:

42


28 de julho de 2011

Exemplo - Maior e Menor Elemento (3)y Considerando o nmero de comparaes realizadas, existe a

possibilidade de obter um algoritmo mais eficiente:Compare os elementos de A aos pares, separando-os em dois subconjuntos (maiores em um e menores em outro), a um custo de n/2 comparaes; 2. O mximo obtido do subconjunto que contm os maiores elementos, a um custo de (n/2) - 1 comparaes; 3. O mnimo obtido do subconjunto que contm os menores elementos, a um custo de (n/2) 1 comparaes.1.

43


28 de julho de 2011

Exemplo - Maior e Menor Elemento void maxmin3(Vetor A, int *Max, int *Min) { (3) int i, FimDoAnel;if ((n % 2) == 0) { A[n] = A[n-1]; FimDoAnel = n; } else FimDoAnel = n - 1; if (A[0] > A[1]) { *Max = A[0]; *Min = A[1]; } else { *Max = A[1]; *Min = A[0]; } i = 3; while (i A[i]) { if (A[i-1] > *Max) *Max = A[i-1]; if (A[i] < *Min) *Min = A[i]; } else { if (A[i-1] < *Min) *Min = A[i-1]; if (A[i] > *Max) *Max = A[i]; } i += 2; } }44 Prof. Dr. Lus Carlos Costa Fonseca 28 de julho de 2011

Exemplo - Maior e Menor Elemento (3)y Os elementos de A so comparados dois a dois e os

elementos maiores so comparados com Max e os elementos menores so comparados com Min; y Quando n mpar, o elemento que est na posio A[n] duplicado na posio A[n + 1] para evitar um tratamento de exceo; y Para esta implementao, para n >0, teremos para o melhor caso, pior caso e caso mdio:

45


28 de julho de 2011

Comparao entre os Algoritmos MaxMin1, MaxMin2 e MaxMin3y A tabela apresenta uma comparao entre os algoritmos dos

programas MaxMin1, MaxMin2 e MaxMin3, considerando o nmero de comparaes como medida de complexidade; y Os algoritmos MaxMin2 e MaxMin3 so superiores ao algoritmo MaxMin1 de forma geral; y O algoritmo MaxMin3 superior ao algoritmo MaxMin2 com relao ao pior caso e bastante prximo quanto ao caso mdio;

46


28 de julho de 2011

Comparao entre os Algoritmos MaxMin1, MaxMin2 e MaxMin3

47


28 de julho de 2011

Comportamento Assinttico de Funesy O parmetro n fornece uma medida da dificuldade para se

resolver o problema; y Para valores suficientemente pequenos de n, qualquer algoritmo custa pouco para ser executado, mesmo os ineficientes; y A escolha do algoritmo no um problema crtico para problemas de tamanho pequeno; y Logo, a anlise de algoritmos realizada para valores grandes de n;

48


28 de julho de 2011

Comportamento Assinttico de Funesy Estuda-se o comportamento assinttico das funes de custo

(comportamento de suas funes de custo para valores grandes de n); y O comportamento assinttico de f(n) representa o limite do comportamento do custo quando n cresce.

49


28 de julho de 2011

Dominao Assintticay A anlise de um algoritmo geralmente conta com apenas

algumas operaes elementares; y A medida de custo ou medida de complexidade relata o crescimento assinttico da operao considerada; y Denio: Uma funo f(n) domina assintoticamente outra funo g(n) se existem duas constantes positivas c e m tais que, para n >= m, temos |g(n)| = 0.

52


28 de julho de 2011

Notao Oy Escrevemos g(n) = O(f(n)) para expressar que f(n) domina

assintoticamente g(n). L-se g(n) da ordem no mximo f(n). y Exemplo: quando dizemos que o tempo de execuo T(n) de um programa O(n2), significa que existem constantes c e m tais que, para valores de n >= m, T(n) =

0, n = m, n2 = n para qualquer n >= m, e no existe uma constante c que possa ser maior ou igual a n para todo n.

56


28 de julho de 2011

Notao Oy Exemplo: g(n) = 3n3 + 2n2 + n O(n3).y Basta mostrar que 3n3 + 2n2 + n = 0. y A funo g(n) = 3n3 + 2n2 + n tambm O(n4), entretanto esta

afirmao mais fraca do que dizer que g(n) O(n3).y Exemplo: g(n) = log5 n O (log n).y O logb n difere do logc n por uma constante que no caso logb

c. y Como n = c logc n, tomando o logaritmos base b em ambos os lados da igualdade temos que logb n = logb clogc n = logc n X logb c.

57


28 de julho de 2011

Operaes com a Notao O

58


28 de julho de 2011

Operaes com a Notao Oy Exemplo: regra da soma O(f(n) + O(g(n)).y Suponha trs trechos cujos tempos de execuo so O(n), O(n2) e

O(n log n). y O tempo de execuo dos dois primeiros trechos O(max(n, n2)), que O(n2). y O tempos de execuo de todos os trs trechos ento O(max(n2, n log n)), que O(n2).

59


28 de julho de 2011

Classes de comportamento assintticoy Se f uma funo de complexidade para um algoritmo F,

ento O(f) considerada a complexidade assinttica ou o comportamento assinttico do algoritmo F. y A relao de dominao assinttica permite comparar funes de complexidade; y Entretanto, se as funes f e g dominam assintoticamente uma a outra, ento os algoritmos associados so equivalentes; y Nestes casos, o comportamento assinttico no serve para comparar os algoritmos;

60


28 de julho de 2011

Classes de comportamento assintticoy Por exemplo, considere dois algoritmos F e G aplicados

mesma classe de problemas, sendo que F leva trs vezes o tempo de G ao serem executados, isto , f(n) = 3g(n), sendo que O(f(n)) = O(g(n)); y Logo, o comportamento assinttico no serve para comparar os algoritmos F e G, porque eles diferem apenas por uma constante;

61


28 de julho de 2011

Comparao de programasy Podemos avaliar programas comparando as funes de

complexidade, negligenciando as constantes de proporcionalidade; y Um programa com tempo de execuo O(n) melhor que outro com tempo O(n2); y Porm, as constantes de proporcionalidade podem alterar esta considerao;

62


28 de julho de 2011

Comparao de programasy Exemplo: um programa leva 100n unidades de tempo para

ser executado e outro leva 2n2. Qual dos dois programas melhor?y depende do tamanho do problema; y Para n < 50, o programa com tempo 2n2 melhor do que o que

possui tempo 100n; y Para problemas com entrada de dados pequena prefervel usar o programa cujo tempo de execuo O(n2); y Entretanto, quando n cresce, o programa com tempo de execuo O(n2) leva muito mais tempo que o programa O(n).

63


28 de julho de 2011

Principais classes de problemasy f(n) = O(1)y Algoritmos de complexidade O(1) so ditos de complexidade

constante; y Uso do algoritmo independe de n; y As instrues do algoritmo so executadas um nmero fixo de vezes;

64


28 de julho de 2011

Principais classes de problemasy f(n) = O(log n)y Um algoritmo de complexidade O(log n) dito ter

complexidade logartmica; y Tpico em algoritmos que transformam um problema em outros menores; y Pode-se considerar o tempo de execuo como menor que uma constante grande; y Quando n mil, log2 n 10, quando n 1 milho, log2 n 20; y Para dobrar o valor de log n temos de considerar o quadrado de n; y A base do logaritmo muda pouco estes valores: quando n 1 milho, o log2n 20 e o log10n 6.65 Prof. Dr. Lus Carlos Costa Fonseca 28 de julho de 2011

Principais classes de problemasy f(n) = O(n)y Um algoritmo de complexidade O(n) dito ter complexidade

linear; y Em geral, um pequeno trabalho realizado sobre cada elemento de entrada; y a melhor situao possvel para um algoritmo que tem de processar/produzir n elementos de entrada/sada; y Cada vez que n dobra de tamanho, o tempo de execuo dobra;

66


28 de julho de 2011

Principais classes de problemasy f(n) = O(n log n)y Tpico em algoritmos que quebram um problema em outros

menores, resolvem cada um deles independentemente e ajuntando as solues depois. y Quando n 1 milho, n log2 n cerca de 20 milhes. y Quando n 2 milhes, n log2 n cerca de 42 milhes, pouco mais do que o dobro.

67


28 de julho de 2011

Principais classes de problemasy f(n) = O(n2)y Um algoritmo de complexidade O(n2) dito ter complexidade

quadrtica; y Ocorrem quando os itens de dados so processados aos pares, muitas vezes em um anel dentro de outro; y Quando n mil, o nmero de operaes da ordem de 1 milho. y Sempre que n dobra, o tempo de execuo multiplicado por 4; y teis para resolver problemas de tamanhos relativamente pequenos;68 Prof. Dr. Lus Carlos Costa Fonseca 28 de julho de 2011

Principais classes de problemasy f(n) = O(n3)y Um algoritmo de complexidade O(n3) dito ter complexidade

cbica; y teis apenas para resolver pequenos problemas; y Quando n 100, o nmero de operaes da ordem de 1 milho; y Sempre que n dobra, o tempo de execuo fica multiplicado por 8;

69


28 de julho de 2011

Principais classes de problemasy f(n) = O(2n)y Um algoritmo de complexidade O(2n) dito ter complexidade

exponencial; y Geralmente no so teis sob o ponto de vista prtico; y Ocorrem na soluo de problemas quando se usa fora bruta para resolv-los; y Quando n 20, o tempo de execuo cerca de 1 milho. Quando n dobra, o tempo fica elevado ao quadrado;

70


28 de julho de 2011

Principais classes de problemasy f(n) = O(n!)y Um algoritmo de complexidade O(n!) dito ter complexidade

exponencial, apesar de O(n!) ter comportamento muito pior do que O(2n); y Geralmente ocorrem quando se usa fora bruta para na soluo do problema; y n = 20 20! = 2432902008176640000, um nmero com 19 dgitos; y n = 40 um nmero com 48 dgitos;

71


28 de julho de 2011

Comparao de funes de complexidade

72


28 de julho de 2011

Comparao de funes de complexidade

73


28 de julho de 2011

Algoritmos Polinomiaisy Algoritmo exponencial no tempo de execuo tem funo de y y

y y

complexidade O(cn); c > 1; Algoritmo polinomial no tempo de execuo tem funo de complexidade O(p(n)), onde p(n) um polinmio; A distino entre estes dois tipos de algoritmos torna-se significativa quando o tamanho do problema a ser resolvido cresce; Por isso, os algoritmos polinomiais so muito mais teis na prtica do que os exponenciais; Algoritmos exponenciais so geralmente simples variaes de pesquisa exaustiva;28 de julho de 2011

74


Algoritmos Polinomiaisy Algoritmos polinomiais so geralmente obtidos mediante

entendimento mais profundo da estrutura do problema; y Um problema considerado:y intratvel: se no existe um algoritmo polinomial para resolv-

lo; y bem resolvido: quando existe um algoritmo polinomial para resolv-lo;

75


28 de julho de 2011

Algoritmos Polinomiais X Algoritmos Exponenciaisy A distino entre algoritmos polinomiais eficientes e algoritmos y

y y

y

exponenciais ineficientes possui vrias excees; Exemplo: um algoritmo com funo de complexidade f(n) = 2n mais rpido que um algoritmo g(n) = n5 para valores de n menores ou iguais a 20; Tambm existem algoritmos exponenciais que so muito teis na prtica; Exemplo: o algoritmo Simplex para programao linear possui complexidade de tempo exponencial para o pior caso mas executa muito rpido na prtica; Tais exemplos no ocorrem com freqncia na prtica, e muitos algoritmos exponenciais conhecidos no so muito teis;28 de julho de 2011

76


Exemplo de Algoritmo Exponencialy Um caixeiro viajante deseja visitar n cidades de tal forma que

sua viagem inicie e termine em uma mesma cidade, e cada cidade deve ser visitada uma nica vez; y Supondo que sempre h uma estrada entre duas cidades quaisquer, o problema encontrar a menor rota para a viagem; y A figura ilustra o exemplo para quatro cidades c1; c2; c3; c4, em que os nmeros nos arcos indicam a distncia entre duas cidades;

77


28 de julho de 2011

Exemplo de Algoritmo Exponencialy O percurso uma soluo para o

problema, cujo percurso total tem distncia 24.

78


28 de julho de 2011

Exemplo de Algoritmo Exponencialy Um algoritmo simples seria verificar todas as rotas e escolher y

y y y

a menor delas; H (n 1)! rotas possveis e a distncia total percorrida em cada rota envolve n adies, logo o nmero total de adies n!; No exemplo anterior teramos 24 adies; Suponha agora 50 cidades: o nmero de adies seria 50! 1064; Em um computador que executa 109 adies por segundo, o tempo total para resolver o problema com 50 cidades seria maior do que 1045 sculos s para executar as adies;

79


28 de julho de 2011

Exemplo de Algoritmo Exponencialy O problema do caixeiro viajante aparece com freqncia em

problemas relacionados com transporte, mas tambm aplicaes importantes relacionadas com otimizao de caminho percorrido.

80


28 de julho de 2011

Tcnicas de Anlise de Algoritmosy Determinar o tempo de execuo de um programa pode ser um

problema matemtico complexo; y Determinar a ordem do tempo de execuo, sem preocupao com o valor da constante envolvida, pode ser uma tarefa mais simples; y A anlise utiliza tcnicas de matemtica discreta, envolvendo contagem ou enumerao dos elementos de um conjunto:y y y y y y

Manipulao de somas; Produtos; Permutaes; Fatoriais; Coeficientes binomiais; Soluo de equaes de recorrncia;

81


28 de julho de 2011

ExercciosD o conceito de algoritmo, tipo de dados e tipo abstrato de dados. 2. O que significa dizer que um algoritmo executa em um tempo proporcional a n? 3. Qual algoritmo voc prefere: um algoritmo que requer n5 passos ou um que requer 2n passos? 4. Explique a diferena entre O(1) e O(2)?1.

82


28 de julho de 2011

ExercciosImplemente os trs algoritmos apresentados nos programas para obter o mximo e o mnimo de um conjunto contendo n elementos. Execute os algoritmos para valores suficientemente grandes de n, gerando casos de teste para o melhor caso, pior caso e caso esperado. Comente os resultados obtidos. 2. Faa uma pesquisa sobre outras notaes diferentes da notao O. Apresente na forma de trabalho.1.

83


28 de julho de 2011

Obrigado!y Contatos:y [email protected] y [email protected] y [email protected]

84


28 de julho de 2011

Documents

01 - Complexidade de Algoritmos