Desmistificando algoritmos thomas cormen

Desmistificando algoritmos Thomas Cormen

Visit to download the full and correct content document: https://ebookmass.com/product/desmistificando-algoritmos-thomas-cormen/

Desmistificando Algoritmos

© 2014, Elsevier Editora Ltda.

Todos os direitos reservados e protegidos pela Lei n° 9.610, de 19/02/1998. Nenhuma parte deste livro, sem autorização prévia por escrito da editora, poderá ser reproduzida ou transmitida sejam quais forem os meios empregados: eletrônicos, mecânicos, fotográficos, gravação ou quaisquer outros.

© 2013, Massachusetts Institute of Technology. All rights reserved.

Copidesque: Ivone Teixeira

Revisão: Tania Heglacy Moreira de Almeida

Editoração Eletrônica: Thomson Digital

Elsevier Editora Ltda.

Conhecimento sem Fronteiras

Rua Sete de Setembro, 111 – 16° andar 20050-006 – Centro – Rio de Janeiro – RJ – Brasil

Rua Quintana, 753 – 8° andar 04569-011 – Brooklin – São Paulo – SP

Serviço de Atendimento ao Cliente 0800-0265340 atendimento1@elsevier.com

ISBN original 978-0-262-51880-2

ISBN 978-85-352-7177-5

ISBN digital 978-85-352-7179-9

Nota: Muito zelo e técnica foram empregados na edição desta obra. No entanto, podem ocorrer erros de digitação, impressão ou dúvida conceitual. Em qualquer das hipóteses, solicitamos a comunicação ao nosso Serviço de Atendimento ao Cliente, para que possamos esclarecer ou encaminhar a questão. Nem a editora nem o autor assumem qualquer responsabilidade por eventuais danos ou perdas a pessoas ou bens, originados do uso desta publicação.

CIP-BRASIL. CATALOGAÇÃO NA PUBLICAÇÃO SINDICATO NACIONAL DOS EDITORES DE LIVROS, RJ

C833d

Cormen, Thomas H.

Desmistificando algoritmos / Thomas H. Cormen ; tradução Arlete Simille Marques. - 1. ed. - Rio de Janeiro : Elsevier, 2014. 23 cm.

Tradução de: Algorithms unlocked

ISBN 978-85-352- 7177-5

1. Algoritmos. 2. Estruturas de dados (Computação). 3. Programação (Computadores). I. Título.

13-05070

CDD: 005.1

CDU: 004.42

Em memória da minha amada mãe, Renee Cormen.

Como os computadores resolvem problemas? Como o seu pequenino GPS consegue encontrar, entre gazilhões de possíveis rotas, o caminho mais rápido para o seu destino e fazer isso em meros segundos? Quando você compra algo pela Internet, como o número do seu cartão de crédito é protegido contra alguém que o intercepta? A resposta a essas perguntas e a uma tonelada de outras é algoritmos. Redigi este livro para revelar a você o mistério dos algoritmos.

Sou coautor do livro didático sobre algoritmos Introduction to Algorithms. É um livro maravilhoso (é claro que a minha opinião é preconceituosa), mas às vezes muito técnico.

Este livro não é Introduction to Algorithms. Não é nem mesmo um livro didático. Não se aprofunda nem se expande muito na área de algoritmos de computador, não ensina técnicas minuciosas para projetar algoritmos de computador e não contém absolutamente nenhum problema ou exercício para o leitor resolver.

Então, o que é este livro? É um lugar para você começar se:

• estiver interessado em saber como os computadores resolvem problemas,

• se quiser saber como avaliar a qualidade dessas soluções,

• gostaria de ver como os problemas em computação e as abordagens para resolvê-los estão relacionados com o mundo que não é do computador,

• souber um pouco de matemática e

• nunca escreveu um programa de computador (embora não fará mal se já tiver escrito algum).

Alguns livros sobre algoritmos de computador são conceituais, com poucos detalhes técnicos. Alguns estão repletos de precisão técnica. Alguns estão no meio desses dois. Cada tipo de livro tem seu lugar. Eu colocaria este livro na categoria intermediária. Sim, tem um pouco de matemática e, às vezes, torna-se um pouco preciso, porém eu evitei me aprofundar em detalhes (exceto talvez no final do livro, quando não consegui mais me controlar).

Eu imagino este livro como se fosse a entrada para uma refeição. Suponha que você vá a um restaurante italiano e peça uma entrada, adiando um pouco a decisão do prato que pedirá depois. A entrada chegou, você a come. Talvez não tenha gostado dela e decidiu não pedir nada mais. Quem sabe tenha gostado, mas é muito nutritiva e você achou que não precisa pedir mais nada. Ou, talvez, você tenha gostado da entrada, não achou que era muito nutritiva e está esperando ansiosamente o prato principal. Ao pensar neste livro como uma entrada para uma refeição, espero um dos dois últimos resultados: você lê o livro, fica satisfeito e acha que não precisa se aprofundar mais no mundo dos algoritmos ou você gostou tanto do que leu que quer aprender mais. Cada capítulo termina com uma seção intitulada “O que mais ler?”, que o guiará a livros e artigos que se aprofundam nos tópicos apresentados.

O que você aprenderá com este livro?

Não sei dizer o que você aprenderá com este livro. Eis o que eu pretendo que você aprenda com este livro:

• O que são algoritmos de computador, um modo de descrevê-los e como avaliá-los.

• Modos simples de procurar informações em um computador.

• Métodos para rearranjar informações em um computador, de modo que esteja em uma ordem prescrita (denominamos essa tarefa “ordenação”).

• Como resolver problemas básicos que podemos modelar em um computador com uma estrutura matemática conhecida como “grafo”. Entre muitas aplicações, grafos são ótimos para modelar redes rodoviárias (quais são as estradas que entram e saem de cruzamentos e quais são os comprimentos dessas estradas?), dependências entre tarefas (qual tarefa deve preceder quais outras tarefas?), relações financeiras (quais são as taxas de câmbio entre todas as moedas do mundo?) ou interações entre pessoas (quem conhece quem, quem odeia quem, qual ator apareceu em um filme com qual outro ator?).

• Como resolver problemas que fazem perguntas sobre cadeias de caracteres de texto. Alguns desses problemas têm aplicações em áreas como biologia, na qual os caracteres representam moléculas de base e as cadeias de caracteres representam as estruturas de DNA.

• Os princípios básicos que fundamentam a criptografia. Mesmo que você nunca tenha criptografado uma mensagem, o seu computador provavelmente criptografou (por exemplo, quando você compra mercadorias on-line).

• Ideias fundamentais de compressão de dados, que vão bem além de “f u cn rd ths u cn gt a gd jb n gd pay”.

• Que alguns problemas são difíceis de resolver em um computador em qualquer quantidade de tempo razoável ou, no mínimo, que ninguém conseguiu descobrir como fazê-lo.

O que você já precisa saber para entender o material deste livro?

Como eu disse antes, há um pouco de matemática neste livro. Se a matemática o assusta, você pode tentar saltá-la ou tentar um livro menos técnico. Porém, eu fiz o possível para tornar a matemática acessível.

Não dou por certo que você já tenha escrito ou até mesmo lido um programa de computador. Se você puder seguir instruções no formato de descrição, conseguirá entender como eu expresso as etapas que, juntas, formam um algoritmo. Se você entender a seguinte anedota, já está a meio caminho:

Você sabe a do cientista de computador que ficou preso no chuveiro? Ele1 estava lavando os cabelos e seguindo as instruções na embalagem do xampu. Ele leu: “Faça espuma. Enxague. Repita.”

1Ou ela. Dada a infeliz razão de gênero na ciência de computadores, a maior probabilidade é que seja ele.

Usei um estilo de escrever razoavelmente informal, esperando que uma abordagem pessoal o ajudará tornando o material acessível. Alguns capítulos dependem de material em capítulos anteriores, mas tais dependências são poucas. Alguns capítulos começam de maneira não técnica e tornam-se progressivamente mais técnicos. Mesmo que você ache que eu estou passando por cima da sua cabeça em um capítulo, provavelmente se beneficiará de ler, no mínimo, o início do próximo capítulo.

Comunique os erros

Se você encontrar um erro neste livro, favor comunicar por meio do endereço unlocked@mit.edu.

Agradecimentos

Grande parte do material deste livro foi retirado de Introduction to Algorithms e, portanto, devo muito aos meus coautores, Charles Leiserson, Ron Rivest e Cliff Stein. Você verá que em todo este livro eu me referi (leia: eu inseri) a Introduction to Algorithms, conhecido mais amplamente pelas iniciais CLRS dos quatro autores. Escrever este livro sozinho me fez perceber o quanto eu sinto falta da colaboração de Charles, Ron e Cliff. E também aproveito para agradecer a todos a quem eu agradeci no prefácio do CLRS.

Também usei material de cursos que lecionei em Dartmouth, especialmente Ciência de Computadores 1, 5 e 25. Agradeço a meus alunos por me deixarem perceber, por meio de suas perguntas perspicazes, quais abordagens pedagógicas funcionavam e, pelo seu silêncio de pedra, quais não funcionavam.

Este livro deve sua existência a uma sugestão de Ada Brunstein, que foi nossa editora na MIT Press quando preparamos a terceira edição de CLRS. Ada seguiu em frente e Jim DeWolf ocupou o lugar dela. Originalmente, este livro estava programado para ser parte da série “Essential Knowledge” da MIT Press, porém a editora achou que era muito técnico para a série (imagine só — eu escrevi um livro demasiadamente técnico para a MIT!). Jim tratou dessa situação potencialmente incômoda permitindo que eu escrevesse o livro que queria em vez do livro que a MIT Press achava que eu estava escrevendo. Agradeço também o apoio de Ellen Faran e Gita Devi Manaktala, da MIT Press.

Julie Sussman, PPA2, foi nossa revisora técnica para a segunda e terceira edições de CLRS e, mais uma vez, adorei tê-la como editora deste livro. Melhor. Editora. Técnica. Que já existiu. Ela permitiu que eu me safasse com nada. Eis aqui uma prova, na forma de um e-mail que Julie me enviou sobre um primeiro rascunho do Capítulo 5:

Prezado Sr. Cormen, Autoridades apreenderam um capítulo que escapou e que estava escondido no seu livro. Não conseguimos determinar de qual livro ele escapou, mas não podemos imaginar como ele poderia ter-se alojado em seu livro durante todos esses meses sem o nosso conhecimento, portanto não temos nenhuma opção senão responsabilizá-lo.

Esperamos que se dê ao trabalho de reformar esse capítulo e eu lhe darei uma oportunidade de tornar-se um cidadão produtivo do seu livro. Anexo envio um relatório do policial que efetuou a prisão. Julie Sussman.

Caso você esteja imaginando o que “PPA” significa, as duas primeiras letras significam “Professional Pain”. Você provavelmente adivinhará o que “A” significa, mas quero salientar que Julie se orgulha desse título e com muita razão. Googols de agradecimentos, Julie!

