Click here to load reader

Projeto e Análise de Algoritmos

  • View
    219

  • Download
    68

Embed Size (px)

Text of Projeto e Análise de Algoritmos

  • Universidade Federal do PiauCentro de Educao Aberta e a Distncia

    Francisco jos de arajojos Messias alves da silva

    PROJETO E ANLISE DE ALGORITMOS

  • Francisco jos de arajojos Messias alves da silva

    Projeto e Anlise de Algoritmos

    ministrio da Educao - mECUniversidade Aberta do brasil - UAbUniversidade Federal do Piau - UFPIUniversidade Aberta do Piau - UAPI

    Centro de Educao Aberta e a Distncia - CEAD

  • Zilda Vieira ChavesRoberto Denes Quaresma Rgosamuel Falco silvaantonio F. de Carvalho FilhoDjane Lemos Ferreira Gabriel Gesiel dos santos sobrinho

    PREsIDENTE Da REPBLICaMINIsTRO Da EDUCaO

    GOVERNaDOR DO EsTaDOREITOR Da UNIVERsIDaDE FEDERaL DO PIaU

    sECRETRIO DE EDUCaO a DIsTNCIa DO MECPREsIDENTE Da CaPEs

    COORDENaDOR GERaL Da UNIVERsIDaDE aBERTa DO BRasILDIRETOR DO CENTRO DE EDUCaO aBERTa E a DIsTNCIa Da UFPI

    Dilma Vana Rousseff Linhares

    aloisio MercadanteWilson Nunes Martins

    jos arimatia Dantas LopesCarlos Eduardo Bielshowskyjorge almeida GuimaresJoo Carlos Teatini de S. Clmaco

    Gildsio Guedes Fernandes

    aDMINIsTRaOaDMINIsTRaO PBLICa

    CINCIas BIOLGICasFILOsOFIa

    FsICaLETRas PORTUGUs

    LETRas INGLsMaTEMTICa

    PEDaGOGIaQUMICa

    sIsTEMas DE INFORMaO

    antonella Maria das Chagas sousaFabiana Rodrigues de almeida CastroMaria da Conceio Prado de OliveiraZoraida Maria Lopes FeitosaMiguel arcanjo Costajos Vanderlei CarneiroLvia Fernanda Nery da Silva

    Joo Bencio de Melo Neto

    Vera Lcia Costa OliveiraMilton Batista da Silva

    Leonardo Ramon Nunes de sousa

    TCNICa EM assUNTOs EDUCaCIONaIsEDIO

    PROjETO GRFICODIaGRaMaO

    REVIsO ORTOGRFICaREVIsO GRFICa

    Prof. Dr. Ricardo alaggio Ribeiro ( Presidente )Des. Tomaz Gomes Campelo

    Prof. Dr. jos Renato de arajo sousaProf. Dr. Teresinha de jesus Mesquita Queiroz

    Prof. Francisca Maria soares MendesProf. Iracildes Maria de Moura F LimaProf. Dr. joo Renr Ferreira de Carvalho

    EQUIPE DE DEsENVOLVIMENTO CONsELHO EDITORIaL Da EDUFPI

    2013. Universidade Federal do Piau - UFPI. Todos os direitos reservados.

    a responsabilidade pelo texto e imagens desta obra do autor. O contedo desta obra foi licenciado, temporria e gratuitamente, para utilizao no mbito do Sistema Universidade Aberta do Brasil, atravs da UFPI. O leitor se compromete a utilizar o contedo desta obra para aprendizado pessoal, sendo que a reproduo e distribuio ficaro limitadas ao mbito interno dos cursos. A citao desta obra em trabalhos acadmicos e/ou profissionais poder ser feita, com indicao da fonte. A cpia desta obra sem autorizao expressa, ou com intuito de lucro, constitui crime contra a propriedade intelectual, com

    sanes previstas no Cdigo Penal. proibida a venda deste material.

    A663p Arajo, Francisco Jos de.Projetos e anlise de algoritimos / Francisco Jos de Arajo.

    Teresina : EDUFPI/CEAD, 2013.128p.

    1. Algoritimos. 2. Algoritimos - Anlise. 3. Educao a Distncia. I. Ttulo.

    CDD 005.1

  • Ao desenvolver um sistema computacional, no podemos deixar de levar em considerao todos os aspectos que influem positiva ou

    negativamente na sua execuo. Projetar bem um sistema antes de sua implementao pode reduzir drasticamente o tempo de sua concluso, alm de utilizar mais eficientemente todos os recursos computacionais que se tem

    disposio. O objetivo desta apostila proporcionar ao leitor um entendimento

    no que se refere ao desenvolvimento de bons algoritmos e sua anlise. O texto foi escrito de forma simples e objetiva. Cada captulo acompanhado de embasamento terico e prtico dos fundamentos de anlise, bem como exemplos de boas implementaes e exerccios. A bibliografia e a web bibliografia ao fim das notas so suficientes para que o leitor se aprofunde na

    teoria apresentada em cada unidade.Na Unidade I so apresentados os conceitos relacionados aos

    fundamentos de anlise de algoritmos, os quais sero descritos suas definies e principais situaes relacionadas aos problemas de anlise.

    Na Unidade II descrita a forma como analisar as principais estruturas contidas em algoritmos, de maneira que possa determinar uma ordem de grandeza do seu desempenho.

    Na Unidade III so apresentadas as principais estratgias para elaborao de algoritmos com bom desempenho, conforme a natureza dos problemas tomados.

    Por fim, na Unidade IV apresentada uma classificao dos principais

    problemas computacionais em estudo e as suas ordens de complexidade, enfocando a natureza de sua resoluo.

  • UNIDADE 1FUNDaMENTOs DE aNLIsE DE aLGORITMOs

    Fundamentos de algoritmos ....................................................... 11Conceitos bsicos ........................................................................ 18Recorrncias ................................................................................ 32

    UNIDADE 2TCNICas DE aNLIsE DE aLGORITMOs

    anlise de algoritmos .................................................................. 47Complexidade de algoritmos ....................................................... 48

    UNIDADE 3TCNICas DE PROjETO DE aLGORITMOs

    Introduo ................................................................................... 63Fora bruta .................................................................................. 63Dividir- e-conquistar .................................................................... 64Programao dinmica ................................................................ 70algoritmos gulosos ...................................................................... 76

    11

    35

    35

  • UNIDADE 4CLassEs DE PROBLEMas

    Introduo ................................................................................. 103solucionabilidade de problemas .............................................. 103Formas de problemas ................................................................ 105Problemas de deciso classe p .................................................. 106Classe np ................................................................................... 108Classe co-np ............................................................................... 109Classe np-completo ................................................................... 110algumas redues ..................................................................... 112A classe np-difcil ....................................................................... 113Relaes entre classes de problemas ........................................ 113Backtracking e branch-and-bound ............................................ 114

    35

  • UNIDADE 1Fundamentos de Anlise de

    Algoritmo

    Esta unidade dedicada aos conceitos iniciais relacionados anlise de algoritmos, noes de funo de complexidade e suas variaes, eficincias e avaliao emprica de algoritmos e s

    variveis envolvidas nesse processo.

    Resumindo

  • PROJETO E ANLISE DE ALGORITMOS 11

    FUNDAmENtos DE ANlIsE DE AlgoRItmo

    FUNDAMENTOS DE ALGORITMOS

    Ao verificar que um dado programa est muito lento, uma pessoa

    prtica pede uma mquina mais rpida ao seu chefe, mas o

    ganho potencial que uma mquina mais rpida pode proporcionar

    tipicamente limitado por um fator de 10 por razes tcnicas

    ou econmicas. Para obter um ganho maior, preciso buscar

    melhores algoritmos. Um bom algoritmo, mesmo rodando em uma

    mquina lenta,sempre acaba derrotando (para instncias grandes

    do problema) um algoritmo pior rodando em uma mquina rpida.

    Sempre.

    - S. S. Skiena, The Algorithm Design Manual

    Introduo

    Neste captulo, apresentaremos alguns fundamentos de algoritmos e algumas ideias iniciais sobre funo de complexidade, eficincia de

    algoritmos, etapas para o desenvolvimento de algoritmos eficientes, medida

    de complexidade e anlise emprica.

    Algoritmo

    O que um Algoritmo?

    Definies:

    Segundo o dicionrio de Aurlio, algoritmo sob o ponto de vista da matemtica processo de clculo ou de resoluo de um grupo de problemas

  • unidade 112

    semelhantes em que se manipulam, com generalidade e sem restries, regras formais para a obteno do resultado ou da soluo do problema.

    Um algoritmo uma sequncia de instrues no ambguas para

    resolver um problema, isto , para obter uma sada desejada para qualquer entrada legtima em um intervalo de tempo finito.

    Um algoritmo qualquer procedimento computacional que recebe como entrada um valor ou um conjunto de valores e produz como sada um valor ou um conjunto de valores.

    Podemos concluir que um algoritmo uma sequncia de passos

    computacionais que transformam a entrada em sada. Exemplo: Considere a seguinte funo:F(x)= x3/5A sua entrada o x e a sua sada e o y ou f(x), o valor que a funo

    retorna. O algoritmo seria o seguinte:1. Entrada: receber o valor de x.2. Elevar x ao cbico e guardar o nmero resultante como z.3. Dividir z por 5 e guardar o nmero resultante como y.4. Sada: imprimir o valor de y.O algoritmo, portanto, a lgica do nosso problema matemtico

    ou informtico. a sequncia de passos que eu fao na minha cabea (ou

    no papel) antes de escrever para uma das linguagens. Se formos pensar, veremos que tudo o que fazemos um algoritmo, um procedimento que recebe uma entrada e envia uma sada, no s no computador, mas na vida.

    Exemplo: Encontrar o maior e o menor valor de um vetor com n valores. Formalmente, o problema poderia ser colocado da seguinte forma:

    Entrada: uma sequncia de n nmeros < a1, a2, a3,...,an> Sada: os valores Min e Max, o menor e o maior valor, respectivamente,

    dentre os valores da entrada.Podem existir vrios algoritmos diferentes para resolver o mesmo

    problema. Nos casos acima, poderamos ter um algoritmo que fizesse a

    mesma coisa de maneira diferente.Os algoritmos descritos neste trabalho sero escritos em uma

    linguagem de pseudocdigo, por est mais prximo da linguagem natural.Por que estudar algoritmos? Devemos conhecer um conjunto de algoritmos de diferentes

    reas, alm de sermos capazes de projetar novos algoritmos e analisar suas eficincias. O estudo de algoritmos , reconhecidamente, a pedra

  • PROJETO E ANLISE DE ALGORITMOS 13

    fundamental da cincia da computao. Algoritmo muito mais que um

    ramo da cincia da computao. o ncleo da cincia da computao e com

    toda a imparcialidade, pode ser considerado relevante para a maioria das cincias, negcios e tecnologia. Programas de computadores no existiriam

    sem algoritmos.

    Instncia

    Instncia de um problema consiste de todas as entradas necessrias para se calcular uma soluo para o problema. Uma instncia de um problema computacional um possvel valor para a entrada.

    Alguns exemplos de problemas e suas instncias:Os nmeros 25, -30 e 10 definem uma instncia do problema da

    equao do segundo grau. A instncia consiste em encontrar um nmero inteiro x tal que 25x2 -30x +10=0.

    < 42, 6, 11,17, 4> uma instncia para o problema da ordenao.

    Um algoritmo dito correto se, para cada instncia de entrada, ele para com a sada correta.

    Que tipos de Problemas so resolvidos com algoritmos?

    A ordenao no o nico problema computacional para o qual foram desenvolvidos algoritmos.

    Algumas aplicaes prticas de algoritmos. Segundo Cormen (2002):1. O Projeto Genoma Humano: tem como objetivo identificar todos os

    100.000 genes do DNA humano, determinar as sequencias dos 3 bilhes de pares de bases qumicas que constituem o DNA humano, armazenar essas informaes em bancos de dados e desenvolver ferramentas para anlise de dados. Cada uma dessas etapas exige Algoritmos sofisticados.

    2. A Internet: permite que pessoas de todo mundo acessem e obtenham com rapidez grandes quantidades de informaes. Para isso, so empregados Algoritmos inteligentes com a finalidade de gerenciar e manipular esse

    grande volume de dados.3. O Comrcio Eletrnico: permite que mercadorias e servios sejam

    negociados e trocados eletronicamente. Possui a capacidade de manter privadas as informaes, como nmeros de cartes de crdito, senhas e extratos bancrios. As tecnologias usadas so a criptografia e as

    ATENO!!Nem todos os problemas podem ser resolvidos por algoritmos. Exemplo. Como se tornar rico e famoso?

  • unidade 114

    assinaturas digitais e so baseadas em Algoritmos numricos e teoria dos nmeros.

    4. Na indstria: alocar recursos escassos de maneira mais eficiente. Localizar poos, designar as tripulaes para os vos, instalar um provedor de servios da Internet, etc. Esses exemplos podem ser resolvidos com o uso da programao linear.

    Alguns exemplos de problemas concretos:

    1. Mapa rodovirio no qual a distncia entre cada par de pontos marcado, tendo como objetivo determinar a menor rota de um ponto a outro do nmero de rotas;

    2. Determinao do produto de n matrizes A1, A2, ... ,An. Como a multiplicao de matrizes associativa, existem vrias ordens de multiplicao;

    3. Temos n pontos no plano e desejamos encontrar a envoltria convexa desses pontos, ou seja, um polgono convexo que contm os pontos.

    Essas listas esto longe de esgotar os exemplos, mas exibem duas caractersticas comuns a muitos algoritmos interessantes:

    1. Existem muitas solues candidatas, porm a maioria no aquilo que desejamos. Encontrar a soluo que queremos pode representar um desafio.

    2. Existem aplicaes prticas. Dos problemas anteriores, o caminho mais curto fornece os exemplos mais fceis. Uma empresa de transportes que utiliza caminhes tem interesse financeiro em encontrar os caminhos mais

    curtos em uma rede ferroviria ou rodoviria porque menores caminhos resultam em menor trabalho e menor consumo de combustvel.

    Complexidade e custo de um algoritmo

    Determinando o menor custo possvel para resolver problemas de uma dada classe, temos a medida de dificuldade inerente para resolver o

    problema. Quando o custo de um algoritmo igual ao menor custo possvel, o algoritmo timo para a medida de custo considerada. Podem existir vrios algoritmos para resolver o mesmo problema.

  • PROJETO E ANLISE DE ALGORITMOS 15

    Medida do custo para execuo do programa

    Em muitas situaes podem existir vrios algoritmos para resolver o mesmo problema, sendo necessrio escolher o melhor. Se a mesma medida de custo aplicada a diferentes algoritmos, ento possvel compar-los e escolher o mais adequado para resolver o problema em questo.

    O custo de utilizao de um algoritmo pode ser medido de vrias maneiras. Uma delas mediante a execuo do programa em um computador, sendo o tempo de execuo medido diretamente. As medidas de tempo obtidas so bastante inadequadas e os resultados jamais devem ser generalizados: os resultados so dependentes do compilador que podem favorecer algumas construes em detrimento de outras; os resultados dependem de hardware; quando grandes quantidades de memria so utilizadas, as medidas de tempo dependem deste aspecto.

    Uma maneira mais adequada de medir o custo de utilizao de um algoritmo por meio do uso de um modelo matemtico baseado em um computador idealizado. Devendo especificar o conjunto de operaes e seus

    custos de execues, mais usual ignorar o custo de algumas das operaes e considerar apenas as operaes mais significativas.

    Funo de Complexidade

    Para medir o custo de execuo de um algoritmo, comum definir

    uma funo de custo ou funo de complexidade f. A funo f(n) a medida do tempo necessrio para executar um algoritmo para um problema de tamanho n.

    Existem dois tipos de funes de complexidade a saber: a funo de complexidade de tempo, onde f(n) mede o tempo necessrio para executar um algoritmo em um problema de tamanho n e a funo de complexidade de espao, onde f(n) mede a memria necessria para executar um algoritmo em um problema de tamanho n.

    Utilizaremos f para denotar uma funo de complexidade de tempo daqui para frente. A complexidade de tempo na realidade no representa tempo diretamente, mas o nmero de vezes que determinada operao considerada relevante executada.

    Funo de Complexidade de Espao f(n): mede a memria necessria para executar um algoritmo em um problema de tamanho n.

  • unidade 116

    Complexidade de um algoritmo o tempo requerido para a execuo deste algoritmo.

    Eficincia de Algoritmos

    Algoritmos criados para resolver o mesmo problema muitas vezes diferem de forma drstica em sua eficincia. Essas diferenas podem ser

    muito mais significativas que as diferenas relativas a hardware e software.

    Dado um problema a ser resolvido, interessante procurar diversos algoritmos que o faa escolher o melhor deles. Mas como decidir quais dos algoritmos melhor?

    Exemplo: Vamos comparar um computador mais rpido (computador

    A) que execute a ordenao por insero com um computador mais lento (computador B) que execute a ordenao por intercalao. Cada um deles deve ordenar um milho de nmeros.

    Suponha que o computador A execute um bilho de instrues por segundo e o computador B execute apenas dez milhes de instrues por segundo. Assim, o computador A ser 100 vezes mais rpido que o computador B.

    Suponha que o programador mais esperto codifique a ordenao

    por insero em linguagem de mquina para o Computador A e que o cdigo resultante exija 2n2 instrues para ordenar n nmeros. Por outro lado, a ordenao por intercalao programada para o computador B por um programador mdio que utiliza uma linguagem de alto nvel com um compilador ineficiente, com o cdigo resultante de 50nlogn instrues. Para

    ordenar um milho de nmeros, o Computador A demora:

    Computador B demora:

    Usando o algoritmo cujo tempo de execuo mais lento, at mesmo com um compilador fraco, o Computador B funciona 20 vezes mais rpido que o computador A. Portanto, o algoritmo de ordenao por intercalao gasta

  • PROJETO E ANLISE DE ALGORITMOS 17

    menos tempo computacional, ou seja, mais eficiente do que o algoritmo de

    ordenao por insero e esta vantagem ainda maior proporo que n cresce.

    Metodologia para Desenvolver Algoritmos Eficientes.

    Os passos necessrios para procurar elaborar algoritmos que sejam eficientes so: Anlise do Problema, Concepo do algoritmo, Anlise de

    eficincia, Verificao e refinamento.

    Passo 1: Anlise do ProblemaA anlise do problema uma etapa importante, pois permite uma

    compreenso do que se pretende e facilita o compartilhamento com outros pesquisadores.

    Passo 2: Concepo do Algoritmo

    A concepo uma etapa criativa. Nesta fase, podem ser aplicadas as principais tcnicas de projeto de algoritmos, as quais sero estudadas posteriormente.

    Passo 3: Anlise de Eficincia

    Por outro lado, o algoritmo pode estar correto, mas no ser eficiente.

    A busca por algoritmos eficientes de suma importncia, pois uma pequena

    alterao no algoritmo poder trazer grande melhoria no desempenho do mesmo.

    Passo 4: Verificao e Refinamento

    A verificao uma etapa importante para garantir que o algoritmo

    trabalhe corretamente e faa o que deve fazer. O refinamento consiste em

    introduzir alteraes no algoritmo com vistas a torn-lo correto e melhorar sua eficincia em tempo de execuo e/ou espao de memria utilizada.

    Um algoritmo resolve um problema quando, para qualquer entrada, produz uma resposta correta quando concedidos tempo e memria suficientes

    para sua execuo.Um algoritmo que resolve um problema (teoricamente) no significa

  • unidade 118

    ser aceitvel na prtica. Os recursos de espao e tempo tm grande

    importncia em casos prticos.s vezes, o algoritmo mais direto est longe de ser razovel em

    termos de eficincia. Um exemplo o caso da soluo de sistemas de

    equaes lineares. O mtodo de Cramer, resolvendo o sistema atravs de sua definio, requer dezenas de milhes de anos para resolver um sistema

    20x20. O mesmo sistema pode ser resolvido em tempo razovel pelo mtodo de Gauss, como mostra a Tabela 1.1.

    Tabela 1.1 TAMANHO DO PROBLEMA X TEMPO DE EXECUO

    O avano tecnolgico concebe mquinas cada vez mais rpidas e que passam a resolver problemas maiores, pois a complexidade do algoritmo que determina o novo tamanho mximo do problema resolvvel.

    Uma base slida de conhecimento e tcnicas de algoritmos uma caracterstica que separa os programadores qualificados dos no

    qualificados. Com a moderna tecnologia computacional, voc pode executar

    alguns trabalhos sem saber muito sobre algoritmos, porm, com uma boa base em algoritmos, possvel fazer muito mais.

    CONCEITOS BSICOS

    A arte de programar consiste em organizar e dominar a

    complexidade

    - Edsger W. Dijkstra

    Introduo

    A anlise de algoritmos tem como objetivo melhorar, se possvel, seu

  • PROJETO E ANLISE DE ALGORITMOS 19

    desempenho e escolher, entre os algoritmos disponveis, o melhor. Existem vrios critrios de avaliao de um algoritmo como: quantidade de trabalho requerido, quantidade de espao requerido, simplicidade, exatido de resposta e otimizao (TOSCANI, 2001).

    As medidas de complexidade introduzem as ideias de complexidade de pessimista (pior caso), bem como as medidas de complexidade de tempo e espao.

    Comportamento Assinttico de Funes

    O parmetro n fornece uma medida da dificuldade para se resolver o

    problema. Para valores suficientemente pequenos de n, qualquer algoritmo

    custa pouco para ser executado, mesmo os ineficientes. A escolha do

    algoritmo no um problema crtico para problemas de tamanho pequeno. Logo, a anlise de algoritmos realizada para valores grandes de n. O

    comportamento assinttico de funo representa o limite do comportamento do custo quando n cresce. Para saber o comportamento de um algoritmo ou problema em relao ao tamanho da entrada, o que relevante?

    Exemplo: Suponha dois algoritmos A e B cujos tempos de execuo sejam TA(n)=3n+10 e TB(n)= n +1. A Figura 1.1 mostra a representao grfica,

    Qual o maior deles? A Tabela 1.2 mostra onde o algoritmo A maior do algoritmo B.

    Tabela 1.2

  • unidade 120

    Para n < 9, TA(n) > TB(n), ou seja, o algoritmo A maior do que B para todo n< 9.

    Figura 1.1 TA(n) > TB(n)

    Exemplo: Considere a existncia de dois algoritmos A e B para a

    soluo de um problema. Se a complexidade de um expressa por TA(n)=n2

    e a do outro por TB(n)=100n. Isso significa que, em funo do tamanho da entrada de dados n, o algoritmo A cresce como uma parbola e o B cresce linearmente. Desta forma, se os algoritmos forem usados para um conjunto de 30 dados, teremos: TB(30)=3000 e TA(30)=900, neste caso, TATB.

    Exemplo: Suponha TC(n) =45n+15 e TD(n)=0,1n2+0,5. Qual delas maior?

    Ordens Assintticas

    A anlise de um algoritmo geralmente conta com apenas algumas operaes elementares. A medida de custo ou medida de complexidade relata o crescimento assinttico da operao considerada.

    A complexidade assinttica definida pelo crescimento da

    complexidade para entradas suficientemente grandes. O comportamento

    assinttico de um algoritmo o mais procurado, pois para um volume grande de dados, a complexidade torna-se mais importante. Algoritmo assintoticamente mais eficiente melhor para as entradas, exceto para entradas relativamente

    pequenas.Consideremos as funes f e g mapeando naturais em reais no

  • PROJETO E ANLISE DE ALGORITMOS 21

    negativos: de N em R+ .Uma cota assinttica superior (CAS) uma funo que cresce mais

    rapidamente que outra e a partir de certo ponto est acima. Por exemplo, uma funo cbica n3 cresce mais rapidamente do que uma quadrtica n2. Dizemos que a cbica n3 CAS para n2. Do mesmo modo, uma funo exponencial 2n CAS para n2.

    Definio:

    Em geral, define-se que g uma cota assinttica superior para f, se e

    somente se (n0 N)(n n0) f(n) g(n) Para n suficientemente grande, g(n) domina f(n).

    Exemplo: O grfico da Figura 1.2 mostra esta notao O:

    Figura 1.2:

    Exemplo: Mostre que a funo exponencial 2n CAS para n2.Exerccio: Para cada um dos seguintes pares de funes f e g,

    verifique se possvel encontrar uma constante n0 N tal que:(n n0) f (n) g (n)

    a) n, nlog2nb) 2n, 3n+1

    Notao O

    A notao O define uma cota assinttica superior.

    Seja N o conjunto dos nmeros naturais e R o conjunto dos nmeros

    reais. O conjunto N* denota o conjunto dos nmeros naturais estritamente positivos, R+* representa o conjunto dos nmeros reais estritamente positivos

  • unidade 122

    e R+ o conjunto dos reais no negativos.Seja f: N * R+ uma funo arbitrria.Definio:

    Dadas duas funes assintoticamente no negativas f e g, dizemos que f est na ordem de g. Escrevemos f=O(g), se f(n) c.g(n) para algum c

    positivo e para todo n suficientemente grande.

    Em outras palavras, existe um nmero positivo c e um nmero natural no, tais que f(n) c.g(n) para todo n maior que no.

    Alternativamente, f(n) O(g(n)) se constante (mas no infinito).

    Exemplo: Seja f(n)=13n3+2n2+5nlogn e g(n)=n3, ento:

    Simbolicamente:O(g(n) = {f : N R+ | (c R+*)(n0 N)(n n0)[f(n) c.g(n)]}Normalmente diz-se que f(n) O(g(n)) ou f(n) O(g(n)). Exemplo grfico da Figura 1.3 de dominao assinttica que ilustra a

    notao O.

    Figura 1.3.

    O valor constante n0 mostrado o menor valor possvel, mas qualquer valor maior vlido.

    Exemplos de Notao OA notao O usada para estabelecer limites superiores de

    complexidade.

    ng

    nflim

    13

    log5213lim

    log5213limlim

    23

    23

    n

    n

    nn

    nnnn

    ng

    nf

  • PROJETO E ANLISE DE ALGORITMOS 23

    Exemplo: Verifique, se g(n)=(n+1)2, ento: g(n) O(n2) ou g(n)=O(n2), ou seja, (cR*+)((n0N)(nn0) g(n)

    cf(n)

    f(n)=n2 (n+1)2 c.n2

    n2+2n+1 c.n2 c 1 + 2/n + 1/n2Logo, n0=1 e c=4 Isto porque (n+1)2 4n2 para n 1.Exemplo: g(n)=3n3 + 2n2 + n O(n3) Basta mostrar que 3n3 + 2n2 + n 6n3, para n 1 A funo g(n) = 3n3 + 2n2 + n tambm O(n4), entretanto, esta

    afirmao mais fraca do que dizer que g(n) O(n3). Exemplo: g(n)=log5n O(logn). O logbn difere do logcn por uma contante no caso logbc. Como n=clogcn, tomando o logaritmo base b em ambos os lados da

    igualdade, temos que logbn=logbclogcn = logcn x logbc

    Exemplo: Suponha que f(n)=2n2 + 3n +4 e que g(n)=n2. Observe que 2n2 =3n + 4 2n2 + 3n2 + 4n2 = 9n2 desde que n 1. Resumindo, f(n) 9g(n) para todo n 1. Portanto, f(n)=O(g(n)).

    Exemplo: Suponha que f(n)= 3 + 2/n e que g(n)= n0, ou seja, g(n)=1. Ento, 3 + 2/n 3 + 1 =4 = 4n0 desde que n 2. Resumindo, f(n) 4g(n) para

    n 2. Portanto, f(n)=O(gn)).

    Exemplo: Suponha que f(n)=n3 e que g(n)=500n2. No verdade que f(n)=O(g(n)). De fato, se existissem c e n0 tais que f(n)cg(n), teramos

    n500c para todo nn0. Mas isso absurdo!

    Exemplo: 7n 2 O(n)

    Prova: Pela definio da notao O, precisou achar uma constante

    c>0 e uma constante inteira n0 >1, tais que 7n 2 cn para todo inteiro nn0. fcil perceber que uma escolha poderia ser c=7 e n0=1. De fato, esta uma das infinitas escolhas possveis porque qualquer nmero real maior ou igual

    a 7 ser uma escolha possvel para c e qualquer inteiro maior ou igual a 1

    uma escolha possvel para n0.

    Algumas regras se aplicam na avaliao O(.)

    Regra das Somas

  • unidade 124

    Proposio 1

    Se determinado algoritmo P se divide em partes independentes, digamos P1 e P2 e sendo T1(n) e T2(n) respectivamente de ordem O(f(n)) e O(g(n)) ento: T(n)=T1(n)+T2(n) e P ser de ordem O(mximo{f(n), g(n)}) (CAMPELLO & MACULAN, 1994).

    Demonstrao:

    Para c1,c2,n1 e n2 constantesT1(n) c1.f(n), n n1T2(n) c2.g(n), n n2 Sendo no= mximo{n1,n2} e com n no.Ento T1(n)+T2(n) c1.f(n)+c2.g(n) (c1+c2)mximo{f(n),g(n)}Portanto, T(n) de ordem O(mximo{f(n),g(n)}.

    Exemplo: Calcular o tempo de execuo de uma sequncia de trechos

    de programas usando a regra da soma para O(f(n))+O(g(n)).Suponha trs trechos cujos tempos de execuo so O(n), O(n2) e

    O(n.logn).O tempo de execuo dos dois primeiros O(max(n,n2)) que O(n2).Exemplo: Considere o caso em que as funes f(.) e g(.) so dadas a

    seguir:

    Neste caso:

    O tempo de execuo de todos os trs trechos O(max(n2,n.logn))

    que O(n2).

    Regra dos Produtos

    mparnse,n

    parnse,nnf

    2

    4

    mparnse,n

    parnse,nng

    3

    2

    mparnse,n

    parnse,nng,nfmximo

    3

    4

  • PROJETO E ANLISE DE ALGORITMOS 25

    Proposio 2 Se T1(n) e T2(n) so de ordem O(f(n)) e O(g(n)) respectivamente,

    ento: T(n) = T1(n) . T2(n) de ordem O(f(n).g(n)).

    Demonstrao

    Por hiptese constantes c1 , c2, n1, n2 tais que:T1(n) = O(f(n)) T1(n) c1.f(n), n n1T2(n) = O(g(n)) T2(n) c2.g(n), n n2Fazendo no = mximo{n1,n2} e c = c1.c2

    T(n)= T1(n).T2(n) c(f(n).g(n)), n noE, portanto, T(n) de ordem O(f(n).g(n)) Segue-se que O(k.f(n)) o mesmo que O(f(n)) quando k uma

    constante positiva.Outras propriedades:f(n)=O(f(n))k. O(f(n))= O(f(n)) k = constateO(f(n)) + O(f(n)) = O(f(n))O(O(f(n))) = O(f(n)) f(n)O(g(n)) = O(f(n)g(n))

    Teorema:

    Se T(n)=tmnm+tm-1n

    m-1+...+ t1n+to um polinmio de grau m ento T(n)=O(nm).

    Demonstrao:

    Usando a definio:

    T(n) = O(nm) ( c R+) T(n) c.n2, n no |T(n)| |tm|n

    m+ |tm-1|nm-1+...+ |t1|n+|to|

    |T(n)| (|tm|+ |tm-1|/n+...+ |to|/nm)nm

    |T(n)| = (|tm|+...+ |to|)nm, n 1

    Substituindo c=|tm|+...+ |to| e no=1Temos |T(n)| c|nm| T(n) c.nm T(n) = O(nm)

  • unidade 126

    Exemplo: Seja T(n)= 2x5+45x4 + 100008x2 -8888888 um polinmio de grau 5, logo T(n)=O(n5), ou seja, despreza todos os termos de grau menor do que 5 e a constante.

    Uma ferramenta poderosa e verstil para provar que alguma funo de ordem de outra a regra do limite, dadas as funes arbitrrias f,g:NR+*.

    1. Se lim(f(n)/g(n)) R+* ento f(n) O(g(n)) e g(n) O(f(n))2. Se lim(f(n)/g(n)) = 0 ento f(n) O(g(n)) mas g(n) O(f(n))3. Se lim(f(n)/g(n)) = + ento f(n) O(g(n)) e g(n) O(f(n))

    Exemplo: Sejam f(n) = logn e g(n) = n

    Deseja-se determinar a ordem relativa das duas funes.Desde que f(n) e g(n) tendem ao infinito quando n tende ao infinito,

    deve-se usar regra de lHpital para calcular este limite.

    Resoluo:

    Provar que este limite existe.

    Agora, a regra do limite nos mostra que logn O(n) e n O(logn). Em outras palavras, a funo n cresce assintoticamente mais rpido

    que log n.

    1. Notao (mega)

    A notao O nos d um limite superior para o tempo que algum algoritmo gastar para qualquer instncia de tamanho n. Para estimar um limite inferior, podemos usar a seguinte notao: (f(n)).

    Exemplo: f(n)=7n3+5 cresce menos rapidamente do que uma exponencial g(n)=2n.

    Diz-se que a exponencial g(n) f(n)).Definio:

    ngnfn

    ngnfn

    ~ ~

    /lim

    /lim

    0/2lim)2

    1//1lim/loglim n

    nnnn

  • PROJETO E ANLISE DE ALGORITMOS 27

    Diz-se que g(n) (f(n)), se e somente se, para alguma constante c R*+ e no N tal que g(n) c.f(n)

    Isto : (f(n)) = {g: NR+ |( c R*+)( no N) ( n no)[g(n) c.f(n)]}

    Em outra palavras, (f(n)) um conjunto de todas as funes g(n) limitadas inferiormente por mltiplo real positivo de f(n), para n suficientemente

    grande.Exemplo: Para mostrar que g(n)= 3n3+2n2 (n3), basta fazer c=1, e

    ento 3n3+2n2 n3 para n 0.Exemplo: Seja g(n)=n para n mpar (n 1) e g(n) = n2/10 para n par (n

    0). Neste caso, g(n) (n2), bastando considerar c=1/10 e n=0,2,4,...Exemplo: A Figura 1.4 mostra o grfico para a notao .

    Figura 1.4

    Exemplo: Seja t(n)=n3-2n2+4n, podemos afirmar que t(n) (n3), pois n3-2n2+4n 0.5n3 para n>1.

    Exemplo: Se f(n)=n2-1, ento so vlidas as igualdades f(n)=(n2), f(n)=(n) e f(n)=(1), mas no vale f(n)=(n3).

    Exerccio: Para as funes exponencial f(n)=2n e cbica g(n)=7n3+5, verifique que f(n) (g(n)), determinando as constantes c e no.

    1. Notao (Theta)

    A notao define um limite assinttico exato. Por exemplo, as funes quadrtica f(n)=5n2 + 4 e g(n)=n2 + 1 crescem com a mesma rapidez.

    Diz-se que f(n) (f(n)), ou seja, (f(n)) = O(f(n)) (f(n)), se e somente se, g(n)) = {f: NR+|( c, d R*+)( no N) (n no)[c.g(n)

  • unidade 128

    f(n) d.g(n)]}

    Podemos afirmar que duas funes f(n) e g(n), f(n)= (g(n)), se e somente se, f(n)=O(g(n)) e f(n)= (g(n)).

    Na prtica, normalmente aplicamos a notao para descrever um

    limite inferior para o melhor caso e a notao O para descrever um limite superior para o pior caso. A Figura 1.5 abaixo ilustra a notao

    Figura 1.5 f(n) (g(n))

    Exemplo: Seja g(n)=n2/3-2n. Vamos mostrar que g(n) = (n2).Temos de obter constantes c, d e n0 tais que c.n

    2 (1/3)n2 - 2n d.n2 para todo n n0.

    Dividindo por n2, temos c 1/3 - 2/n d.O lado direito da desigualdade ser sempre vlido para qualquer

    valor de n 1 quando escolhemos d 1/3. Da mesma maneira, escolhendo c

    1/21, o lado esquerdo da desigualdade ser vlido para qualquer valor de

    n 7. Logo, escolhendo c = 1/21, d = 1/3 e n0 = 7, verifica-se que n2/3 - 2n=

    (n2).Outras constantes podem existir, mas o importante que existe

    alguma escolha para as trs constantes.

    A regra do limite para a notao reformulada da seguinte forma:

    1. Se lim(f(n)/g(n)) R+* ento f(n) (g(n)) 2. Se lim(f(n)/g(n)) = 0 ento f(n) O(g(n)), mas f(n) (g(n))3. Se lim(f(n)/g(n)) = + ento f(n) (g(n)), mas f(n) (g(n))Comparao de FunesAlgumas das propriedades relacionadas a nmeros reais tambm se

    aplicam a comparao de funes assintticas. Nas propriedades seguintes, suponha que f(n) e g(n) sejam assintoticamente positivas.

    As notaes apresentadas respeitam as seguintes propriedades:

  • PROJETO E ANLISE DE ALGORITMOS 29

    Reflexividade:

    1. f(n)= (f(n))

    2. f(n)= O(f(n))3. f(n)= (f(n))

    Simetria:1. f(n)=O(g(n)) se e somente se g(n)=O(f(n))Transitividade: 2. f(n) = (g(n)) e g(n) = (h(n)) implicam f(n) = (h(n))

    3. f(n) = O(g(n)) e g(n) = O(h(n)) implicam f(n) = O(h(n))4. f(n) = (g(n)) e g(n) = (h(n)) implicam f(n) = (h(n))

    Comportamento Assinttico

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

    Exemplo: Dois algoritmos C e D aplicados mesma classe de problemas, sendo que C leva trs vezes o tempo de D ao ser executado,

    isto , f(n) = 3g(n), sendo que O(f(n)) = O(g(n)). Logo, o comportamento

    assinttico no serve para comparar os algoritmos C e D porque eles diferem apenas por uma constante.

    Podemos avaliar programas, comparando as funes de complexidade. Um programa com tempo de execuo O(n) melhor que outro com tempo O (n2). Porm, as constantes de proporcionalidade podem alterar esta considerao.

    Exemplo: Um programa leva 100n unidades de tempo para ser executado e outro leva 2n2. Qual dos dois o melhor?

    A resposta a essa pergunta depende do tamanho do problema a ser executado. Para n

  • unidade 130

    Classes de Comportamentos Assintticos

    As principais classes de problemas possuem as funes de complexidade descritas a seguir. Segundo Zivianni (2007),

    1. f(n)=O(1)1. Algoritmos de complexidade O(1) so ditos de complexidade

    constante. O uso do algoritmo independe do tamanho de n. As instrues do algoritmo so executadas um nmero fixo de vezes.

    2. f(n) = O(log n)1. Um algoritmo de complexidade O(log n) dito ter complexidade

    logartmica. Esse tipo de execuo ocorre em algoritmos que resolvem um problema transformando-o em problemas pequenos.

    1. f(n) = O(n)1. Um algoritmo de complexidade O(n) dito ter complexidade linear. 1. f(n) = O(nlog n)1. Tpico em algoritmos que quebram um problema em outros menores

    resolve cada um deles independentemente e depois unindo as solues.

    2. f(n) = O(n2)1. Um algoritmo de complexidade O(n2) dito ter complexidade

    quadrtica, os quais ocorrem quando os itens de dados so processados aos pares, sendo muitas vezes em um ninho dentro do outro. So teis para resolver problemas de tamanhos pequenos.

    3. f(n) = O(n3)1. Um algoritmo de complexidade O(n3) dito ter complexidade

    cbica. teis para resolver pequenos problemas.

    4. f(n) = O(2n)1. Um algoritmo de complexidade O(2n) dito ter complexidade

    exponencial. No so teis do ponto de vista prtico.

    5. f(n) = O(n!)1. Um algoritmo de complexidade O(n!) dito ter complexidade

    exponencial tambm, apesar de a complexidade fatorial O(n!) ter

  • PROJETO E ANLISE DE ALGORITMOS 31

    comportamento muito pior que O(2n).Segue a ordem de complexidade dos algoritmos.2. O(1) < O(log n) < O(n) < O(n log n)

  • unidade 132

    A Figura 1.4 abaixo ilustra o exemplo para quatro cidades c1, c2, c3 e c4 em que os nmeros nos arcos indicam a distncia entre as cidades. O percurso uma soluo para o problema, cujo percurso

    total em distncia 24.

    Figura 1.6 Problema do caixeiro viajante

    RECORRNCIAS

    Introduo

    Quando um algoritmo contm uma chamada recursiva, o seu tempo de execuo pode ser descrito por uma recorrncia. Uma recorrncia uma

    equao ou uma inequao que descreve uma funo em termos de seu valor em entrada menor. Para exemplificar, vamos apresentar a equao de

    recorrncia do Mergesort (Intercalao). T(n)= Cuja soluo T(n)=O(nlogn).Apresentaremos a seguir trs mtodos para resolver recorrncia, isto

    , para obter limites assintticos para a soluo.

    Algoritmos Definidos por Recorrncia

    1. Quando se deseja especificar um algoritmo para a soluo de um

    determinado problema, podemos utilizar duas abordagens:1. Definir um algoritmo iterativo.

    2. Definir um algoritmo recursivo.

    Algoritmos Iterativos:

    Saiba MaisO uso da notao O iniciou vrias discusses na comunidade de anlise de algoritmos e teoria da computao, como por exemplo, a de que a igualdade f(n) = g(n) de mo nica, ou seja, apenas no sentido esquerdo para direita, mesmo adotando-se o fato de que a notao O defina um conjunto de funes.

  • PROJETO E ANLISE DE ALGORITMOS 33

    1. Algoritmo do fatorial

    1 FAT 1

    2 para i de 2 at n, faa:3 FAT FAT * i

    4 retorne FAT

    1. Algoritmo de Fibonacci

    1 Fib(1) Fib(2) 1

    2 para i de 3 at n faa3 Fib(1) Fib(i - 2) + Fib(i 1)

    Algoritmos Recursivos

    1. Na construo de um algoritmo recursivo devemos ter o cuidado de sempre especificarmos primeiro a condio bsica para depois

    estabelecermos o passo recorrente. Estes dois elementos devero estar isolados por intermdio de uma clusula condicional do tipo:

    Se ento:

    Seno,

    Algoritmos Recursivos:

    Algoritmo Fatorial

    funo Fat(n): Se n = 0 ou n = 1, ento: retorne (1) Seno, retorne(n * Fat(n - 1))

    Algoritmo de Fibonacci funo Fib(n): Se n = 1 ou n = 2, ento:

    DesafioApresente um algoritmo recursivo para calcular o produto de dois inteiros m e n usando apenas adio.

  • unidade 134

    retorne (1) Seno, retorne (Fib(n - 2) + Fib(n - 1))

    Recorrncias

    Uma recorrncia uma frmula que define uma funo sobre os

    nmeros naturais. Uma relao de recorrncia um caminho para definir

    uma funo por uma expresso envolvendo a mesma funo.Exemplo: A recorrncia abaixo define uma funo T no conjunto dos

    nmeros naturais: T(1) =1 e T(n)=T(n-1) + 3n + 2 para n=2, 3, 4, ...Eis os valores de T(n) para valores pequenos de n:

    Seja T(n) uma funo de complexidade que representa o nmero de inspees nos n elementos do conjunto. O termo T(n) especificado em

    funo dos termos anteriores T(1), T(2), ..., T(n - 1).T(n) = T(n/3) + n, T(1) = 1 (para n=1 fazemos uma inspeo).Por exemplo: T(3) = T(3/3) + 3 = 4; T(9) = T(9/3) + 9 = 12?, e assim

    por diante.Seja T(n) uma funo de complexidade que representa o nmero de

    inspees nos n elementos do conjunto. O termo T(n) especificado em

    funo dos termos anteriores T(1), T(2),... , T(n - 1).

    Solucionando Recorrncia

    Resolver uma relao de recorrncia nem sempre fcil. Resolvendo

    uma relao de recorrncia, determina-se o tempo de execuo do algoritmo

    recursivo correspondente.Exemplo: A sequncia T abaixo se encontra definida por recorrncia:

    1. Condio bsica: T(1) = 22. Passo recorrente: T(n) = 2 T(n - 1), para n 2

  • PROJETO E ANLISE DE ALGORITMOS 35

    Solucionando Recorrncia:

    De acordo com a definio da sequncia T, temos os seguintes

    termos:T(1) = 2T(2) = 2T(1) = 2 2 = 22 T(3) = 2T(2) = 2 22 = 23 T(4) = 2T(3) = 2 23 = 24 T(5) = 2T(4) = 2 24 = 25 Podemos concluir que T(n) = 2n. Esta equao denominada de

    SOLUO EM FORMA FECHADA para a relao de recorrncia sujeita a

    condio bsica T(1). Denomina-se RESOLVER uma recorrncia ao processo

    de se encontrar uma soluo em forma fechada para a recorrncia.

    Exemplo: Atravs de induo matemtica a conjectura T(n) = 2n, verificada da seguinte forma:

    Passo bsico:

    1. T(1) = 21 = 2 verdade;

    2. Hiptese de Induo:I. Suponha que T(k) = 2k seja verdade;

    3. Passo Indutivo:Prova-se que T(k+1) = 2k+1 Pela definio temos T(k+1) = 2T((k+1)-1) = 2T(k) = 2 2k = 2k+1

    Logo, est provada nossa conjectura.

    4. Passo Indutivo:Prova-se que T(k) = 3k2/2 + 7k/2 - 4Temos T(k) = T(k-1) + 3k + 2 por definio

    T(k) = [3(k-1)2/2 + 7(k-1)/2 - 4] + 3k + 2T(k) = 3k2/2 + 7k/2 - 8/2T(k) = (3k2 + 7k - 8)/2 Logo, est provada nossa conjectura.

    Como a frmula est correta, prova-se que T(n) = O(n2).Como determinar a complexidade de um algoritmo recursivo?Exemplo: Algoritmo Mergesort

  • unidade 136

    Pode ser escrito pela recorrncia:

    Tcnicas de Recorrncia

    Apresentaremos a seguir trs mtodos para resolver recorrncias,

    isto , para obter limites assintticos para a soluo.2. Mtodo da Substituio;3. Mtodo da rvore de Recurso (iterao);

    4. Mtodo Mestre.

    Mtodo da Substituio

    Este mtodo consiste em propor uma forma para a soluo (por inspirao); determinar as constantes envolvidas por induo e mostrar que o limite estabelecido vlido. Substituio vem do fato de substituir a resposta inspirada pela hiptese indutiva aplicada a valores menores. um mtodo poderoso, mas depende da percepo de quem analisa. eficiente, mas

    s pode ser aplicado em casos nos quais seja fcil pressupor a forma de resposta.

    Exemplo: Determinar um limite superior para a recorrncia T(n) =

    2T(n/2) +(n)

    Supondo que o mtodo da soluo visualizada seja T(n) = O(n log

    n, o mtodo consiste em provar que T(n) c n log n para uma constante

    c > 0 apropriada.Assumiremos que este limite verdadeiro para n/2 , isto , T( n/2

    ) c n/2 log( n/2 ). Substituindo na recorrncia temos:

    T(n) 2(c n/2 log( n/2 ) + n c n log(n/2) + n

    c n logn c n log2 + n

    c n logn c n + n

    c n logn, para c 1

    O prximo passo consiste em provar que a nossa soluo vlida para as condies de contorno do problema, ou seja, devemos mostrar que podemos escolher a constante c to grande quanto possvel que o limite T(n) cnlogn vale para as condies de contorno. Assumindo que T(1) = 1 como

    condio de contorno da recorrncia, no conseguiremos encontrar uma

  • PROJETO E ANLISE DE ALGORITMOS 37

    constante c, pois T(1) c 1 log1 = 0. A sada para superar esta dificuldade

    consiste em usar um valor n n0 sendo n0 uma constante qualquer maior do que 1. Assim podemos impor T(2)= 4 e T(3)= 5, constantes e usar a recorrncia a partir de T(4).

    T(2) c 2 log2

    4 2 c

    c 2, para todo n 2.

    Como observamos, qualquer valor de c 2 suficiente para que os

    casos bsicos de n=2 e n=3 sejam vlidos.A grande dificuldade deste mtodo que no existe uma forma

    geral para solucionar recorrncias corretamente. Pressupor soluo exige

    experincia e criatividade na rea, entretanto existem algumas heursticas,

    rvore de recurso, que veremos adiante, que podem ajudar a gerar boas hipteses.

    Se uma recorrncia for semelhante a uma que voc j tenha visto

    antes, ento ser fcil supor uma soluo semelhante.Exemplo: Considere a recorrncia.

    T(n) = 2T( n/2 +35) + n, que semelhante recorrncia vista anteriormente, exceto pelo termo 35. Este termo no pode afetar substancialmente a soluo da recorrncia. Quando n grande, a diferena

    entre T( n/2 ) e T( n/2 +35) no grande. Conclumos que T(n)=O(nlogn), pode ser verificado usando o mtodo da substituio.

    Exemplo: Resolver a recorrncia T(n) = 2T(n ) + logn Parece difcil, porm tentaremos resolv-la mediante uma substituio

    de variveis. Por convenincia vamos considerar que n inteira. Substituindo

    m = logn obtemos T(2m) = 2T(2m/2) + m. Substituindo a recorrncia S(m) = T(2m), produzimos a recorrncia S(m) = 2S(m/2) + m, cuja soluo j conhecida, ou seja, S(m) = O(m logm) . Substituindo m obtemos T(n) = T(2m) = S(m) = O(m logm)= O(logn.log(logn))

    O Mtodo de rvore de Recurso (Iterao)

    Embora o mtodo de substituio possa fornecer uma prova de que uma soluo para uma recorrncia correta, s vezes difcil apresentar

    uma boa suposio. Traar uma rvore de recurso um caminho direto para se criar uma boa suposio. Este mtodo consiste em desenhar uma rvore cujos ns representam os tamanhos dos subproblemas. Cada nvel i

  • unidade 138

    contm todos os subproblemas de profundidade i. Dois aspectos importantes devem ser considerados: A altura da rvore e o nmero de passos executados em cada nvel. A soluo de recorrncia (tempo de execuo do algoritmo)

    a soma de todos os passos de todos os nveis. No caso particular em que o total de passos de cada nvel o mesmo, l(n), por exemplo, a soluo T(n)=h.l(n), onde h a altura da rvore.

    Uma rvore de recurso usada para gerar uma boa suposio, o qual verificado pelo mtodo de substituio.

    Talvez o mtodo seja mais intuitivo. Exemplo: Considere a equao de recorrncia do Mergesort.

    Veremos como uma rvore de recurso forneceria uma boa suposio

    para a recorrncia T(n) = 2T(n/2) + n

    1. Supomos que n potncia de 2.

    n/2h = 1 h = log2n Total = h.n A altura da rvore h=logn Logo, O(n . log n)

    Mesmo este mtodo no exigindo inspirao, requer mais lgebra que o mtodo da substituio. A ideia consiste em expandir (iterar) a recorrncia e

    express-la como um somatrio e dependendo apenas de n e das condies iniciais.

    Exemplo: Considere a recorrncia

    Soluo usando a lgebra:T(n) = 2(2T(n - 2) + 1) + 1

  • PROJETO E ANLISE DE ALGORITMOS 39

    T(n) = 4T(n - 2) + 2 + 1T(n) = 4(2T(n - 3) + 1) + 2 + 1T(n) = 23T(n - 3) + 4 + 2 + 1 - - - - - - - - - - - - - - - - - - - - T(n) = 2i T(n-i) + 2i-1 + 2i-2 +...+ 21 + 20 O caso base alcanado quando i = n - 1Logo, T(n) = 2n-1 + 2n-2 + 2n-3 +...+ 21 + 20

    T(n) = 2n - 1 = O(2n)

    Mtodo Mestre

    Este mtodo fornece uma receita de bolo para resolver recorrncia da

    forma: T(n) = aT(n/b) + f(n), onde a 1 e b > 1 so constantes e f(n) uma

    funo assintoticamente positiva. O mtodo exige a memorizao de trs

    casos, mas a soluo de muitas recorrncias torna-se mais simples.

    Utilizando o mtodo mestre, a soluo depende do Teorema Mestre.

    Teorema Mestre

    Sejam a 1 e b > 1, constantes. Seja f(n) uma funo, e seja T(n)

    definido no domnio dos inteiros no negativos pela recorrncia T(n) = aT(n/b)

    + f(n), onde n/b pode ser n/b ou n/b. Ento, T(n) pode ser limitada assintoticamente por:

    1- Se f(n) = O(nlogba-) para uma constante > 0, ento T(n) = (nlogba).2- Se f(n) = (nlogba), ento T(n) = (nlogbalogn).3- Se f(n) = (nlogba+) para uma constante > 0 e se af(n/b) cf(n)

    para alguma constante c < 1 e n suficientemente grande, ento T(n) = (f(n)). Para melhor compreender o significado deste teorema, observe que

    nos trs casos estamos comparando a funo f(n) com a funo nlogba. A

    soluo da recorrncia dada pela maior das duas funes. No caso 1, a

    funo nlogba maior, ento a soluo T(n) = (nlogba). No caso 2, as funes

    so de mesma dimenso, sendo introduzido um fator logn e a soluo T(n) = (nlogb

    alogn) = (f(n)logn). No caso 3, a funo f(n) maior, ento, a soluo T(n) = (f(n)).

    importante ressaltar que o teorema no cobre todos os casos possveis, apenas aqueles em que f(n) menor que nlogba por um fator polinomial, isto , f(n) deve ser assintoticamente menor ou maior que nlogba

  • unidade 140

    para os casos 1 e 3 do teorema Mestre. Para o caso 3, deve ser satisfeita a condio de regularidade onde af(n/b) cf(n).

    Exemplo: Considere a seguinte equao de recorrncia

    1. T(n) = 9T(n/3) + n

    Neste caso, a = 9, b = 3, f(n) = n nlogba = nlog39 = (n2) Como f(n) = O(nlogb

    a-), onde = 1, podemos aplicar o caso 1 do teorema mestre e concluir que a soluo T(n) = (n2).

    1. T(n) = T(2n/3) + 1Neste caso, a = 1, b = 3/2, f(n) = 1 e nlogba = 1.2. Aplica-se o caso 2, desde que f(n) = (nlogb

    a) = (1) e a soluo da

    recorrncia T(n) = (logn).

    3. T(n) = 3T(n/4) + nlogn Neste caso, a = 3, b = 4 e f(n) = nlogn, sendo nlogb

    a = nlog43 = O(n0,793).

    Como f(n) = (nlog42 + ), onde = 0,2, aplica-se o caso 3, caso a condio de

    regularidade puder ser preservada.

    Mtodo Mestre: Exemplo

    Assim, para n tendendo para o infinito, af(n/b) = 3(n/4)log(n/4) (3/4)

    nlogn = cf(n), para c = 3/4. Logo, pelo caso 3, a recorrncia corresponde a

    T(n) = (nlogn).

    Exerccio 1

    1. O que algoritmo? 2. Fornea um exemplo de aplicao que exija contedo algortmico no

    nvel de aplicao e discuta a funo dos algoritmos envolvidos.3. O que significa dizer que um algoritmo executa em tempo polinomial a n?4. Comparao entre os tempos de execuoPara cada funo f(n) e cada tempo t na tabela a seguir, determine o maior tamanho n de um problema que pode ser resolvido no tempo t, supondo-se que o algoritmo para resolver o problema demore f(n) microssegundos.

  • PROJETO E ANLISE DE ALGORITMOS 41

    Exerccio 2

    1. Dois algoritmos gastam n2 dias e n3 segundos, respectivamente, para resolverem uma instncia de tamanho n. Em alguma situao, o algoritmo quadrtico melhor do que o algoritmo cbico? Justificar formalmente.

    2. Sejam A e B dois algoritmos cujas complexidades so, respectivamente, determinadas pelas funes f(n) e g(n) dadas abaixo. Para cada caso, determine os valores inteiros positivos de n para os quais o algoritmo A leve menos tempo para executar do que o algoritmo B.

    1. f(n)= 2n2 -2 e g(n)= 3n +5 2. f(n)= 3n4 + 2n2 + 1 e g(n)=4n2 + 1

    3. Suponha que estamos comparando uma implementao do algoritmo de ordenao por insero com uma implementao do mergesort. O primeiro consome 8n2 unidades de tempo quando aplicado a um vetor de comprimento n e o segundo consome 64nlogn. Para que valores de n o primeiro mais rpido que o segundo?

    4. Suponha dois algoritmos A e B com funes de complexidade de tempo a(n)=n2-n+549 e b(n)=49n+49, respectivamente. Determine quais valores de n pertencentes ao conjunto dos nmeros naturais para os quais A leva menos tempo para executar do que B.

    5. Para os seguintes pares de funes, determine o menor valor para n, para o qual a segunda funo torna-se menor do que a primeira:

    a) n2, 10n c) n2/logn, n(logn)2

    b) 2n, 2n3 d) n3/2, n2.81 6. Para cada um dos seguintes pares de funes f e g, verifique se possvel

    encontrar uma constante n0 N tal que (n n0) f(n) g(n)a) n, nlog2(n) b) 2

    n, 3n+1

  • unidade 142

    7. Quais das afirmaes abaixo so verdadeiras? Justifique a sua resposta.

    a) 10n = O(n) b) 10n2 = O(n) c) 2n+1 = O(2n)d) 22n = O(2n) e) n = O(n2) f) f(n) = O(v(n)) e g(n) = O(u(n)) f(n) + g(n) = (v(n)+u(n)) g) (3/2)n2 + (7/2)n 4 =O(n2)

    8. Qual das seguintes afirmaes sobre crescimento assinttico de funes no verdadeira?

    a) se f(n)=O(g(n)) e g(n)=O(h(n)), ento f(n)=O(h(n))b) se f(n) =O(g(n)), ento g(n)=(f(n))

    c) 6n2 + 8n + 3=O(n2)d) se f(n)=O(g(n)), ento g(n)=Of(n))e) 3n3 + 30n=O(n3)

    9. verdade que n2 + 2000n +5466 = O(n2)? Justifique.10. verdade que n2 - 2000n +5466 = O(n)? Justifique.11. verdade que n4 -99988889n2 + 5000008= O(n3)? Justifique. 12. Para cada um dos seguintes pares de funes f e g, verifique se possvel

    encontrar constantes n0 N e c R+, tais que (n n0) f(n) cg(n):

    a) 25n, n3 b) 10nn2, n2n 13. Suponha que f(n) = (3/2) n2 + (7/2)n-4 e que g(n) = n2. Verifique que f(n)

    O(g(n)), determinando constantes n0 N e c R*+ . 14. Suponha que f(n) = 3n3 + 2n2 e que g(n) = n3. Verifique que f(n) O(g(n)),

    determinando constantes n0 N e c R*+ .15. Provar que a notao O transitiva, isto , se f(n) O(g(n)) e g(n)

    O(h(n)), ento f(n) O(h(n)) para qualquer funo f: N R*.16. Provar que se f(n) O(n), ento [f(n)]2 O(n2). 17. Sejam duas funes no negativas f(n) e g(n). Diz-se que f(n)=(g(n)) se

    f(n)=O(g(n)) e g(n)=O(f(n)). Mostre que max(f(n), g(n)) = (f(n) + g(n)).

    ExERCCIO III

    1. Considere a equao de recorrncia a seguir, definindo T(n):

  • PROJETO E ANLISE DE ALGORITMOS 43

    Demonstre por induo que T(n)= n(n +1)/2.2. Considere a equao de recorrncia a seguir, definindo T(n):

    Demonstre por induo que T(n)=2n

    3. Considere a recorrncia:Mostre que T(n)8n logn para n8. Deduza da que T(n)=O(nlogn).

    4. Usar o mtodo da substituio para provar que a soluo de T(n)= T(n/2) + 1 O(logn).

    5. Mostre que a soluo de T(n)=2T(n/2) + n O(n2).6. Atravs do Mtodo da Substituio, prove que:

    1. T(n)=T(n/2) + 1 O(logn)2. T(n)=2T(n/2) + n3 O(n3)

    7. Em ambos os casos, considere T(1)=1.1. Mostrar que a soluo para a recorrncia

    T(n)= O(1) para n=0T(n)= T(n-1) + 1 para n>0

    8. Atravs do Mtodo Mestre, determinar limites assintticos para as seguintes recorrncias.

    a) T(n) = 4T(n/2) + nb) T(n) = 4T(n/2) + n2 c) T(n) = 7T(n/8) + n2

    9. Atravs do Mtodo Mestre, prove que a ordem assinttica de 1. T(n)=16T(n/4) + n2 O(n2logn)2. T(n)=2T(n/2 +10) + n O(nlogn)

  • unidade 144

  • PROJETO E ANLISE DE ALGORITMOS 45

    UNIDADE 2tcnica de Anlise de

    Algoritmos

    Esta unidade reservada para a anlise mais especfica de algoritmos, em especial, aos algoritmos

    recursivos, bem como ao estudo dos mtodos de resoluo de recorrncia e a determinao de suas complexidades.

    Resumindo

  • PROJETO E ANLISE DE ALGORITMOS 47

    tCNICA DE ANlIsE DE AlgoRItmos

    ANLISE DE ALGORITMOS

    "A anlise de algoritmos uma disciplina de engenharia. Um engenheiro civil, por exemplo, tem mtodos e tcnicas para prever o comportamento de uma estrutura antes de construi-la. Da mesma forma, um projetista de algoritmos deve ser capaz de prever o comportamento de um algoritmo antes de implement-lo."

    Annimo

    Introduo

    A anlise de algoritmos um ramo da cincia da computao

    que estuda as tcnicas de projeto de algoritmos e os algoritmos de forma abstrata, sem estarem implementados em uma linguagem de programao em particular ou implementadas de algum modo. Ela se preocupa com os recursos necessrios para a execuo do algoritmo, tais como o tempo de execuo e o espao de armazenamento de dados.

    Neste captulo, apresentaremos algumas tcnicas muito teis para analisar a complexidade do pior caso de um algoritmo, envolvendo as principais estruturas de controle normalmente encontradas, bem como mostraremos alguns exemplos de aplicaes.

    Analisar Algoritmos

    Uma metodologia usada para realizar a complexidade de um

  • unidade 248

    algoritmo est baseada na sua estrutura (TOSCANI, 2001). Ela detm a complexidade do algoritmo, passo a passo, atravs das complexidades de suas componentes.

    Sero analisadas as complexidades de cada uma das principais estruturas algortmicas a seguir, estabelecendo equaes para elas.

    3. Atribuio: v w,

    4. Sequncia: S; T,

    5. Condicional: se b ento S seno T ou (se b ento S)6. Iterao definida (incondicional)

    para i de j at m faa S.7. Iterao indefinida ( condicional )

    enquanto b faa S.

    Complexidade de Algoritmos

    1. O tempo de execuo de um comando de atribuio, leitura ou de escrita pode ser considerado com O(1). Existem excees para as linguagens que permitem a chamada de funes em comandos de atribuio ou quando envolvem vetores de tamanho arbitrariamente grande.

    2. O tempo de execuo de uma sequncia de comandos determinado pelo maior tempo de execuo de qualquer comando da sequncia.

    3. O tempo de execuo de um comando de deciso dos comandos executados dentro do comando condicional, mais o tempo para avaliar a condio, que O(1).

    4. O tempo para executar um lao a soma do tempo de execuo do corpo do lao mais o tempo de avaliar a condio para determinao, multiplicando pelo nmero de iteraes do lao.

    5. Quando o programa possui procedimentos no recursivos, o tempo de execuo de cada procedimento deve ser computado separadamente um a um, iniciando com os procedimentos que no chamam outros procedimentos. A seguir, devem ser avaliados os procedimentos que chamam os procedimentos que no chamam outros procedimentos, usando os tempos dos procedimentos j avaliados. Este processo repetido at se chegar ao programa principal.

  • PROJETO E ANLISE DE ALGORITMOS 49

    6. Quando o programa possui procedimentos recursivos, para cada procedimento associada uma funo de complexidade f(n) e, em geral, a anlise desta funo envolve a soluo de uma relao de recorrncia.

    Complexidades de Atribuies

    A atribuio uma estrutura sintaticamente simples, cuja semntica depende do tipo de dado atribudo. A atribuio pode ser uma operao simples, como a atribuio de um valor a uma varivel, ou uma atribuio mais complexa, como a insero de um nodo num grafo, a atualizao de uma matriz, dentre outros.

    Exemplo: Considere as atribuies a seguir:7. Para as variveis inteiras i e j:

    i 0 {inicializao}

    j i {transferncia}

    Ambas tm complexidade constante: O(1).

    8. Para lista v de inteiros e varivel inteira m:m Max(v) {valor mximo}

    Esta atribuio envolve (sendo n o comprimento da lista em v).Determinar o mximo da lista v, com complexidade O(n);Transferir este valor, com complexidade O(1).Sua complexidade tem ordem linear: O(n) +O(1)=O(n),9. Para listas u, v e w;

    uv {transfere lista}

    w Reversa(v) {inverte lista}

    A atribuio uv transfere cada elemento da lista v com complexidade

    O(n) para uma lista v com comprimento n. A atribuio wReversa(v) envolve (lista v com comprimento n);

    Inverter a lista v com complexidade O(n). Transferir os elementos da lista invertida com complexidade O(n).Sua complexidade tem ordem O(n) +O(n) : O(n).

    Complexidade de Sequncias

    Essa estrutura tem a forma: S; T. A complexidade da sequncia a

    soma das complexidades componentes.

  • unidade 250

    Exemplo: Considere as sequncias a seguir:

    10. Para variveis inteiras n e m:n 0; m n

    Sua complexidade tem ordem 1 + 1: O(1).11. Para lista v de inteiros e varivel inteira i:i Max(v); i i + 1;

    Sua complexidade tem ordem n + 1: O(n).12. Para listas u, v e w: (as listas tm comprimento n)

    u v; w Reversa(v). (Lista invertida)

    Sua complexidade tem ordem n + n: O(n).Exemplo: Considere o trecho de algoritmov Reversa(n);

    w Ordene(v);

    Onde Reversa e Ordene tem complexidade O(n) e O(n2).O algoritmo tem complexidade de ordem n+n2, isto , O(n2).Exemplo: Dados algoritmos Prim(u) e Buscab(a,v), considere a

    sequncia:

    v Prim(u); Buscab(a,v);

    Vamos Supor que:

    Prim(u) d como sada a primeira metade da lista em u com comprimento n/2 e complexidade O(n) (n o comprimento da lista em u).

    Buscab(a,v) procura a na lista v, com complexidade O(log m), para lista v com comprimento m.

    O algoritmo composto tem complexidade de ordem n+log n/2, ou seja, O(n).

    Complexidades Condicionais

    A estrutura condicional pode apresentar-se de diversas formas, as mais usuais sendo as seguintes:

    Se b ento S seno Te

    Se b ento SAnlise destas formas:Vamos iniciar a anlise como a forma mais simples

    Estrutura Condicional: Se b ento S Exemplo: Considere as estruturas condicionais a seguir:

  • PROJETO E ANLISE DE ALGORITMOS 51

    13. Para varivel inteira i:Se i = 0 ento i i + 1;

    Esta estrutura condicional envolve:Determinar se o valor de i 0, sua complexidade O(1).Caso afirmativo, executar a atribuio i i + 1 com complexidade

    O(1).Sua complexidade total tem ordem constante O(1).1. Para lista v de inteiros e varivel inteira m;Se m = 0 ento m Max(v);

    Esta atribuio envolve (n comprimento da lista):Determinar se o valor de m 0, com O(1). Caso afirmativo, executar a atribuio m Max(v) com complexidade

    O(n).Sua complexidade no pior caso tem ordem O(n).1. Estrutura Condicional Se b ento S seno TExemplo: Considere as estruturas condicionais a seguir:2. Para variveis inteiras i e j

    Se i j ento i i + jseno j i + 1

    Esta estrutura condicional envolve:Determinar se os valores de i e j so diferentes com complexidade

    O(1). Caso afirmativo, executar a atribuio i i + j com complexidade O(1).

    Caso negativo, executar a atribuio j i + 1 com complexidade

    O(1). Sua complexidade tem ordem constante O(1). 1. Para listas u e v (inteiros)

    Se u = v, ento v Prim(u)

    seno u Ordene (v)

    Esta estrutura condicional envolve:Determinar se as listas u e v so iguais com complexidade O(n). Caso

    afirmativo, executar v Prim(u) com complexidade O(n) e (Prim(u) d como

    sada a primeira metade da lista( n/2 ). Caso negativo, executar u Ordene(v), usando um dos algoritmos

    de ordenao com complexidade O(n2).Sua complexidade total, no pior caso : O(n) +O(n) + O(n2)= O(n2).

    Complexidade de Iterao Definida

  • unidade 252

    A estrutura a ser trabalhada a iterao definida ou incondicional da

    forma:para i de j at m, faa S. Esta iterao executa S (m j +1) vezes com valores de i variando

    de j at m. Considerando-se que os valores de j e m no so alterados na execuo de S, o nmero de iteraes determinado por (m j +1).

    Exemplo: Considere as iteraes definidas a seguir:

    Para varivel inteira m: para i de 1 at 20, faa m m + 1

    Sua complexidade tem ordem constante 20 . 1, isto , O(20)=O(1)Para vetor A[1 .. n] de inteiros:

    para i de 1 at n faa A[i] 0

    Sua complexidade do tipo n . 1, isto , O(n).Para vetor A[1 .. n] de inteiros:

    para i de 1 at n, faa A[i] A[i] + 1

    Sua complexidade n . 1: O(n).Para varivel real s e o vetor R[1..n] de reais:

    para i de 1 at n, faa s s + R[i]

    Sua complexidade n . 1: O(n).Para varivel real t e matriz quadrada Q[1..n,1..n] de reais:

    para i de 1 at n, faa t t + Q[i,i]

    Sua complexidade O(n).

    1. Complexidade de Iterao Indefinida

    Esses tipos de laos no so to fceis de analisar comparados com os laos para. O primeiro fator a ser observado a regra de parada do lao. Se a regra de parada envolve uma varivel inteira e uma constante, o lao pode ser analisado de maneira semelhante ao lao para. Quando o controle envolve duas variveis inteiras, a anlise padro consiste em expressar o comportamento como uma varivel nica a ser decrementada.

    Iteraes indefinidas ou condicionais podem tomar vrias formas,

    dentre elas ENQUANTO e REPITA.

    Enquanto b faa SExemplo: Considere os trechos de algoritmos a seguir.Para varivel inteira i:i 0

  • PROJETO E ANLISE DE ALGORITMOS 53

    Enquanto i 10 faa:

    i i + 1

    Sua complexidade tem ordem constante 10.1, isto , O(10).Inicializao de vetor A [1..n] de inteiros:

    i 0

    Enquanto i n, faa:

    i i + 1;

    A[i] 0;

    Sua complexidade tem ordem n . 1: O(n).Atualizao de vetor A [1..n] de inteiros:

    i n

    Enquanto i > 0 faaA[i] A[i] + 1;

    i i 1;

    Sua complexidade tem ordem O(n).OBS: Esses tipos de laos no so fceis de analisar como os laos

    para.Primeiro, o fator a regra de parada, o qual envolve varivel inteira e

    uma constante e pode ser analisado semelhante o para.Segundo, quando envolvem duas variveis inteiras, a anlise consiste

    em expressar o comportamento como uma varivel nica a ser decrementadaAnalisar um algoritmo prever o que o algoritmo ir precisar. s

    vezes o hardware importante, mas o que acontece com frequncia medir o tempo que ir demorar. O tempo de execuo de um algoritmo depende geralmente do tamanho de sua entrada. Portanto, a anlise de algoritmo est baseada no tamanho de sua entrada para compar-lo com outros algoritmos e ter noo de quanto tempo ele vai demorar.

    Exemplo: Analisar o seguinte algoritmo:1. para i 1 at n faa

    2. para 1 at i faa

    3. imprima i x j x n4. fim para

    5. fim para

    Para medir o custo do algoritmo, nossa anlise consistir em ver quantas vezes cada passo executado. Mediremos o custo de cada linha (cada passo a ser executado), sempre em funo de n. Vamos analisar o

    algoritmo.

  • unidade 254

    Linha 1 Ser executada n+1 vezes

    Linha 2 Ser executado n xni=1 + n vezesLinha 3 Ser executada n xni=1 Linha 4 No tem custo.

    O lao da linha 1 voltar para si mesmo n vezes, isto , testar novamente sua condicional e incrementar um. No final ele ter que testar

    novamente para dizer que j passou de n. Por isso, ele ser executado n + 1 vez, ao invs de simplesmente n.

    O lao da linha 2 ser executado um nmero de vezes que a varivel i, onde i ir de 1 a n. Portanto, ele ser executado o nmero de vezes que equivale a soma de 1 a n mais n.

    O lao da linha 3 ser executado o mesmo nmero que a linha 2, mas sem n.

    Exemplo : Faa a anlise para o seguinte trecho de programa:ler(n); T1(n)= O(1)para i de 1 at n faapara j de 1 at n faa T2(n)=O(n

    2) A[i,j] 0;

    para i de 1 at n faa T3(n)=O(n) A[i,j] 1;

    T(n) = T1(n) + T2(n) + T3(n)T(n) = O(1) + O(n2) + O(n) = O(n2)

    Exemplo: Faa a anlise do trecho do programa:Se A[i,i] = 0, ento:

    para i de 1 at n, faa: para j de 1 at n , faa f(n) = n2 A[i,j] 0;

    Seno: para i de 1 at n ,faa g(n) = n A[i,i] 1;

    T(n) = f(n) + g(n) = O(max(f(n),g(n))T(n) = O(max(n2, n)) = O(n2) Exemplo: FatorialLer(n);

    i 2;

    Desafio:Qual o tempo de execuo total para contar de 1 a n em binrio, se o tempo necessrio para somar 1 ao nmero i proporcional ao nmero de bits na representao binria de i que devem ser alterados para representar i+1?

  • PROJETO E ANLISE DE ALGORITMOS 55

    Fat 1;

    enquanto i n, faa:

    Fat Fat * i;

    i i +1;

    escreva Fat;Exemplo: Verificar se um inteiro n primo

    Primo verdade

    i 2

    enquanto i * i n, faa:

    Se n mod i = 0, ento: primo falsidade

    goto 44 seno: i i +1;

    44 fim

    Exemplo: Considere o algoritmo para ordenar n elementos de um conjunto A.

    Para i de 1 at n-1, faa: min i;

    para j de i + 1 at n, faa: Se A[j] < A[min], ento:

    min j;

    temp A[min];

    A[min] A[i];

    A[i] temp;

    Exemplo: Algoritmos para avaliao de polinmios de grau n da forma:Pn(x) = anx

    n + an-1xn-1 + ... +a1x + a

    E so comparadas as suas complexidades.Algoritmo 1 Ler (n, an,, an-1-,,..., a0,,x} P a0 y x

    para i de 1 at n-1, faa: P P + ai * y;

    yy + x;

    P P + an * y;

    Cada execuo de lao implica em dois produtos e uma soma, 3

  • unidade 256

    operaes de tempo constante. Como este executado (n-1), Portanto o algoritmo 1 tem complexidade; T(n) = (n-1)[O(1)+O(1) +O(1)] = O(n)

    Algoritmo 2 Ler (n, an,, an+1-,,..., a1, a0,x} P a0 para i de 1 at n, faa: P P + ai * x

    i;O lao executado n vezes e a cada execuo (2 + i) as operaes

    so realizadas,portanto, Algoritmo 3 Ler (n, an,, an-1-,,..., a1, a0,x} P an; para i de n-1 at 0, faa: P ai + x * P;

    Neste caso, cada execuo do lao realiza uma soma e um produto, ou seja, duas operaes de tempo de execuo. Assim T(n) = n. O(1) = O(n)

    Este exemplo mostra claramente a importncia de algoritmos eficientes.

    Para valores grandes, digamos n = 10000, um nmero pequeno de operaes seriam realizadas (108 ou 104)

    Algoritmos de Menor Complexidade para OrdenaoHeapsort O(n log n)

    Mergesort possvel provar que este limitante o melhor possvel, isto , estes

    algoritmos so timos.

    Teorema: Dados um vetor A [1],..., A [n] e um valor x, verificar se x

    elemento do vetor.Qual o melhor algoritmo? Depende! Dados ordenados ou no?Dados ordenados:Pesquisa binria com complexidade de O(log n).Dados no ordenados:Pesquisa sequencial com complexidade de O(n).

    Desafio:Mostre que qualquer algoritmo de ordenao baseado em comparaes pode ser transformado em um mtodo estvel sem afetar o tempo de execuo assinttico do algoritmo.

  • PROJETO E ANLISE DE ALGORITMOS 57

    A complexidade total ser a soma das complexidades da ordenao com:

    O(n log n) + O(log n) = O(n log n)

    Pesquisa sequencial melhor.Variante: H m elementos x a serem testados.

    Dados no ordenados:Pesquisa sequencial O(m n)

    Ordenar + pesquisa binriaO(n log n) + O(m log n) = O((n+m) log n)

    Hiptese: m nAgora, a segunda alternativa a mais eficiente.

    O(n log n), O(n2)

    Exerccio

    1. Quanto tempo (em nmero de operaes) gasto para executar o seguinte algoritmo?

    para i1 at n-1, faa:

    Para k1 at n, faa:

    S[i,k] S[i,k] S[i,k]*S[i,i]/S[i,i]

    2. Determine o tempo consumido na execuo do algoritmo abaixo:S0

    para i1 at n, faa:

    SS + A[i]

    mS/n

    k1

    para i2 at n, faa:

    se (A[i] m)/2

  • unidade 258

    Lao1(n)

    s0

    para i1 at n, faa:

    ss + 1

    Lao2(n),

    t1

    para t1 at 2n, faa:

    tt*i

    Lao3(n);

    t1

    para t1 at n2, faa:

    tt*i

    Lao 4(n);

    s0

    para i1 at 2n, faa:

    para j1 at i, faa:

    ss +i

    Lao5(n);

    s0

    para i1 at n2 , faa:

    para j1 at i, faa:

    ss +i

    Figura 1.8 Algoritmo.

    3. Fornea uma estimativa em notao O e em funo de n para o mtodo do lao1, dado no algoritmo da figura 1.8.

    4. Fornea uma anlise similar para o mtodo lao 2 do algoritmo da figura 1.8.

    5. Fornea uma anlise similar para o mtodo lao 3 do algoritmo da figura 1.8.

    6. Fornea uma anlise similar para o mtodo lao 4 do algoritmo da figura 1.8.

    7. Fornea uma anlise similar para o mtodo lao 5 do algoritmo da figura

    1.8.8. Faa a anlise do algoritmo de ordenao por insero1 Ordenao por insero (A, n)2 Para j2 at n, faa:

  • PROJETO E ANLISE DE ALGORITMOS 59

    3 xA[j]

    4 ij 1

    5 enquanto i > 0 e A[i] > x, faa:

    6 A[i + 1] A[i]

    7 ii 1

    8 A[i + 1] x

  • unidade 160

  • PROJETO E ANLISE DE ALGORITMOS 61

    UNIDADE 3tcnica de Projeto de

    Algoritmos

    Esta unidade dedicada a demonstrar as principais tcnicas para elaborao de algoritmos com bons desempenhos e, de acordo com a natureza do problema, propiciar ao leitor decidir qual estratgia utilizar diante de certas situaes especficas de resoluo. Exemplificaremos as tcnicas

    com alguns dos principais algoritmos relacionados a cada estratgia.

    Resumindo

  • PROJETO E ANLISE DE ALGORITMOS 63

    tCNICA DE PRojEto DE AlgoRItmos

    INTRODUO

    "Ter uma base slida de conhecimento das tcnicas de projeto de algoritmos uma caracterstica que separa os programadores verdadeiramente qualificados dos novatos. Com a moderna tecnologia da computao, voc pode realizar algumas tarefas sem saber muito sobre algoritmos, mas com uma boa experincia em algoritmos, voc pode fazer muito, muito mais."

    Cormen, Leiserson, Rivers, Stein, "Introduction to Algorithms"

    Ao se projetar um bom algoritmo, deve-se levar em conta uma estratgia que possibilite obter uma boa complexidade, tanto temporal quanto espacial. Diante disso, tcnicas de projeto de algoritmos so conjuntos de tcnicas que compreendem tantos os mtodos de codificao de algoritmos

    quanto a forma de determinar sua complexidade e que propiciam a produo de algoritmos fortes e levando em considerao a forma pela qual determinado algoritmo chega a soluo desejada.

    FORA BRUTA

    a mais simples estratgia de projeto de algoritmos. Soluo direta para resolver um problema, usualmente baseada no prprio enunciado do problema e nas definies dos conceitos envolvidos. Consiste em enumerar

    todos os possveis candidatos de uma soluo e verificar se cada um satisfaz

    o problema. considerada por muitos a tcnica de projeto mais fcil de aplicar.

  • unidade 364

    Apesar desta tcnica, raramente, gerar algoritmos eficientes,

    uma importante tcnica para projeto de algoritmos, visto que aplicvel a uma ampla variedade de problemas, podendo ser empregada em diversas situaes comuns, porm importantes. Por exemplo, encontrar o maior elemento de uma lista, somar n nmeros, os divisores de um nmero natural n, etc.

    Assim, uma alternativa vlida quando se deseja resolver um problema pequeno atravs de um algoritmo simples e direto. A fora bruta tipicamente usada em problemas cujo tamanho limitado ou quando h uma heurstica usada para reduzir o conjunto de candidatos para um espao aceitvel.

    Para alguns problemas, a tcnica de fora bruta gera algoritmos razoveis, prticos e sem limitaes no tamanho da instncia, como por exemplo, o problema da multiplicao de matrizes, casamento de padres, etc.

    O esforo para projetar algoritmos mais eficientes pode no compensar

    o trabalho, quando o tamanho das instncias ou a quantidade de problemas a resolver pequeno, ou seja, se obtm uma velocidade aceitvel.

    Tambm pode ser utilizado quando a simplicidade da implementao mais importante que a velocidade de execuo como nos casos de aplicaes crticas em que os erros de algoritmo possuem srias consequncias.

    DIVIDIR- E-CONQUISTAR

    Introduo

    Esta tcnica consiste em decompor instncias a serem resolvidas em um nmero de subinstncias menores do mesmo problema, resolvendo sucessivamente e independentemente cada uma delas, combinando-as para obter a soluo do problema original.

    Apresentaremos, a seguir, um exemplo da aplicao desta tcnica de projeto de algoritmos aplicada ordenao.

    Ordenao

    Seja T[1..n] um vetor de n elementos. Deseja-se ordenar esses

    elementos em ordem crescente.

  • PROJETO E ANLISE DE ALGORITMOS 65

    Usando a tcnica dividir-e-conquistar, devemos dividir T em duas partes iguais ou de tamanhos semelhantes, ordenar cada uma delas recursivamente, e ento fazer um merge das solues respeitando a ordenao. O algoritmo a seguir, de nome mergesort verifica o tamanho da

    instncia a ser ordenada, caso ela tenha tamanho inferior a c, uma constante determinada experimentalmente, o algoritmo ordena com o uso do algoritmo de ordenao por insero; caso contrrio, o vetor a ser ordenado dividido em duas partes iguais e o procedimento mergesort chamado recursivamente com cada uma das metades U e V do vetor original T. O procedimento merge

    invocado quando se dispe dos dois vetores ordenados U e V, gerando o

    vetor final ordenado pela mesclagem(merge) de U e V.

    Algoritmo Mergesort 1 proc mergesort(T[1..n])

    2 incio 3 se n

  • unidade 366

    Vetor aps retorno das duas ordenaes recursivas

    Vetor aps o merge

    Correo:

    Pelo teorema de Jean Pierre basta olhar, esse algoritmo est correto, ou seja, dado um vetor T no ordenado, ao final do algoritmo, teremos um

    vetor T ordenado. Mais formalmente, para instncia de tamanho menor ou igual a c, as

    mesmas so ordenadas por um algoritmo j conhecido e correto. Assumimos que o algoritmo ordena corretamente um vetor de tamanho

    tj, para i

  • PROJETO E ANLISE DE ALGORITMOS 67

    Neste caso aplicado o caso 2 do mtodo mestre. Ento, T(n) (n.logn) O mergesort superior ao algoritmo de ordenao por insero

    que lhe serve de base e considerado algoritmo timo juntamente com o heapsort. No entanto, o mergesort gasta muita memria intermediria, enquanto o heapsort usa apenas o vetor original.

    Outra questo interessante relativa diviso do vetor. Ser que faz alguma diferena dividir ao meio ou dividir em outras propores? Supondo que o algoritmo seja como abaixo:

    1 proc mergesort2(T[1..n]) 2 incio 3 se n

  • unidade 368

    representao destes nmeros por ponteiro flutuante no recomendvel,

    a menos que se esteja interessado, exclusivamente, na ordem de magnitude e com os algarismos mais significativos do resultado. Se o mesmo tiver de

    ser calculado de forma exata com todos os algarismos, h a necessidade de implementar operaes aritmticas no software.

    Embora uma multiplicao elementar raramente leve mais tempo do que uma adio na maioria dos computadores, isto est longe de ser verdade quando os operandos envolvidos so muito grandes. H algoritmos que somam dois inteiros em tempo linear, por outro lado, o algoritmo clssico e a multiplicao a la russe leva um tempo quadrtico para multiplicar estes mesmos operandos. Como melhorar? Seja u e v dois inteiros com n dgitos decimais a serem multiplicados.

    Utilizando a estratgia de Dividir-e-Conquistar, possvel separar cada um desses operandos em duas partes do mesmo tamanho, o mais prximo possvel: u = 10sw + x; v = 10sy + z, onde 0x

  • PROJETO E ANLISE DE ALGORITMOS 69

    8 y v div 10s ; z v mod 10s 9 retornar mult (w,y) 102s + (mult(w,z) + mult(x,y)) 10s + mult (x,z)

    Seja T(n) o tempo, no pior caso, necessrio para o algoritmo multiplicar dois inteiros de n dgitos, h algoritmos conhecidos que executam em tempo linear divises e multiplicaes por 102s e 10s, bem como as adies. O mesmo ocorre para as operaes de mdulo, uma vez que estas so equivalentes a uma diviso, uma multiplicao e uma subtrao de inteiros. A ltima parte do algoritmo consiste em quatro chamadas recursivas, cada uma delas serve para multiplicar dois inteiros cujo tamanho aproximadamente n/2. Ento, T(n) 3T(n/2) + T(n/2) + (n).

    Esta equao torna-se T(n) 4T(n/2) + (n), quando n uma potncia de 2. Pode-se, facilmente, verificar que a complexidade deste algoritmo

    O(n2). O artifcio que permite acelerar o processo consiste em executar os

    clculos wy,wz + xy, e xz em menos de quatro meias multiplicaes, mesmo

    que seja necessrio ter de fazer mais adies. Isto sensvel, pois a adio muito mais rpida do que a multiplicao (que quadrtica) quando os operandos so grandes. Considere o produto:

    r = (w + x)( y+ z) = wy + (wz + xy )+ xz.

    Depois de apenas uma multiplicao, incluindo os trs termos

    necessrios para calcular uv, duas outras multiplicaes so necessrias para isolar esses termos. Isso sugere que se deve substituir a ltima parte do algoritmo por:

    r mult (w + x, y + z)

    p mult (w,y); q mult (x,z)

    retorna 102sp+10s(rpq) + q Seja T(n) o tempo necessrio pelo algoritmo modificado para

    multiplicar dois inteiros no mximo de tamanho n. Sabendo-se que w + x e y

    + z pode ter at 1 + n/2 dgitos, supe-se que exista constante c R+ e n0 N, tal que:

    T(n) T (n/2) + T(n/2) + T (1+n/2) + cn para cada n n0 . A equao equivale a T(n) 3T(n/2) + O(n) .

    Assumindo n, sendo potncia de 2, pode-se considerar que:

    T(n) = 3T(n/2) + cnAplicando o mtodo mestre, nlogb

    a = nlog23 e f(n)=(n), da f(n)

    O(nlog23). Assim, aplica-se o caso 1 e o algoritmo (nlog2

    3).

  • unidade 370

    Desta forma, o algoritmo de multiplicao de inteiros de n dgitos tem complexidade O(n1,59), para algum valor n > n0, que melhor do que a do algoritmo clssico O(n2).

    Entretanto, as constantes escondidas so tantas que o algoritmo s se torna interessante na prtica quando n bastante grande. Uma boa implementao provavelmente no usar a base 10, mas de preferncia a

    maior base na qual o hardware pode multiplicar diretamente dois dgitos.

    Exemplo: Deseja-se multiplicar u=2.345 e v=6.789. A decomposio inicial

    dos operandos dada por n=4, s=2, w=23, x=45, y=67, e z=89. Ns

    obtemos sucessivamente p=23X67=1541, q=45X89=4.005 e r=(23+45)

    (67+89)=68x156=10.608. Finalmente, o produto desejado uv obtido,

    calculando: 1.541x104+(10.6081.5414.005)x102+ 4.005=15.410.000+506.200+

    405=15.920.205.

    claro que este exemplo muito pequeno e seria mais rpido usar o algoritmo clssico de multiplicao.

    A multiplicao no a nica operao interessante que envolve inteiros grandes. Diviso de inteiros, operaes, o mdulo e o clculo da parte inteira da raiz quadrada podem ser executados em um tempo de mesma ordem que o necessrio para a multiplicao. Um outro ponto importante que operaes com inteiros grandes so de suma importncia para a criptologia.

    PROGRAMAO DINMICA

    Introduo

    Programao Dinmica resolve problemas combinando as solues dos subproblemas.

    Programao refere-se a um mtodo tabular, no programao no computador. A tcnica de dividir-para-conquistar particiona o problema em subproblemas independentes, resolve-os recursivamente e ento combina suas solues para resolver o problema original. A programao dinmica, por sua vez, aplicvel quando os subproblemas no so independentes, havendo assim a necessidade de uma tabela para armazenamento dos resultados a serem compartilhados e evitar clculos repetidos.

    A programao dinmica pode ser dividida em quatro passos: 1. Caracterizao da estrutura de uma soluo tima;

    Saiba MaisA tcnica de diviso-e-conquista parte do folclore do projeto de estruturas de dados e algortimos. O mtodo mestre para resolver recorrncias de diviso-e-conquista tem suas origens rastreadas em um artigo de Bentley, Haken e Saxe. O algoritmo de diviso-e-conquista para a multiplicao de inteiros grandes em tempo O (n1,59) normalmente atribudo aos russos Karatsuba e Ofman. O algortimo conhecido como assintoticamente mais rpido para multiplicar dois nmeros de n dgitos executa em tempo O (n log n log log n).

  • PROJETO E ANLISE DE ALGORITMOS 71

    2. Definir recursivamente o valor de uma soluo tima; 3. Clculo do valor de uma soluo tima; 4. Construo de uma soluo tima a partir da informao

    computada. Os passos de 1 a 3 formam a base de uma soluo por programao

    dinmica para um problema. O passo 4 necessrio quando necessitamos informao adicional para facilitar a computao do passo 3.

    Multiplicao de Diversas Matrizes

    Seja A1A2...An uma sequncia de n matrizes que devem ser multiplicadas. H diversas formas de se obter o resultado desejado. Para maior clareza, apresentamos um exemplo:

    Seja A1 uma matriz 13x5, A2 5x89, A3 89x3 e A4 3x34. Para obter M=((A1A2)A3)A4), calculamos sucessivamente

    A1A2 - 5785 produtos (A1A2)A3 - 3471 produtos ((A1A2)A3)A4) - 1326 produtos para um total de 10582 produtos escalares. H 5 maneiras diferentes

    de se multiplicar essas matrizes e obter o mesmo resultado final:

    ((AB)C)D - 10582 (AB)(CD) 54201 (A(BC)D) - 2856 A((BC)D) - 4055 A(B(CD)) 26418 O modo mais eficiente cerca de 19 vezes mais rpido que o menos

    eficiente.

    Os problemas consistem em determinar a forma mais eficiente de

    parentizao usando um algoritmo adequado. Para obter a melhor maneira de calcular o produto, podemos usar

    o algoritmo da fora bruta e verificar todas as possveis formas. Seja T(n) o

    nmero de modos de parentizao diferentes em um produto de n matrizes. Fazendo um corte entre a i-sima e a (i+1)-sima matrizes do produto, ento:

    M = (M1M2...Mi)(Mi+1Mi+2...Mn) Agora, h T(i) maneiras de parentizar o termo do lado esquerdo e

    T(n-i) maneiras de parentizar o termo do lado direito. H T(i)T(n-i) maneiras de parentizar T(n), e i pode assumir valores de 1 a n-1, o que nos d a

  • unidade 372

    seguinte recorrncia:

    A condio inicial T(1)=1. A partir da podemos levantar os seguintes valores:

    Os valores de T(n) so chamados nmeros de Catalo. T(n) (4n/n2) o que pode ser verificado provando que

    e que

    No entanto, um algoritmo (4n/n2) impraticvel para valores n grandes.

    Uma abordagem seria o uso de algoritmos gulosos. No entanto, dentre os algoritmos gulosos bvios, no permitir a obteno de soluo tima.

    Tentaremos verificar se o princpio de otimizao pode ser empregado

    e assim a programao dinmica resolver tal problema.

    Passo 1: A estrutura de um parentizao tima

    O primeiro passo do paradigma da programao dinmica caracterizar a estrutura de uma soluo tima. Adotaremos a notao Ai..j para a matriz que resulta da avaliao do produto AiAi+1...Aj.

    Para obter a soluo do problema proposto, devemos obter A1..n, que pode ser obtido pelo produto de A1..kAk+1..n cujo custo timo obtido pela soma do custo de A1..k com Ak+1..n mais o custo do produto delas. A subcadeia A1..k deve ter parentizao tima, do contrrio poderamos substitu-la por outra com custo menor que o timo, o que uma contradio.

  • PROJETO E ANLISE DE ALGORITMOS 73

    Logo, uma soluo tima para uma instncia do problema contm

    solues timas para as subinstncias do mesmo problema, o que permite o emprego da programao dinmica.

    Passo 2: Uma soluo tima recursiva

    Deve-se definir uma expresso recursiva para a soluo tima em

    funo das subinstncias.Ser usada uma tabela mij 1 i j n para armazenar a soluo

    tima para Mi.Mi+1. O valor m[i,i]=0, pois Ai..i = Ai, no havendo necessidade de qualquer clculo.

    Para i

  • unidade 374

    1 proc Parentizar_Cadeia_Matriz(p:vetor[0..n];s:vetor[1..n,1..n])

    2 {p armazena as dimenses das n matrizes }

    3 para i:=1 at n, faa: 4 m[i,i]:=0;

    5 para d:=2 at n, faa:6 para i:=1 at n-d+1, faa:7 j:=i+d-1;

    8 m[i,j ]: = min i k< j { m[i,k] + m[ k,j] + p[i1]p[k]p[j] }

    9 s[i,j]:= k , tq m[i,j] = m[i,k]+m[k,j]+p[i-1]p[k]p[j]

    O algoritmo computa, inicialmente, m[i,i] 0, para i=1,2,...,n (custo

    mnimo para cadeias de comprimento 1). Ento, usa a recorrncia para calcular

    m[i,i+1], para i=1,2,...,n-1 ( custo mnimo para cadeias de comprimento d=2) e

    assim por diante at d=n. Em cada passo, o custo m[i,j] depende apenas dos

    valores m[i,k] e m[k+1,j] que j foram calculados.

    A complexidade do algoritmo pode ser determinada, observando que h dois laos (linhas 5 e 6) executando O(n2) vezes as linhas 7 e 8. A linha 8 tem complexidade O(n) no pior caso, o que conduz a uma complexidade O(n3) para o algoritmo todo.

    Passo 4: Construindo uma soluo tima

    O algoritmo apresentado determina o nmero timo de multiplicaes escalares para calcular o produto de uma cadeia de matrizes, mas no mostra diretamente como multiplicar as matrizes. O passo 4 constri uma soluo tima a partir da informao obtida. A tabela s[1..n,1..n] determina a melhor

    forma de multiplicar as matrizes atravs do valor k usado na melhor partio da cadeia. O seguinte algoritmo recursivo calcula o produto da cadeia de matrizes de forma tima:

    A chamada inicial deve ser Produto_Cadeia_Matrizes(A,s,1,n).

    O Problema de Caminho Mnimo

    Utiliza-se algoritmo que faz uso de tcnicas de programao dinmica, denominado algoritmo de Dijkstra, para determinao de caminho mnimo de um n para todos os demais ns de um grafo orientado com arestas

    Desafio:Dado um conjunto P de n times de futebol, projete um algoritmo para organizar um torneio round-robin, em que c