Não sou nenhum criptógrafo, e o capítulo sobre princípios de criptografia beneficiou-se tremendamente de comentários e sugestões de Ron Rivest, Sean Smith, Rachel Miller e Huijia Rachel Lin. Esse capítulo traz uma citação de pé de página sobre sinais de beisebol, pela qual agradeço a Bob Whalen, o treinador de beisebol de Dartmouth, pela paciência que teve ao me explicar um pouco sobre os sistemas de sinais no beisebol. Ilana Arbisser verificou que os biólogos computacionais alinham sequências de DNA do modo que eu expliquei no Capítulo 7. Jim DeWolf e eu fizemos várias combinações de palavras para o título deste livro, mas foi um aluno de Dartmouth, Chander Ramesh, que propôs Algorithms Unlocked.

O Departamento de Ciência de Computadores de Dartmouth College é um lugar incrível para trabalhar. Meus colegas são brilhantes e companheiros, e nosso pessoal profissional não deve nada a nenhum outro. Se você estiver procurando um programa de ciência de computadores no nível de graduação e pós-graduação ou se estiver procurando uma cargo universitário em ciência de computadores, tente Dartmouth.

Finalmente, agradeço à minha esposa, Nicole Cormen; aos meus pais, Renee e Perry Cormen; à minha irmã, Jane Maslin; e aos pais de Nicole, Colette e Paul Sage, por seu amor e apoio. Meu pai tem certeza de que a figura na página 2 é um 5, e não um S.

TOM CORMEN

Hanover, New Hampshire

Novembro de 2012

O que são algoritmos e por que você deve se importar com eles?

Vamos começar com a pergunta que sempre me fazem: “O que é um algoritmo?”1

Uma resposta de âmbito geral seria “um conjunto de etapas para executar uma tarefa”. Você executa algoritmos na sua vida diária. Você tem um algoritmo para escovar os dentes: abrir o tubo de pasta dental, pegar a escova de dentes, apertar o tubo de pasta dental sobre a escova e aplicar a quantidade necessária de dentifrício, fechar o tubo, colocar a escova em um quadrante da boca, movimentá-la para cima e para baixo durante N segundos etc. Se você pega ônibus ou metrô para ir trabalhar, terá um algoritmo para isso. E assim por diante.

Mas este livro é sobre algoritmos executados em computadores ou, de modo mais geral, dispositivos de computação. Exatamente como os algoritmos que você executa, os algoritmos executados em computadores também afetam a sua vida diária. Você usa o seu GPS para determinar uma rota de viagem? O aparelho executa o que denominamos algoritmo de “caminho mínimo” para determinar essa rota. Você compra produtos pela Internet? Então você usa (ou deveria usar) um site seguro que executa um algoritmo criptográfico. Quando você compra produtos pela Internet, eles são entregues por um serviço de entrega privado? Esse serviço usa algoritmos para designar pacotes a caminhões individuais e então determinar a ordem em que cada motorista deve entregar esses pacotes. Algoritmos são executados em computadores em todos os lugares — no seu laptop, em servidores, no seu smartphone, em sistemas embutidos (como no seu carro, no seu forno de micro-ondas ou em sistemas de ar condicionado) — em todos os lugares!

O que distingue um algoritmo executado em um computador de um algoritmo que você executa? Você poderia tolerar quando um algoritmo não é descrito com precisão, mas um computador não pode. Por exemplo, se você vai de carro para o trabalho, o seu algoritmo de ir de carro para o trabalho poderia dizer “se o tráfego estiver ruim, pegue uma rota alternativa”. Embora você saiba o que quer dizer “tráfego ruim”, um computador não sabe.

1 Ou, como um amigo que jogava hóquei comigo perguntaria: “O que é um mau goritmo?”

Portanto, um algoritmo de computador é um conjunto de etapas para executar uma tarefa descrita com precisão suficiente para que um computador possa executá-la. Se você já fez programação de computador, pouca que seja, em Java, C, C++, Python, Fortran, Matlab ou semelhantes, tem alguma ideia do que significa nível de precisão. Se você nunca escreveu um programa de computador, talvez perceba tal nível de precisão ao ver como eu descrevo algoritmos neste livro.

Vamos à próxima pergunta: “O que queremos de um algoritmo de computador?”

Algoritmos de computador resolvem problemas de computação. Queremos duas coisas de um algoritmo de computador: dada uma entrada para um problema, o algoritmo deve sempre produzir uma solução correta para o problema e usar recursos computacionais eficientemente ao fazê-lo. Vamos examinar esses dois desejos, um por vez.

CORREÇÃO

O que significa produzir uma solução correta para um problema? Normalmente, podemos especificar com precisão o que uma solução correta acarretaria. Por exemplo, se o seu GPS produzir uma solução correta para determinar a melhor rota de viagem, pode ser que essa rota, entre todas as rotas possíveis para você ir de onde está até onde deseja ir, seja a que o levará ao seu destino no menor tempo possível. Ou, talvez, essa rota seja a que tem a menor distância possível. Ou a que o levará ao seu destino desejado o mais rapidamente possível, mas sem pagar pedágio. É claro que as informações que o seu GPS usa para determinar uma rota podem não estar de acordo com a realidade. A menos que possa acessar informações de tráfego em tempo real, o seu GPS pode entender que o tempo para percorrer uma estrada é igual à distância total da estrada dividida pelo limite de velocidade nessa estrada. Todavia, se a estrada estiver congestionada, o GPS pode lhe dar um mau conselho se o que você estiver procurando for a estrada mais rápida. Ainda assim poderíamos dizer que o algoritmo de roteamento que o GPS executa está correto, mesmo que a entrada dada ao algoritmo não esteja; para a entrada que lhe foi dada, o algoritmo de roteamento produz a rota mais rápida.

Agora, para alguns problemas, pode ser difícil ou até impossível dizer se um algoritmo produz uma solução correta. Considere o reconhecimento de caracteres ópticos, por exemplo. Essa imagem de 11 × 6 pixels é um 5 ou um S?

Alguns dirão que é um 5, enquanto outros poderão achar que é um S; portanto, como podemos afirmar que a decisão de um computador é correta ou incorreta?

Não podemos. Neste livro, focalizaremos algoritmos de computador que têm soluções cognoscíveis.

Todavia, às vezes, podemos aceitar que um algoritmo de computador pode produzir uma resposta incorreta, desde que possamos controlar a frequência com que isso acontece. Criptografia é um bom exemplo. O criptossistema RSA comumente usado depende de determinar se números grandes — realmente grandes, significando os de centenas de dígitos — são primos. Se você já escreveu um programa de computador, provavelmente pode escrever um que determine se um número n é primo. O programa testaria todos os divisores candidatos de 2 até n 1 e, se qualquer desses candidatos for de fato um divisor de n , então n é composto. Se nenhum número entre 2 e n 1 for divisor de n, então n é primo. Porém, se n tiver centenas de dígitos, haverá muitos divisores candidatos, mais até do que um computador realmente veloz poderia verificar em qualquer quantidade de tempo razoável. É claro que você poderia fazer algumas otimizações, como eliminar todos os candidatos pares uma vez determinado que 2 não é um divisor, ou parar ao chegar a n (visto que, se d é maior que n e d é um divisor de n, então n/d é menor que n e é também divisor de n; por consequência, se n tem um divisor, você o encontrará no instante em que chegar a n ). Se n tiver centenas de dígitos, embora n tenha aproximadamente somente metade do número de dígitos que n tem, ainda é um número grande. A boa notícia é que sabemos de um algoritmo que testa rapidamente se um número é primo. Porém, a má notícia é que ele pode cometer erros. Em particular, se ele declarar que n não é primo, então n definitivamente não é primo, mas se ele declarar que n é primo, há uma chance de n não sê-lo. A má notícia não é tão ruim assim: podemos controlar a taxa de erro de modo que seja realmente baixa, por exemplo, um erro a cada 250 vezes. Isso é suficientemente raro — um erro em aproximadamente um milhão de bilhões de vezes — para que a maioria de nós se sinta confortável com a utilização desse método para determinar se um número é primo pelo método criptográfico RSA.

Correção é um assunto arriscado com outra classe de algoritmos, denominados algoritmos de aproximação. Algoritmos de aproximação aplicam-se a problemas de otimização, nos quais queremos determinar a melhor solução de acordo com alguma medida quantitativa. Determinar a rota mais rápida, como um GPS faz, é um exemplo no qual a medida quantitativa é o tempo de viagem. Para alguns problemas, não temos nenhum algoritmo que determine uma solução ótima em qualquer quantidade de tempo razoável, mas sabemos de um algoritmo de aproximação que, em quantidade razoável de tempo, pode encontrar uma solução que é quase ótima. Nesse caso, “quase ótima” normalmente quer dizer que a medida quantitativa da solução encontrada pelo algoritmo de aproximação está dentro de algum fator da medida quantitativa da solução ótima. Contanto que especifiquemos qual é o fator desejado, podemos dizer que uma solução correta dada por um algoritmo de aproximação é qualquer solução que esteja dentro daquele fator da solução ótima.

USO DE RECURSO

O que significa um algoritmo usar recursos computacionais eficientemente? Já aludimos a uma medida de eficiência quando discutimos algoritmos de aproximação: tempo. Um algoritmo que dá uma solução correta mas leva muito tempo para produzir essa solução correta poderia ser de pouco ou nenhum valor. Se o seu GPS demorou uma hora para

determinar qual rota ele recomenda, você se daria o trabalho de ligá-lo? Na verdade, o tempo é a medida principal de eficiência que usamos para avaliar um algoritmo, uma vez demonstrado que o algoritmo dá uma solução correta. Mas não é a única medida. Poderíamos nos preocupar com a quantidade de memória que o algoritmo exige (seu uso de memória), visto que um algoritmo tem de ser executado dentro da memória disponível. Outros possíveis recursos que um algoritmo poderia usar: comunicação em rede, bits aleatórios (porque algoritmos que fazem escolhas aleatórias precisam de uma fonte de números aleatórios) ou operações de disco (para algoritmos projetados para trabalhar com dados residentes em disco).

Neste livro, como na maioria da literatura de algoritmos, focalizaremos apenas um recurso: o tempo. Como julgamos o tempo exigido por um algoritmo? Diferentemente da correção, que não depende do computador particular no qual o algoritmo é executado, o tempo de execução propriamente dito de um algoritmo depende de diversos fatores extrínsecos ao algoritmo em si: da velocidade do computador, da linguagem de programação na qual o algoritmo foi implementado, do compilador ou interpretador que traduz o programa para código executado no computador, da habilidade do programador que escreve o programa e de outras atividades que ocorrem no computador ao mesmo tempo que a execução do programa. E tudo isso pressupondo que o algoritmo seja executado em apenas um computador com todos os seus dados na memória.

Se fôssemos avaliar a velocidade de um algoritmo implementando-o em uma linguagem de programação real, executando-o em um computador particular com uma entrada dada e medindo o tempo que o algoritmo gasta, nada saberíamos sobre a velocidade de execução do algoritmo com uma entrada de tamanho diferente ou, possivelmente, até mesmo com uma entrada diferente de igual tamanho. Se quiséssemos comparar a velocidade relativa do algoritmo com a de algum outro algoritmo em relação ao mesmo problema, teríamos de implementar ambos e executá-los com várias entradas de vários tamanhos. Então, como podemos avaliar a velocidade de um algoritmo?

A resposta é que fazemos isso por meio de uma combinação de duas ideias. A primeira é que determinamos quanto tempo o algoritmo leva em função do tamanho de sua entrada. Em nosso exemplo de determinação de rota, a entrada seria alguma representação de um mapa rodoviário, e seu tamanho dependeria do número de interseções e do número de estradas que se ligam às interseções no mapa. (O tamanho físico da rede rodoviária não importaria, visto que podemos caracterizar todas as distâncias por números, e todos os números ocupam o mesmo tamanho na entrada; o comprimento de uma estrada não tem nenhuma relação com o tamanho da entrada.) Em um exemplo mais simples, para pesquisar uma lista de itens dada e determinar se um item particular está presente na lista, o tamanho da entrada seria o número de itens na lista.

A segunda é que avaliamos o quão rapidamente a função que caracteriza o tempo de execução aumenta com o tamanho da entrada — a taxa de crescimento do tempo de execução. No Capítulo 2, veremos as notações que usamos para caracterizar o tempo de execução de um algoritmo, porém o mais interessante em nossa abordagem é que examinamos somente o termo dominante no tempo de execução e não consideramos coeficientes. Isto é, focamos a ordem de crescimento do tempo de execução. Por exemplo, suponha que pudéssemos determinar que uma implementação específica de

um algoritmo particular para pesquisar uma lista de n itens leva 50n + 125 ciclos de máquina. O termo 50n domina o termo 125 assim que n se torna grande o suficiente, começando com n ≥ 3 e crescendo em dominância para listas de tamanhos ainda maiores. Assim, não consideramos o termo de baixa ordem 125 quando descrevemos o tempo de execução desse algoritmo hipotético. O que poderia surpreender você é que também descartamos o coeficiente 50, caracterizando, desse modo, que o tempo de execução cresce linearmente com o tamanho da entrada n. Como outro exemplo, se um algoritmo levasse 20n3 + 100n2 + 300n + 200 ciclos de máquina, diríamos que seu tempo de execução cresce segundo n3. Novamente, os termos de baixa ordem — 100n2, 300n e 200 — tornam-se cada vez menos significativos à medida que o tamanho da entrada n aumenta.

Na prática, os coeficientes que ignoramos não importam. Mas eles dependem tão fortemente de fatores extrínsecos que é inteiramente possível que, se estivéssemos comparando dois algoritmos, A e B, que têm a mesma ordem de crescimento e executam a mesma entrada, A pudesse executar mais rapidamente que B com uma combinação particular de máquina, linguagem de programação, compilador/interpretador e programador, ao passo que B executaria mais rapidamente que A com alguma outra combinação. É claro que, se os algoritmos A e B produzem soluções corretas e A sempre executa duas vezes mais rapidamente que B, se todo o resto for igual, vamos preferir sempre executar A em vez de B. Todavia, do ponto de vista da comparação de algoritmos no campo abstrato, focalizamos a ordem de crescimento, descartando coeficientes ou termos de baixa ordem.

Quanto à pergunta final que fazemos neste capítulo, “Por que eu deveria me importar com algoritmos de computador?”, a resposta depende de quem você seja.

ALGORITMOS DE COMPUTADOR PARA NÃO AFICIONADOS

Ainda que não se considere um aficionado de computadores, os algoritmos de computador importam para você. Afinal, a menos que esteja em uma expedição da vida selvagem sem GPS, provavelmente os usará todos os dias. Você já procurou algo na Internet hoje? O motor de busca que você usou — Google, Bing ou qualquer outro — empregou algoritmos sofisticados para pesquisar a Web e decidir em que ordem apresentar seus resultados. Você já dirigiu seu carro hoje? A menos que o seu carro seja um clássico dos automóveis, seus computadores de bordo tomaram milhares de decisões, todas baseadas em algoritmos, durante a sua viagem. Eu poderia continuar indefinidamente.

Como usuário final de algoritmos, é bom que você aprenda um pouco sobre como projetamos, caracterizamos e avaliamos os algoritmos. Entendo que você tenha no mínimo um leve interesse, já que pegou este livro e o leu até aqui. Muito bem! Agora vamos ver se despertamos o seu interesse rapidamente e se aguenta até a próxima festa na qual surja o assunto de algoritmos.2

2 Sim, eu sei que, a menos que você more no Vale do Silício, raramente o assunto algoritmos surgirá nas festas que você frequenta; porém, por alguma razão, nós, os professores de ciência da computação, achamos que é importante que nossos alunos não nos envergonhem em festas com sua falta de conhecimento em áreas particulares da ciência da computação.

ALGORITMOS DE COMPUTADOR PARA AFICIONADOS

Se você gosta de computadores, é bom se interessar também por algoritmos de computador! Eles não somente estão no coração de tudo o que vai dentro do seu computador, mas também são uma tecnologia, exatamente como tudo o mais que está dentro do seu computador. Você pode até pagar mais caro por um computador equipado com o mais recente e melhor processador, mas precisará executar implementações de bons algoritmos nesse computador para que o dinheiro que gastou valha a pena.

Damos um exemplo que ilustra como os algoritmos são de fato uma tecnologia. No Capítulo 3, veremos alguns algoritmos diferentes que ordenam uma lista de n valores em ordem crescente. Alguns desses algoritmos terão tempos de execução que crescem segundo n2, mas alguns terão tempos de execução que crescem somente segundo n lg n. O que é lg n? É o logaritmo na base 2 de n, ou log2 n. Cientistas da computação usam logaritmos base 2 com tanta frequência que, exatamente como matemáticos e cientistas usam a abreviatura ln para o logaritmo natural — loge n —, os cientistas da computação usam sua própria abreviatura para logaritmos base 2. Agora, como a função lg n é o inverso de uma função exponencial, ela cresce muito lentamente com n. Se n = 2x, então x = lg n. Por exemplo, 210 = 1024, portanto lg1024 é apenas 10; de modo semelhante, 220 = 1.048.576 e, assim, lg1.048.576 é apenas 20; 230 = 1.073.471.824 significa que lg1.073.471.824 é somente 30. Portanto, o crescimento de n lg n versus n2 troca um fator de n por um fator de apenas lg n, e esse é um negócio que você aceitaria fazer a qualquer instante.

Vamos tornar esse exemplo mais concreto confrontando um computador mais rápido (computador A), que executa um algoritmo de ordenação cujo tempo de execução para n valores cresce segundo n2, com um computador mais lento (computador B), que executa um algoritmo de ordenação cujo tempo de execução cresce segundo n lg n. Cada um deles deve ordenar um arranjo de 10 milhões de números. (Embora 10 milhões de números possa parecer muito, se os números forem inteiros de 8 bytes, a entrada ocupará cerca de 80 megabytes,o que cabe muitas e muitas vezes na memória até mesmo de um laptop baratinho.) Suponha que o computador A execute 10 bilhões de instruções por segundo (mais rapidamente que qualquer computador sequencial único à época da redação deste livro) e que o computador B execute somente 10 milhões de instruções por segundo, de modo que o computador A é mil vezes mais rápido do que o computador B em poder de computação bruto. Para tornar a diferença ainda mais drástica, suponha que o programador mais esperto do mundo codifique em linguagem de máquina para o computador A, e o código resultante exija 2n2 instruções para ordenar n números. Suponha ainda mais que um programador apenas médio escreva para o computador B usando linguagem de alto nível com um compilador ineficiente e que o código resultante tenha 50 n lg n instruções. Para ordenar 10 milhões de números, o computador A leva

o que é mais de 5,5 horas, enquanto o computador B leva

5010 lg 10 instruções

≈

1.163 segundos, 77 7

10 instruções /segundo

o que é menos de 20 minutos. Usando um algoritmo cujo tempo de execução cresce mais lentamente, mesmo com um compilador ruim, o computador B executa mais de 17 vezes mais rapidamente que o computador A! A vantagem do algoritmo n lg n é ainda mais pronunciada quando ordenamos 100 milhões de números: enquanto o algoritmo n2 no computador A leva mais de 23 dias, o algoritmo n lg n no computador B leva menos de quatro horas. Em geral, à medida que o tamanho do problema aumenta, o mesmo ocorre com a vantagem relativa do algoritmo n lg n

Mesmo com os impressionantes avanços que vemos continuamente no hardware de computador, o desempenho total do sistema depende de escolher algoritmos eficientes, tanto quanto de escolher hardware rápido ou sistemas operacionais eficientes. Exatamente como há avanços rápidos em outras tecnologias de computador, também há esses mesmos avanços em algoritmos.

O QUE MAIS LER?

Em minha muitíssimo tendenciosa opinião, a fonte mais clara e mais útil sobre algoritmos de computador é Introduction to Algorithms [CLRS09], de autoria de quatro camaradas demoniacamente lindos. O livro é comumente denominado “CLRS”, as iniciais dos autores. Muito do material que apresento neste livro retirei do livro deles, que é muitíssimo mais completo que este. Porém, os autores supõem que você já fez ao menos um pouco de programação de computador, e não economizam na matemática. Se achar que o nível de matemática desse livro está bom e que você está pronto para ir mais a fundo no assunto, o CRLS será melhor (na minha humilde opinião, é claro).

O livro de John MacCormick, Nine Algorithms That Changed the Future [Mac12] descreve vários algoritmos e aspectos relacionados da computação que afetam nossa vida diária. O tratamento de MacCormick é menos técnico do que o deste livro. Se achar que a minha abordagem neste livro é demasiadamente matemática, recomendo que tente ler o livro de MacCormick. Você conseguirá entender grande parte dele, mesmo que seus conhecimentos de matemática sejam pífios.

No improvável evento de você achar que o CLRS é muito água com açúcar, poderá tentar os vários volumes do conjunto The Art of Computer Programming, de Donald Knuth [Knu97, Knu98a, Knu98b, Knu11]. Embora o título da série possa dar a entender que ela focaliza detalhes de escrita de código, esses livros contêm análises de algoritmos brilhantes e profundos. Porém, aviso: o material em TAOCP é intenso. A propósito, se você está imaginando de onde vem a palavra “algoritmo”, Knuth informa que ela é derivada do nome “al-Khowârizmî”, um matemático persa do século IX.

Além do CLRS, há vários outros textos excelentes sobre algoritmos de computador publicados ao longo dos anos. As notas referentes ao Capítulo 1 do CLRS apresentam uma lista de muitos desses livros. Em vez de reproduzir essa lista aqui, procure-a no CLRS.

Como descrever e avaliar algoritmos de computador

No capítulo anterior, você teve uma ideia de como expressamos em palavras o tempo de execução de um algoritmo de computador: focalizando o tempo de execução como função do tamanho da entrada e, especificamente, a ordem de crescimento do tempo de execução. Neste capítulo, voltaremos um pouco atrás e veremos como descrever algoritmos de computador. Então veremos as notações que usamos para caracterizar os tempos de execução de algoritmos. Encerraremos este capítulo examinando algumas técnicas que usamos para projetar e entender algoritmos.

COMO DESCREVER ALGORITMOS DE COMPUTADOR

Sempre temos a opção de descrever um algoritmo de computador como um programa executável em uma linguagem de programação comumente usada, como Java, C, C++, Python ou Fortran. Na verdade, é exatamente isso que fazem vários livros didáticos sobre algoritmos. O problema de usar linguagens de programação reais para especificar algoritmos é que você pode se atolar nos detalhes da linguagem e não perceber as ideias que fundamentam os algoritmos. Outra abordagem, que adotamos no livro Introduction to Algorithms, usa “pseudocódigo”, que parece uma mistura de várias linguagens; se você já usou uma linguagem de programação real, facilmente entenderá pseudocódigo. Porém, se nunca programou, o pseudocódigo poderá parecer um pouco misterioso.

A abordagem que adoto neste livro é a de não tentar descrever algoritmos para software ou hardware, mas para “massacinzentaware”: aquilo que está entre as suas orelhas. Além disso, adotarei como premissa que você nunca escreveu um programa de computador e, portanto, não expressarei algoritmos em nenhuma linguagem de programação real ou nem mesmo em pseudocódigo. Em vez disso, eu os descreverei em inglês (nesta tradução, em português) usando analogias com cenários do mundo real, sempre que puder. Para indicar o que acontece quando (o que denominamos “fluxo de controle” em programação) usarei listas e listas dentro de listas. Se quiser implementar um algoritmo em uma linguagem de programação real, acreditarei piamente que você será capaz de traduzir minha descrição em código executável.

Se bem que tentarei manter as descrições em nível um tanto não técnico quanto possível, este livro é sobre algoritmos para computadores, e por isso terei de usar terminologia de computação. Por exemplo, programas de computador contêm procedimentos (também conhecidos como funções ou métodos em linguagens de programação reais) que especificam como fazer algo. Para conseguir que o procedimento realmente faça o que deve fazer, nós o chamamos . Quando chamamos um procedimento, nós lhe fornecemos entrada (usualmente, no mínimo, uma, mas alguns procedimentos não precisam de nenhuma). Especificamos a entrada como parâmetros entre parênteses após o nome do procedimento. Por exemplo, para calcular a raiz quadrada de um número, podemos definir um procedimento SQUARE-ROOT(x); nesse caso, nos referimos à entrada para o procedimento como parâmetro x. A chamada de um procedimento pode ou não produzir resultado, dependendo de como especificamos o procedimento. Se o procedimento produzir resultado (ou saída), usualmente consideramos que tal resultado é algo que é passado de volta ao seu chamador. Em jargão de computação, dizemos que o procedimento retorna um valor.

Muitos programas e algoritmos trabalham com vetores de dados. Um arranjo agrega dados do mesmo tipo em uma entidade. Pense em um arranjo como se ele fosse uma tabela, na qual, dado o índice de uma entrada, podemos falar sobre o elemento do arranjo que está naquele índice. Por exemplo, veja a tabela a seguir com os cinco primeiros presidentes dos Estados Unidos:

Por exemplo, o elemento no índice 4 nessa tabela é James Madison. Pensamos nessa tabela não como cinco entidades separadas, mas como uma tabela com cinco entradas. Um arranjo é semelhante. Os índices para um arranjo são números consecutivos que podem começar em qualquer lugar, mas usualmente nós os começaremos em 1.1 Dado o nome de um arranjo e um índice para o arranjo, nós os combinamos com colchetes para indicar um elemento particular do arranjo. Por exemplo, denotamos o i-ésimo elemento de um arranjo A por A[i].

Arranjos em computadores têm outra característica importante: o tempo que se leva para acessar qualquer elemento de um arranjo é o mesmo. Uma vez dado ao computador um índice i para o arranjo, ele pode acessar o i-ésimo elemento tão rapidamente quanto pode acessar o primeiro elemento, independentemente do valor de i.

1 Se você programa em Java, C ou C++, está acostumado a usar arranjos que começam em 0. Começar arranjos em 0 é bom para computadores, mas para a nossa massacinzentaware muitas vezes é mais intuitivo começar em 1.

Vamos ver nosso primeiro algoritmo: buscar um valor particular em um arranjo. Isto é, dado um arranjo, queremos saber qual entrada no arranjo, se houver alguma, contém um valor dado. Para ver como podemos fazer uma busca em um arranjo, vamos imaginar que ele seja uma longa prateleira cheia de livros e supor que você queira saber em que lugar da prateleira pode encontrar um livro escrito por Jonathan Swift. Os livros na prateleira podem estar organizados de algum modo, talvez em ordem alfabética por autor, em ordem alfabética por título ou, em uma biblioteca, pelo número de chamada. Talvez a prateleira de livros seja como a que eu tenho em casa, na qual meus livros não estão organizados de nenhum modo particular.

Se você não puder saber de antemão que os livros estão organizados na prateleira, como encontrará o livro de Jonathan Swift? Eis o algoritmo que eu seguiria. Eu começaria na extremidade esquerda da prateleira e examinaria o livro que está na extrema esquerda. Se for de Swift, localizei o livro. Caso contrário, examinaria o próximo livro à direita e, se esse livro fosse de Swift, teria localizado o livro. Se não, continuaria indo para a direita e examinaria livro após livro até encontrar um livro de Swift ou até chegar à extremidade direita da prateleira, caso em que poderia concluir que ela não contém nenhum livro de Jonathan Swift. (No Capítulo 3, veremos como buscar um livro quando os livros estão organizados na prateleira.)

Agora veja como podemos descrever esse problema de busca em termos de computação. Vamos imaginar que os livros que estão na prateleira formam um arranjo. O livro na extrema esquerda está na posição 1, o próximo livro à direita dele está na posição 2, e assim por diante. Se tivermos n livros na prateleira, o livro na extrema direita estará na posição n. Queremos determinar o número de posição na prateleira de qualquer livro de Jonathan Swift.

Como um problema de computação geral, temos um arranjo A (a prateleira inteira cheia de livros na qual teremos de procurar) de n elementos (os livros individuais) e queremos determinar se um valor x (um livro de Jonathan Swift) está presente no arranjo A . Se estiver, queremos determinar um índice i tal que A [ i ] = x (a i -ésima posição na prateleira contém um livro de Jonathan Swift). Também precisamos de algum modo de indicar que o arranjo A não contém x (a prateleira não contém nenhum livro de Jonathan Swift). Não supomos que x aparece no máximo uma vez no arranjo (talvez você tenha várias cópias de algum livro) e, portanto, se x estiver presente no arranjo x , ele pode aparecer várias vezes. Tudo o que queremos de um algoritmo de busca é qualquer índice no qual encontraremos x no arranjo. Vamos supor que os índices desse arranjo começam em 1, de modo que seus elementos são A [ i ] até A [ n ].

Se buscarmos um livro de Jonathan Swift começando na extremidade esquerda da prateleira, verificando livro por livro à medida que prosseguimos para a direita, denominaremos essa técnica busca linear. Em termos de um arranjo em um computador, começamos no início do arranjo, examinamos cada elemento do arranjo por vez (A[1] depois A[2], depois A[3], e assim por diante até A[n]) e registramos o lugar onde encontramos x, caso o encontremos.

O procedimento a seguir, LINEAR-SEARCH, adota três parâmetros, que separamos por vírgulas na especificação.

Procedimento LINEAR-SEARCH (A, n, x)

Entrada:

• A: um arranjo.

• n: o número de elementos em A no qual procurar.

• x: o valor que buscamos.

Saída: Um índice i para o qual A[i] = x ou o valor especial NOT-FOUND, que pode ser qualquer índice inválido no arranjo, por exemplo, 0 ou qualquer inteiro negativo.

1. Ajustamos resposta para NOT-FOUND.

2. Para cada índice i, indo de 1 a n, em ordem:

a. Se A[i] = x, então ajuste resposta para o valor de i

3. Retorne o valor de resposta como saída.

Além dos parâmetros A , n e x, o procedimento LINEAR-SEARCH usa uma variável denominada resposta . O procedimento designa um valor inicial de NOTFOUND à resposta na etapa 1. A etapa 2 verifica cada entrada de arranjo A [1] até A[n] para ver se a entrada contém o valor x. Sempre que a entrada A[i] for igual a x, a etapa 2A designa o valor corrente de i à resposta. Se x aparecer no arranjo, o valor de saída retornando na etapa 3 é o último índice no qual x apareceu. Se x não aparecer no arranjo, o teste de igualdade na etapa 2A nunca será verdadeiro, e o valor de saída retornado é NOT-FOUND, como designado à resposta na etapa 1.

Antes de continuarmos discutindo busca linear, comentamos como especificar ações repetidas, como na etapa 2. É bastante comum em algoritmos executar alguma ação para uma variável adotando valores em alguma faixa. A execução de ações repetidas é denominada laço e, toda vez que o executamos, o laço é uma iteração. Para o laço da etapa 2, escrevi: “Para cada índice i, indo de 1 a n, na ordem.” Em vez disso, de agora em diante, escreverei “Para i = 1 até n”, que é uma frase mais curta, porém transmite a mesma estrutura. Observe que, quando escrevo um laço desse modo, temos de dar à variável do laço (aqui, i) um valor inicial (aqui, 1), e em cada iteração do laço temos de testar o valor corrente da variável do laço em relação a um limite (aqui, n). Se o valor corrente da variável do laço for menor ou igual ao limite, fazemos tudo no corpo do laço, (aqui, a etapa 2A). Após uma iteração executar o corpo do laço, incrementamos a variável do laço — somando 1 a ela — e voltamos a comparar a variável do laço, agora com seu novo valor, com o limite. Testamos repetidamente a variável do laço em relação ao limite, executamos o corpo do laço e incrementamos a variável do laço até que ela ultrapasse esse limite. Então, a execução continua da etapa que vem imediatamente após o corpo do laço (aqui, etapa 3). Um laço da forma “Para i = 1 até n”, executa n iterações e n + 1 testes em relação ao limite (porque a variável do laço ultrapassa o limite no teste n + 1).

Espero que ache óbvio que o procedimento LINEAR-SEARCH sempre retorna uma resposta correta. Todavia, você pode ter notado que esse procedimento é ineficiente: ele continua a pesquisar o arranjo mesmo após ter encontrado um índice i para o qual A[i] = x. Normalmente, você não continuaria a procurar um livro assim que o encontrasse em sua prateleira, continuaria? Em vez disso, podemos escrever nosso procedimento de busca linear de modo que ele pare assim que encontrar o valor x no arranjo. Presumimos que, quando dizemos retornar um valor, o procedimento imediatamente retorna o valor ao seu chamador, que então assume o controle.

Procedimento BETTER-LINEAR-SEARCH (A, n, x)

Entradas e Saída: As mesmas de LINEAR-SEARCH.

1. Para i = 1 até n: a. Se A[i] = x, então retorne o valor de i como saída.

2. Retorne NOT-FOUND como saída.

Acredite ou não, podemos tornar a busca linear ainda mais eficiente. Observe que, cada vez que passamos pelo laço da etapa 1, o procedimento BETTERLINEAR-SEARCH faz dois testes: um teste na etapa 1 para determinar se i ≤ n (e, se for, executar mais uma iteração do laço) e o teste da igualdade na etapa 1A. Em termos de fazer uma busca em uma prateleira de livros, esses testes correspondem a ter de verificar duas coisas para cada livro: você passou do final da prateleira e, se não passou, o livro seguinte é de Jonathan Swift? É claro que você não sofrerá muito por ter passado do final da prateleira (se estiver examinando os livros muito de perto, o máximo que acontecerá é dar de cara com uma parede no final da prateleira), mas em um programa de computador, em geral, é muito ruim tentar acessar elementos do arranjo depois do final do arranjo. O seu programa pode falhar ou corromper dados.

É possível dar um jeito de executar somente uma verificação para cada livro que examinar. E se você tivesse certeza de que sua prateleira contém um único livro de Jonathan Swift? Então também teria certeza de que o encontraria e, portanto, nunca teria de verificar se chegou ao final da prateleira. Bastaria verificar cada livro por vez para ver se é de Swift.

Talvez você tenha emprestado todos os seus livros de Jonathan Swift ou, então, achou que tinha livros dele mas nunca teve; portanto, poderia não ter certeza de que a sua prateleira contém qualquer livro desse autor. Eis o que você pode fazer. Pegue uma caixa vazia do tamanho de um livro e escreva no lado estreito da caixa (onde seria a lombada de um livro) “As viagens de Gulliver” de Jonathan Swift. Então, quando estiver procurando da esquerda para a direita ao longo da prateleira, só precisará verificar se está vendo alguma coisa escrita por Swift; não terá de se preocupar em passar do final da prateleira porque sabe que encontrará algo de Swift. A única pergunta é se você realmente encontrou um livro de Swift ou se encontrou a caixa vazia que identificou como se fosse um livro dele. Se encontrou a caixa vazia, na realidade você não tem um livro de Swift. Todavia, isso é fácil de verificar, e você só precisa fazê-lo uma única vez, ao final de sua busca, em vez de uma vez para cada livro na prateleira.

Há mais um detalhe do qual você precisa estar ciente: e se o único livro de Jonathan Swift que você tinha em sua prateleira fosse o livro na extrema direita? Se substituí-lo pela caixa vazia, a sua busca terminará na caixa vazia e você poderá concluir que não tinha o livro. Portanto, terá de fazer mais uma verificação para essa possibilidade, mas é apenas uma verificação, em vez de uma verificação para cada livro na prateleira.

Em termos de um algoritmo de computador, colocaremos o valor x que estávamos procurando na última posição, A[n], depois de salvar o conteúdo de A[n] em outra variável. Assim que encontrarmos x, testaremos para ver se realmente o encontramos. Denominamos o valor que pusemos no arranjo sentinela, mas você pode imaginá-lo como se fosse a caixa vazia.

Procedimento SENTINEL-LINEAR-SEARCH (A, n, x)

Entradas e saída: As mesmas de LINEAR-SEARCH.

1. Salve A[n] em último e então ponha x em A[n].

2. Iguale i a 1.

3. Enquanto A[i] ≠ x , faça o seguinte:

a. Incremente i

4. Restaure A[n] de último

5. Se i < n ou A[n] = x, retorne o valor de i como saída.

6. Caso contrário, retorne NOT-FOUND como saída.

A etapa 3 é um laço, mas não um laço que conta alguma variável de laço. Em vez disso, o laço itera enquanto a condição se mantiver; aqui, a condição é que A[i] ≠ x. O modo de interpretar tal laço é realizar o teste (aqui, A[i] ≠ x) e, se o teste for verdadeiro, fazer tudo no corpo do laço (aqui, etapa 3A, que incrementa i). Então volte e execute o teste, e, se o teste der verdadeiro, execute o corpo. Continue assim, executando o teste e o corpo, até o teste dar falso. Então continue da etapa seguinte após o corpo do laço (aqui, continue da etapa 4).

O procedimento SENTINEL-LINEAR-SEARCH é um pouco mais complicado que os dois primeiros procedimentos de busca linear. Como ele coloca x em A[n] na etapa 1, temos a garantia de que A[i] será igual a x para algum teste na etapa 3. Quando isso acontecer, sairemos do laço da etapa 3, e o índice i não mudará dali em diante. Antes de fazermos qualquer outra coisa, a etapa 4 restaura o valor original em A[n] (minha mãe me ensinou a pôr as coisas de volta em seus lugares depois de usá-las). Então, temos de determinar se realmente encontramos x no arranjo. Como colocamos x no último elemento, A[n], sabemos que, se encontrarmos x em A[i] onde i < n, realmente encontramos x e queremos retornar o índice i. E se encontrarmos x em A[n]? Isso significa que não encontramos x antes de A[n] e, portanto, precisamos determinar se A[n] é igual a x. Se for, temos de retornar o índice n, que é igual a i nesse ponto, mas se não for temos de retornar NOT-FOUND. A etapa 5 faz esses testes e retorna o índice correto se x estava originalmente no arranjo. Se x foi encontrado só porque a etapa 1 o colocou no arranjo, a etapa 6 retorna NOT-FOUND. Embora SENTINEL-LINEAR-SEARCH tenha de executar dois testes depois de seu laço terminar, ele realiza somente um teste em cada iteração do laço, o que o torna mais eficiente do que LINEAR-SEARCH ou BETTER-LINEAR-SEARCH.

COMO CARACTERIZAR OS TEMPOS DE EXECUÇÃO

Vamos voltar ao procedimento LINEAR-SEARCH da página 12 e entender seu tempo de execução. Lembre-se de que queremos caracterizar o tempo de execução em função do tamanho da entrada. Aqui, nossa entrada é um arranjo A de n elementos, juntamente com o número n e o valor x que estamos buscando. O tamanhos de n e x são insignificantes à medida que o arranjo fica grande — afinal, n é apenas um inteiro isolado e x é apenas tão grande quanto um dos n elementos do arranjo —, portanto diremos que o tamanho da entrada é n, o número de elementos em A

Temos de adotar algumas premissas simples sobre o tempo que as coisas demoram. Presumiremos que cada operação individual — seja uma operação aritmética (como adição,

subtração, multiplicação ou divisão), seja uma comparação, uma designação a uma variável, uma indexação a um arranjo ou uma chamada ou retorno de um procedimento — demora alguma quantidade de tempo fixa que é independente do tamanho da entrada.2 O tempo poderia variar de operação a operação, por exemplo, uma divisão poderia levar mais tempo que uma adição, porém quando uma etapa compreende apenas operações simples, cada execução individual daquela etapa leva alguma quantidade de tempo constante. Como as operações executadas são diferentes de etapa a etapa, e em razão dos fatores extrínsecos que apresentamos na página 3, o tempo para executar uma etapa poderia variar de etapa a etapa. Vamos dizer que cada execução da etapa i leva tempo o t i , onde t i é alguma constante que não depende de n.

É claro que temos de levar em conta que algumas etapas são executadas várias vezes. As etapas 1 e 3 são executadas apenas uma vez, mas e a etapa 2? Temos de testar i em relação a n um total de n + 1 vezes: n vezes nas quais i ≤ n e uma vez quando i é igual a n + 1 para sairmos do laço. A etapa 2A é executada exatamente n vezes, uma vez para cada valor de i de 1 a n. Não sabemos de antemão quantas vezes igualaremos resposta ao valor de i; poderia ser qualquer número de vezes, de 0 (se x não estiver presente no arranjo) a n (se todo valor de n no arranjo for igual a x). Se quisermos ser precisos em nossas contas — e normalmente não seremos assim tão precisos —, teremos de reconhecer que a etapa 2 faz duas coisas diferentes que são executadas um número diferente de vezes: o teste de i em relação a n ocorre n + 1 vezes, mas incrementar i acontece somente i vezes. Vamos separar o tempo para a linha 2 em ′ t 2 para o teste e ′′ t 2 para incrementar. De modo semelhante, separaremos o tempo para a etapa 2A em ′ t A 2 para testar se A[i] = x e ′′ t A 2 para igualar resposta a i. Portanto, o tempo de execução de LINEAR-SEARCH está em algum lugar entre

Agora reescrevemos novamente esses limites, reunimos os termos que são multiplicados por n, reunimos o resto dos termos e vemos que o tempo de execução está em algum lugar entre o limite inferior

′ + ′′ + ′

222 12 3

e o limite superior

2 Se você conhece um pouco de arquitetura de computadores, saberá que o tempo para acessar uma variável ou elemento de arranjo dado não é necessariamente fixo, já que pode depender de a variável ou elemento de arranjo estar na memória cache, na memória principal ou fora da memória, em um disco ou sistema de memória virtual. Alguns modelos sofisticados de computadores levam essas questões em conta, mas muitas vezes é suficiente presumir que todas as variáveis e entradas de arranjo estão na memória principal e que o acesso a todas elas leva a mesma quantidade de tempo.

Observe que ambos os limites são da forma c·n + d, onde c e d são constantes que não dependem de n. Isto é, eles são funções lineares de n. O tempo de execução de LINEAR-SEARCH é limitado por baixo por uma função linear de n e por cima por uma função linear de n

Usamos uma notação especial para indicar que um tempo de execução é limitado por cima por alguma função linear de n e por baixo por alguma função linear (possivelmente diferente) de n. Escrevemos que o tempo de execução é Θ(n). Esta é a letra grega teta, e dizemos “teta de n” ou apenas “teta n”. Como prometido no Capítulo 1, essa notação descarta o termo de ordem baixa + ′ + tt t () 12 3 e os coeficientes de ) ( ′ + ′′ + ′ n ttt 222 A para o limite inferior e ′ + ′′ + ′ + ′′ ttt t 222 A2 A para o limite superior). Embora percamos precisão por caracterizarmos o tempo de execução como Θ(n), ganhamos as vantagens de destacar a ordem de crescimento do tempo de execução e suprimir detalhes tediosos.

Essa notação Θ aplica-se a funções em geral, e não apenas às que descrevem tempos de execução de algoritmos, aplicando-se a outras funções que não as lineares. A ideia é que, se temos duas funções, f(n) e g(n), dizemos que f(n) é Θ(g(n)) se f(n) estiver dentro de um fator constante em relação a g(n) para n suficientemente grande. Portanto, podemos dizer que o tempo de execução de LINEAR-SEARCH está dentro de um fator constante em relação a n, tão logo n torne-se grande o suficiente.

Há uma definição técnica assustadora da notação Θ, mas felizmente é raro que tenhamos de recorrer a ela para usar a notação. Simplesmente focalizamos o termo dominante descartando termos de ordens mais baixas e fatores constantes. Por exemplo, a função n2/4 + 100n + 50 é Θ(n2); nesse caso descartamos os termos de baixa ordem 100n e 50, e descartamos o fator constante 1/4. Embora os termos de baixa ordem dominem n 2 /4 para valores pequenos de n, assim que n passar de 400, o termo n 2 /4 ultrapassará 100n + 50. Quando n = 1.000, o termo dominante n2/4 é igual a 250.000, ao passo que os termos de baixa ordem 100n + 50 somam somente 100.050; para n = 2.000, a diferença torna-se 1.000.000 versus 200.050. No mundo dos algoritmos, abusamos um pouco da notação e escrevemos f(n) = Θ(g(n)), de modo que podemos escrever n2/4 + 100n + 50 = Θ(n2).

Agora vamos examinar o tempo de execução de BETTER-LINEAR-SEARCH da página 13. Esse é um pouco mais complicado que o de LINEAR-SEARCH porque não sabemos de antemão quantas vezes o laço iterará. Se A[1] igual a x, ele iterará apenas uma vez. Se x não estiver presente no arranjo, o laço iterará todas as n vezes, que é o máximo possível. Cada iteração do laço leva alguma quantidade de tempo constante; portanto, podemos dizer que, no pior caso, BETTER-LINEAR-SEARCH leva o tempo Θ(n) para buscar um arranjo de n elementos. Por que “pior caso”? Como queremos que os algoritmos tenham baixos tempos de execução, o pior caso ocorre quando um algoritmo leva o tempo máximo para qualquer entrada possível.

No melhor caso, quando A[1] é igual a x, BETTER-LINEAR-SEARCH leva apenas uma quantidade de tempo constante: ele iguala i a 1, verifica se i ≤ n, o teste A[1] = x resulta verdadeiro e o procedimento retorna o valor de i, que é 1. Essa quantidade de tempo não depende de n. Escrevemos que o tempo de execução do melhor caso de BETTER-LINEAR-SEARCH é Θ(1) porque, no melhor caso, seu tempo de execução está dentro de um fator constante de 1. Em outras palavras, o tempo de execução do melhor caso é uma constante que não depende de n

Portanto, vemos que não podemos usar a notação Θ como uma afirmação abrangente que se aplica a todos os casos do tempo de execução de BETTER-LINEAR-SEARCH. Não podemos dizer que o tempo de execução é sempre Θ(n) porque, no melhor caso, ele é Θ(1). E não podemos dizer que o tempo de execução é sempre Θ(1) porque, no pior caso, ele é Θ(n). Todavia, podemos dizer que uma função linear de n é um limite superior em todos os casos e que temos uma notação para isso: O(n). Quando falamos nessa notação, dizemos “Ó maiúsculo de n” (“big-oh of n”) ou apenas “ó de n” (“oh of n”). Uma função f(n) é O(g(n)) se, logo que n se tornar suficientemente grande, f(n) é limitada por cima por alguma constante vezes g(n). Novamente, abusamos um pouco da notação e escrevemos f(n) = O(g(n)). Para BETTER-LINEAR-SEARCH, podemos usar a declaração abrangente que diz que seu tempo de execução em todos os casos é O(n); embora o tempo de execução possa ser melhor que uma função linear de n, ele nunca é pior.

Usamos a notação O para indicar que um tempo de execução nunca é pior que uma constante vezes alguma função de n, mas e se quiséssemos indicar que um tempo de execução nunca é melhor que uma constante vezes alguma função de n? Esse é um limite inferior, e usamos a notação Ω, que é a imagem especular da notação O: uma função f(n) é Ω(g(n)) se, logo que n tornar-se suficientemente grande, f(n) é limitada por baixo por alguma constante vezes g(n). Dizemos que “f(n) é ômega maiúsculo (ômega grande) de g(n)” ou apenas que “f(n) é ômega de g(n)”, e podemos escrever f(n) = Ω(g(n)). Visto que a notação O dá um limite superior, a notação Ω dá um limite inferior, e a notação Θ dá ambos os limites, superior e inferior, podemos concluir que uma função f(n) é Θ(g(n)) se e somente se f(n) for O(g(n)) e Ω(g(n)).

Podemos fazer uma declaração abrangente sobre um limite inferior para o tempo de execução de BETTER-LINEAR-SEARCH: em todos os casos ele é Ω(1). É claro que essa declaração é pateticamente fraca, visto que seria de esperar que qualquer algoritmo aplicado a qualquer entrada levasse, no mínimo, tempo constante. Não usaremos muito a notação Ω, mas ocasionalmente ela virá a calhar.

O termo abrangente para a notação, Θ a notação O e a notação Ω é notação assintótica. Isso porque essas notações capturam o crescimento de uma função à medida que seu argumento aproxima-se assintoticamente de infinito. Todas essas notações assintóticas nos dão o luxo de descartar termos de baixa ordem e fatores constantes de modo que possamos ignorar detalhes tediosos e focalizar o que é importante: como a função cresce com n

Agora vamos voltar a SENTINEL-LINEAR-SEARCH, da página 14. Exatamente como BETTER-LINEAR-SEARCH, cada iteração de seu laço leva uma quantidade de tempo constante e pode haver qualquer número de 1 a n interações. A diferença fundamental entre SENTINEL-LINEAR-SEARCH e BETTER-LINEAR-SEARCH é que o tempo por iteração de SENTINEL- LINEAR-SEARCH é menor que o tempo por iteração de BETTER-LINEAR-SEARCH. Ambos levam uma quantidade de tempo linear no pior caso, mas o fator constante para SENTINEL-LINEAR-SEARCH é melhor. Embora pudéssemos esperar que SENTINEL-LINEAR-SEARCH fosse mais rápido na prática, ele o seria apenas por um fator constante. Quando expressamos o tempo de execução de BETTER-LINEAR-SEARCH e SENTINEL-LINEAR-SEARCH usando notação assintótica, eles são equivalentes: Θ(n) no pior caso, Θ(l) no melhor caso e O(n) em todos os casos.

INVARIANTES DE LAÇO

Para os nossos três tipos de busca linear, foi fácil ver que cada um dá uma resposta correta. Às vezes, é um pouco mais difícil. Há uma ampla gama de técnicas, mais do que eu poderia comentar aqui.

Um método comum de mostrar correção usa uma invariante de laço: uma afirmativa que demonstramos ser verdadeira cada vez que iniciamos uma iteração de laço. Para que uma invariante de laço nos ajude a questionar a correção, temos de mostrar três coisas sobre ela:

Inicialização: É verdadeira antes da primeira iteração do laço.

Manutenção: Se é verdadeira antes de uma iteração do laço, permanecerá verdadeira antes da próxima iteração.

Terminação: O laço termina e, quando termina, a invariante do laço, juntamente com a razão do término do laço, nos dá uma propriedade útil. Como exemplo, damos aqui uma invariante de laço para BETTER-LINEARSEARCH:

No início de cada iteração da etapa 1, se x estiver presente no arranjo A, estará presente no subvetor (uma porção contígua de um arranjo) de A[i] a A[n].

Nem precisamos dessa invariante de laço para mostrar que, se o procedimento retornar um índice que não seja NOT-FOUND, o índice retornado é correto: o único modo de o procedimento poder retornar um índice i na etapa 1A é porque x é igual a A[i]. Em vez disso, usaremos essa invariante de laço para mostrar que, se o procedimento retornar NOT-FOUND na etapa 2, x não está em nenhum lugar no arranjo:

Inicialização: Inicialmente, i = 1 de modo que o subvetor na invariante de laço é A[i] até A[n], que é o arranjo inteiro.

Manutenção: Considere que, no início de uma iteração para um valor de i, se x estiver presente no arranjo A, ele estará presente na forma do subvetor de A[i] a A[n]. Se passarmos por essa iteração sem retornar, saberemos que A[i] ≠ x e poderemos dizer com segurança que, se x estiver presente no arranjo A, ele estará presente no subvetor de A[i + 1] a A[n]. Como i é incrementado antes da próxima iteração, a invariante de laço continua a valer antes da próxima iteração.

Terminação: Esse laço deve terminar, seja porque o procedimento retorna na etapa 1A seja porque i > n. Já tratamos do caso em que o laço termina porque o procedimento retorna na etapa 1A.

Para tratar do caso em que o laço termina porque i > n, recorremos ao contrapositivo da invariante de laço. O contrapositivo da declaração “se A então B” é “se não B então não A ”. O contrapositivo de uma declaração é verdadeiro se e somente se a declaração for verdadeira. O contrapositivo da invariante de laço é “se x não está presente no subvetor de A[i] a A[n], então ele não está presente no arranjo A”.

Agora, quando i > n, o subvetor de A[i] a A[n] é vazio e, portanto, esse subvetor não pode conter x. Portanto, pelo contrapositivo da invariante do laço, x não está presente em nenhum lugar no arranjo A e, portanto, é adequado retornar NOT-FOUND na etapa 2. Uau! É muito raciocínio para o que, na realidade, é um simples laço! Temos que passar por tudo isso todas as vezes que escrevermos um laço? Eu não, mas há alguns cientistas da computação que insistem em tal raciocínio rigoroso para cada laço que

seja. Quando estou escrevendo código real, na maioria das vezes que escrevo um laço constato que tenho uma invariante de laço em algum lugar no fundo da memória. Ela pode estar tão fundo na minha mente que nem mesmo percebo que ela está lá, mas eu poderia declará-la caso fosse necessário. Embora a maioria de nós concorde que uma invariante de laço já é demais para entender o simples laço em BETTER-LINEAR-SEARCH, invariantes de laço podem vir muito bem a calhar quando queremos entender por que laços mais complexos fazem a coisa certa.

RECURSÃO

Com a técnica de recursão, resolvemos um problema resolvendo instâncias menores do mesmo problema. Dou aqui o meu exemplo canônico favorito de recursão: computar n! (“fatorial de n”), que é definido por valores não negativos de n como n! = 1 se n = 0 e

=⋅nn nn n !( 1) (2)( 3) 32 1

se n ≥ 1. Por exemplo, 5! = 5 ·4· 3· 2· 1 = 120. Observe que

−= nn nn (1)! (1)( 2) (3)3 21, e, portanto,

=⋅nn n !( 1) para n ≥ 1 . Definimos n ! em termos de um problema “menor”, a saber, ( n 1 )!.

Poderíamos escrever um procedimento recursivo para calcular n! da seguinte maneira:

Procedimento FATORIAL (n)

Entrada: Um inteiro n ≥ 0.

Saída: O valor de n!.

1. Se n = 0, então retorne 1 como saída.

2. Caso contrário, retorne n vezes o valor retornado chamando FACTORIAL(n 1) recursivamente.

O modo como escrevi a etapa 2 é bem atrapalhado. Em vez disso, eu poderia escrever apenas “Caso contrário, retorne n·FACTORIAL ( n 1)” usando o valor de retorno da chamada recursiva dentro de uma expressão aritmética maior.

Para a recursão funcionar, duas propriedades devem valer. A primeira é que deve haver um ou mais casos-bases, nos quais computamos a solução diretamente sem recursão. A segunda é que cada chamada recursiva do procedimento deve ser a uma instância menor do mesmo problema que eventualmente chegará a um caso-base. Para o procedimento FACTORIAL, o caso-base ocorre quando n é igual a 0, e cada chamada recursiva é sobre uma instância na qual o valor de n é reduzido de 1. Desde que o valor original de n seja não negativo, a certa altura as chamadas recursivas se reduzirão ao caso-base.

Questionemos que o trabalho de um algoritmo recursivo pode parecer exageradamente simples à primeira vista. A chave é acreditar que cada chamada recursiva produz o resultado correto. Desde que estejamos dispostos a acreditar que chamadas recursivas fazem a coisa certa, questionar a correção muitas vezes é fácil. Eis como

poderíamos questionar que o procedimento FACTORIAL retorna a resposta correta. É claro que, quando n = 0, o valor retornado, 1, é igual a n!. Presumimos que, quando n ≥ 1, a chamada recursiva FACTORIAL (n 1) faz a coisa certa: ela retorna o valor de (n 1)!. Então o procedimento multiplica esse valor por n e, com isso, computa o valor de n!, que ele retorna.

Damos aqui um exemplo no qual as chamadas recursivas não são instâncias menores do mesmo problema, embora a matemática esteja correta. É de fato verdadeiro que, se n ≥ 0, então n! = ( n + 1)!/( n + 1). Porém, o seguinte procedimento recursivo, que tira proveito dessa fórmula, nunca conseguiria dar uma resposta quando n ≥ 1:

Procedimento BAD-FACTORIAL (n)

Entrada e Saída: As mesmas de FACTORIAL.

1. Se n = 0, então retorne 1 como saída.

2. Caso contrário, retorne BAD-FACTORIAL(n + 1)/(n + 1).

Se chamássemos BAD-FACTORIAL(1), ele geraria uma chamada recursiva de BAD-FACTORIAL(2), que geraria uma chamada recursiva de BAD-FACTORIAL(3). e assim por diante, e jamais chegaria até o caso-base quando n é igual a 0. Se você implementasse esse procedimento em uma linguagem de programação real e o executasse em um computador real, veria rapidamente algo como “erro de estouro de pilha”.

Muitas vezes podemos reescrever algoritmos que usam um laço em estilo recursivo. Damos a seguir busca linear, sem uma sentinela, escrita recursivamente:

Procedimento

RECURSIVE-LINEAR-SEARCH (A, n, i, x)

Entradas: As mesmas de LINEAR-SEARCH, mas com um parâmetro adicional i

Saída: O índice de um elemento igualando x no subvetor de A[i] a A[n] ou NOT-FOUND se x não aparece nesse subvetor.

1. Se i > n, então retorne NOT-FOUND.

2. Caso contrário, (i ≤ n), se A[i] = x, então retorne i.

3. Caso contrário, (i ≤ n e A[i] ≠ x), retorne

RECURSIVE-LINEAR-SEARCH (A, n, i + 1, x).

Aqui, o subproblema é buscar x no subvetor, indo de A [ i ] a A [ n ]. O caso-base ocorre na etapa 1 quando esse subvetor está vazio, isto é, quando i > n. Como o valor de i aumenta em cada uma das chamadas recursivas da etapa 3, se nenhuma chamada recursiva nunca retornar um valor de i na etapa 2 a certa altura i ficará maior que n e chegaremos ao caso-base.

O QUE MAIS LER?

Os Capítulos 2 e 3 de CLRS [CLRS09] abrangem muito do material deste capítulo. Um dos primeiros livros didáticos sobre algoritmos de autoria de Aho, Hopcroft e Ullman [AHU74] influenciou a área ao utilizar notação assintótica para analisar algoritmos. Tem dado muito trabalho provar que os programas estão corretos; se você quiser ir mais fundo nessa área, experimente ler os livros de Gries [Gri81] e Mitchell [Mit96].

Algoritmos para ordenar e buscar

No Capítulo 2, vimos três variações de busca linear em um vetor. Podemos fazer algo melhor? Resposta: depende. Se nada soubermos sobre a ordem dos elementos no vetor, a resposta é não, não podemos fazer algo melhor. No pior caso, teríamos de examinar todos os b elementos porque, se não encontrarmos o valor que estamos procurando nos primeiros n 1 elementos, ele poderia estar no último ou n-ésimo elemento. Portanto, não poderemos conseguir um tempo de execução do pior caso melhor que Θ (n) se nada soubermos sobre a ordem dos elementos no vetor.

Todavia, suponha que o vetor esteja ordenado em ordem não decrescente: cada elemento é menor ou igual ao seu sucessor no vetor, de acordo com alguma definição de “menor que”. Neste capítulo veremos que, se um vetor está ordenado, podemos usar uma técnica simples conhecida como busca binária para fazer uma busca em um vetor de n elementos no tempo de apenas O(lg n). Como vimos no Capítulo 1, o valor de lg n cresce muito lentamente em comparação com n e, portanto, a busca binária ganha da busca linear no pior caso.1

O que significa um elemento ser menor que outro? Quando os elementos são números, é óbvio. Quando os elementos são cadeias de caracteres de texto, podemos pensar em uma ordenação lexicográfica: um elemento é menor que outro se vier antes do outro elemento em um dicionário. Quando os elementos são alguma outra forma de dados, temos de definir o que significa “menor que”. Desde que tenhamos alguma noção clara de “menor que”, podemos determinar se um vetor é ordenado.

Lembrando o exemplo de livros em uma prateleira, no Capítulo 2, poderíamos ordenar os livros em ordem alfabética por autor, em ordem alfabética por título ou, em uma biblioteca, por número de chamada. Neste capítulo, diremos que os livros estão ordenados na prateleira se aparecerem em ordem alfabética por autor, da esquerda para a direita. Todavia, a prateleira pode conter mais de um livro do mesmo autor; talvez você tenha várias obras de William Shakespeare. Se quisermos buscar não apenas qualquer livro de Shakespeare, mas um livro específico de Shakespeare, diremos que, se dois livros têm o mesmo autor, o livro cujo título vem antes na ordem alfabética deve ficar à esquerda. Alternativamente, poderemos dizer que só o que nos

1 Se você não é aficionado de computadores e pulou a seção “Algoritmos de computador para aficionados”, no Capítulo 1, deve ler o material sobre logaritmos na página 6.

importa é o nome do autor; portanto, quando fizermos uma busca, qualquer coisa de Shakespeare servirá. Denominamos chave a informação que serve de comparação. Em nosso exemplo da prateleira de livros, a chave é apenas o nome do autor, em vez de uma combinação baseada primeiro no nome do autor e depois no título, caso haja duas obras do mesmo autor.

Então, como conseguimos ordenar o vetor, antes de mais nada? Neste capítulo, veremos quatro algoritmos — ordenação por seleção, ordenação por inserção, ordenação por intercalação e ordenação rápida (quicksort) — para ordenar um vetor, aplicando cada um deles ao nosso exemplo da prateleira de livros. Cada algoritmo de ordenação terá suas vantagens e suas desvantagens, e, no final do capítulo, faremos uma revisão e comparação desses algoritmos de ordenação. Todos os algoritmos de ordenação que veremos neste capítulo levam tempo Θ (n2) ou Θ (nlg n) no pior caso. Portanto, se você for executar somente algumas buscas, será melhor executar apenas busca linear. Mas, se você for executar muitas buscas, o melhor será primeiro ordenar o vetor e depois usar busca binária.

Ordenar é por si só um problema importante, e não somente como etapa prévia de processamento na busca binária. Pense em todos os dados que devem ser ordenados, como as entradas em uma lista telefônica, por nome; cheques no extrato mensal do banco por números e/ou datas nos quais eles foram processados pelo banco; ou até resultados de um motor de busca na Web, por relevância em relação à consulta. Ordenar é, frequentemente, uma etapa em algum outro algoritmo. Por exemplo, em computação gráfica, frequentemente os objetos são dispostos em camadas, uns sobre os outros. Um programa que apresenta objetos na tela teria de ordená-los de acordo com uma relação “acima” para poder desenhá-los de baixo para cima.

Antes de continuarmos, um comentário sobre o que é que ordenamos. Além da chave (que denominaremos chave de ordenação quando estamos ordenando), os elementos que ordenamos usualmente incluem também o que denominamos dados satélites. Embora dados satélites possam vir de um satélite, em geral não vêm. Dados satélites são as informações associadas à chave de ordenação, e devem acompanhá-la quando movimentamos elementos. Em nosso exemplo da prateleira de livros, a chave de ordenação é o nome do autor e os dados satélites são o livro em si.

Explico dados satélites aos meus alunos de um modo que eu tenho certeza de que eles entenderão. Mantenho uma planilha com as notas dos alunos, cujas linhas são ordenadas em ordem alfabética por nome de aluno. Para determinar as notas finais do curso no final do semestre, eu ordeno as linhas, sendo a chave de ordenação a coluna que contém a porcentagem de pontos obtidos no curso, e o resto das colunas, incluindo os nomes dos alunos, os dados satélites. Em seguida, ordeno a planilha em ordem decrescente de porcentagem, de modo que as linhas no topo correspondem a notas A, e as linhas de baixo, a notas D e E.2 Suponha que eu rearranjasse somente a coluna que contém a porcentagem sem mover a coluna inteira que contém a porcentagem. Isso deixaria os nomes dos alunos em ordem alfabética independentemente das

2 Dartmouth usa E, não F, para indicar uma nota que reprovaria o aluno. Não sei bem por que, mas imagino que isso tenha simplificado o programa de computador que converte notas representadas por letras em uma escala de 4 a 0.

porcentagens. Então, os alunos cujos nomes aparecem em primeiro lugar no alfabeto ficariam felizes, enquanto os que viessem no final do alfabeto, nem tanto.

Damos aqui outros exemplos de chaves de ordenação e dados satélites. Em uma lista telefônica, a chave de ordenação seria o nome, e os dados satélites seriam o endereço e o número do telefone. Em um extrato bancário, a chave de ordenação seria o número do cheque, e os dados satélites incluiriam o montante do cheque e a data em que foi compensado. Em um motor de busca, a chave de ordenação seria a medida da relevância para a consulta, e os dados satélites seriam o URL da página Web mais quaisquer outros dados sobre a página que estão armazenados no motor de busca.

Quando trabalharmos com vetores neste capítulo, agiremos como se cada elemento contivesse somente uma chave de ordenação. Se você estiver implementando qualquer dos algoritmos de ordenação dados aqui, terá de certificar-se de estar movendo os dados satélites associados a cada elemento ou, no mínimo, um ponteiro para os dados satélites sempre que mover a chave de ordenação.

Para que a analogia da prateleira de livros aplique-se a vetores em um computador, precisamos pressupor que a prateleira e seus livros têm dois aspectos adicionais, que eu admito que não são terrivelmente realistas. O primeiro é que todos os livros na prateleira são do mesmo tamanho porque, em um vetor de computador, todas as entradas de vetor são do mesmo tamanho. O segundo é que podemos numerar as posições dos livros na prateleira de 1 a n, e denominaremos cada posição espaço (slot). Espaço 1 é o espaço na extrema esquerda e espaço n é o espaço na extrema direita. Como você provavelmente já percebeu, cada espaço na prateleira corresponde a uma entrada no vetor.

Quero também comentar a palavra “ordenação”. Em linguagem comum, ordenação pode significar algo diferente do que aquilo que usamos em computação.

O dicionário on-line My Mac define “ordenar” como “arranjar sistematicamente em grupos; separar de acordo com tipo, classe etc.”: o modo como poderíamos “ordenar” roupas, por exemplo, camisas em um lugar, calças em outro, e assim por diante. No mundo dos algoritmos de computador, ordenar significa pôr em alguma ordem bem definida, e “arranjar sistematicamente em grupos” significa “colocar em um balde” (“bucketing”, “bucketizing”) ou em uma “cesta” (“binning”) ou, ainda, “classificar”.

BUSCA BINÁRIA

Antes de vermos alguns algoritmos de ordenação, vamos ver o que é busca binária, que requer que o vetor a ser submetido à busca já esteja ordenado. A busca binária tem a vantagem de levar somente tempo O(lg n) para fazer uma busca em um vetor de n elementos.

Em nosso exemplo da prateleira de livros, começamos com os livros já ordenados por nome de autor, da esquerda para a direita na prateleira. Usaremos o nome do autor como a chave e buscaremos qualquer livro de Jonathan Swift. Agora você pode entender que, como o sobrenome do autor começa com “S”, que é a décima nona letra do alfabeto, pode percorrer três quartos do caminho na prateleira (visto que 19/26 é aproximadamente 3/4) e fazer a busca ali. Porém, se você tiver todas as obras de Shakespeare, tem vários livros de um autor cujo sobrenome vem antes de Swift, o que pode empurrar os livros de Swift mais para a direita do que você esperava.

Em vez disso, veja como você poderia aplicar a busca binária para encontrar um livro de Jonathan Swift. Vá até o espaço que está exatamente no meio da prateleira, ache o livro que está ali e examine o nome do autor. Vamos dizer que você encontrou um livro de Jack London. Não somente esse não é o livro que você está procurando, mas, como você sabe que os livros estão ordenados em ordem alfabética de autor, também sabe que todos os livros à esquerda do livro de London não podem ser o livro que você está procurando. Examinando apenas um livro, você não precisou considerar metade dos livros que estão na prateleira! Qualquer livro de Swift deve estar na metade direita da prateleira. Portanto, agora você achará o espaço que está no ponto a meio caminho na metade direita da prateleira, e procurará o livro ali. Suponha que seja um livro de Leon Tolstói. Novamente, esse não é o livro que procura, mas você sabe que pode eliminar todos os livros à direita dele: metade dos livros que continuaram como possibilidades. Nesse ponto, você sabe que, se sua prateleira contiver qualquer livro de Swift, eles estarão no quarto de livros que está à direita do livro de London e à esquerda do livro de Tolstói. Em seguida, você acha o livro no espaço que está a meio caminho nesse quarto em consideração. Se for de Swift, a rodada terminou. Caso contrário, novamente você pode eliminar metade dos livros restantes. A certa altura, ou você acha o livro de Swift ou chega ao ponto no qual nenhum espaço é uma possibilidade. Neste último caso, você conclui que a prateleira não contém nenhum livro de Jonathan Swift.

Em um computador, fazemos busca binária em um vetor. A qualquer ponto, estamos considerando apenas um subvetor, isto é, a porção do vetor entre dois índices, incluindo os dois índices; vamos denominá-los p e r. Inicialmente, p = 1 e r = n, de modo que o subvetor começa como o vetor inteiro. Dividimos repetidamente ao meio o tamanho do subvetor que estamos considerando até que uma de duas coisas aconteça: ou encontramos o valor que estamos procurando ou o subvetor está vazio (isto é, p torna-se maior que r). A divisão repetitiva do tamanho do subvetor ao meio é o que dá origem ao tempo de execução O(lg n).

Com um pouco mais de detalhes, eis como uma busca binária funciona. Vamos dizer que estejamos buscando o valor x no vetor A. Em cada etapa, estamos considerando somente o subvetor que começa em A[p] e termina em A[r]. Como estaremos trabalhando bastante com subvetores, vamos denotar esse subvetor por A [ p . . r ]. A cada etapa, computamos o ponto médio q do subvetor em consideração, calculando a média entre p e r, e descartando a parte fracionária, se houver alguma: =+[]qp r () /2 (Aqui, usamos a operação “piso”, [] , para descartar a parte fracionária. Se você estiver implementando essa operação em linguagem como Java, C ou C + +, poderá apenas usar divisão inteira para descartar a parte fracionária.) Verificamos se A[q] é igual a x; se for, terminamos, porque podemos apenas retornar q como um índice em que o vetor A contém x

Se, ao contrário, constatarmos que A [q] ≠ x, aproveitamos a vantagem de supor que o vetor A já está ordenado. Visto que A[q] ≠ x, há duas possibilidades: A[q] > x ou A[q] < x. Em primeiro lugar tratamos do caso em que A[q] > x. Como o vetor está ordenado, sabemos não somente que A[q] é maior que x, mas também — considerando que o vetor está disposto da esquerda para a direita — que todo elemento do vetor à direita de A[q] é maior que x. Portanto, podemos eliminar de consideração todos os

elementos à direita de A[q]. Iniciaremos nossa próxima etapa sem mudar p, mas com r igual a q 1:

Se, em vez disso, constatarmos que A[q] < x, saberemos que cada elemento do vetor à esquerda de A[q] é menor que x e, portanto, podemos eliminar esses elementos de consideração. Começaremos nossa próxima etapa sem mudar r, mas com p igual a q + 1:

Damos a seguir o exato procedimento para busca binária:

Procedimento BINARY-SEARCH (A, n, x)

Entradas e Saída: As mesmas de LINEAR-SEARCH.

1. Iguale p a 1 e r a n

2. Enquanto p ≤ r, faça o seguinte:

a. Iguale q a +       pr () /2

b. Se A[q] = x, então retorne q.

c. Caso contrário, (A[q] ≠ x), se A[q] > x, então iguale r a q 1.

d. Caso contrário, (A[q] < x), iguale p a q + 1.

3. Retorne NOT-FOUND.

O laço na etapa 2 não termina necessariamente porque p tornou-se maior que r. Ele pode terminar na etapa 2B porque constata que A[q] é igual a x e retorna q como um índice em A, onde x ocorre.

Para mostrar que o procedimento BINARY-SEARCH funciona corretamente, basta mostrar que x não está presente em nenhum lugar no vetor se BINARY-SEARCH retornar NOT-FOUND na etapa 3. Usamos a seguinte invariante de laço:

No início de cada iteração do laço da etapa 2, se x estiver em algum lugar no vetor A, está em algum lugar no subvetor A[p..r].

E um breve argumento usando a invariante de laço:

Inicialização: A etapa 1 inicializa os índices p e r para 1 e n, respectivamente, e portanto a invariante do laço é verdadeira quando o procedimento entra pela primeira vez no laço.

Manutenção: Argumentamos acima que as etapas 2C e 2D ajustam p ou r corretamente.

Término: Se x não está no vetor, a certa altura o procedimento chega ao ponto

onde p e r são iguais. Quando isso acontece, a etapa 2A computa q como o mesmo

p e r. Se a etapa 2C igualar r a q 1, no início da próxima iteração r será igual a p 1, de modo que p será maior que r. Se a etapa 2D igualar p a q + 1, no início da próxima iteração p será igual a r + 1, e novamente p será maior que r . De qualquer modo, o teste do laço na etapa 2 resultará falso e o laço terminará. Como p > r, o subvetor p > r estará vazio e, portanto, o valor x não pode estar presente nele. Tomar o contrapositivo da invariante do laço (veja página 18) nos diz que, se x não está presente no subvetor A[p..r], então não está presente em nenhum lugar no vetor A. Portanto, o procedimento está correto ao retornar NOT-FOUND na etapa 3. Podemos também escrever busca binária como um procedimento recursivo:

Procedimento

RECURSIVE-BINARY-SEARCH (A, p, r, x)

Entradas e Saída: As entradas A e x são as mesmas de LINEAR-SEARCH, assim como a saída. As entradas p e r delimitam o subvetor A[p..r] em consideração.

1. Se p > r, então retorne NOT-FOUND.

2. Caso contrário p ≤ r, faça o seguinte:

a. Iguale q para +       pr () /2

b. Se A[q] = x, então retorne q

c. Caso contrário, (A[q] ≠ x), se A[q] > x, então retorne

RECURSIVE-BINARY-SEARCH A, p, q 1, x.

d. Caso contrário, (A[q] < x), retorne

RECURSIVE-BINARY-SEARCH (A, q + 1, r, x).

A chamada inicial é RECURSIVE-BINARY-SEARCH (A, 1, n, x).

Agora vamos ver como é que a busca binária leva tempo O(lg n) em um vetor de n elementos. A observação fundamental é que o tamanho r p + 1 do subvetor em consideração é dividido aproximadamente ao meio em cada iteração do laço (ou em cada chamada recursiva da versão recursiva, mas vamos focalizar a versão iterativa em BINARY-SEARCH). Se você tentar todos os casos constatará que, se uma iteração começa com um subvetor de s elementos, a próxima iteração terá     s /2 ou s/2 1 elementos, dependendo de s ser par ou ímpar e de A[q] ser maior ou menor que x. Já vimos uma vez que logo que o tamanho do subvetor chega a 1, o procedimento termina na próxima iteração. Portanto, podemos perguntar de quantas iterações do laço precisamos para dividir repetidamente ao meio um subvetor desde o seu tamanho original n até o tamanho 1. Isso seria o mesmo que o número de vezes que, começando com um subvetor de tamanho 1, precisaríamos para dobrar seu tamanho para chegar a um tamanho de n. Mas isso é apenas exponenciação: multiplicar repetidamente por 2. Em outras palavras, para qual valor de x 2x chega a n? Se n fosse uma potência exata de 2, já vimos na página 6 que a resposta seria lg n. É claro que n poderia não ser uma potência exata de 2, caso em que a resposta estaria dentro de 1 de lg n. Finalmente, observamos que cada iteração do laço leva uma quantidade de tempo constante, isto é, o tempo para uma única iteração não depende do tamanho n do vetor original ou do tamanho do subvetor sob consideração. Vamos usar notação assintótica para suprimir os fatores constantes e o termo de baixa ordem. (O número de iterações do laço é lg n ou

gn 11 ? Quem se importa?) Entendemos que o tempo de execução de busca binária é O(lg n).