Introdução a Algoritmos

Um algoritmo é um conjunto de instruções que realizam uma tarefa.

Adaptado do livro: Entendendo Algoritmos: Um Guia Ilustrado Para Programadores e Outros Curiosos

Os algoritmos aqui apresentados são rápidos ou porque resolvem problemas interessantes, ou por ambos os motivos. A seguir estão descritos alguns pontos importantes que serão demonstrados.

Algoritmo de Pesquisa Binária

Vamos supor que você esteja procurando o nome de uma pessoa em uma agenda telefônica. O nome começa com K. Você pode começar na primeira página da agenda e ir folheando até chegar aos Ks. Porém você provavelmente vai começar pela metade, pois sabe que os Ks estarão mais perto dali.

Ou suponha que esteja procurando uma palavra que começa com O em um dicionário. Novamente, você começa a busca pelo meio.

Isto é um problema de busca. E todos estes casos usam um algoritmo para resolvê-lo: pesquisa binária.

A pesquisa binária é um algoritmo. Sua entrada é uma lista ordenada de elementos. Se o elemento que você está buscando está na lista, a pesquisa binária retorna a sua localização. Caso contrário, a pesquisa binária retorna None.

Por exemplo:

Procurando empresas em uma agenda com a pesquisa binária.

Eis um exemplo de como a pesquisa binária funciona. Estou pensando em um número entre 1 e 100.

Você deve procurar adivinhar o meu número com o menor número de tentativas possível. A cada tentativa, digo se você chutou muito para cima, muito para baixo ou corretamente.

Digamos que começou tentando assim: 1, 2, 3, 4… Veja como ficaria. É uma tentativa ruim de acertar o número.

Isso se chama pesquisa simples (talvez pesquisa estúpida seja um termo melhor). A cada tentativa, você está eliminando apenas um número. Se o meu número fosse o 99, você precisaria de 99 chances para acertá-lo.

Uma maneira melhor de busca. Comece com 50.

“Muito baixo”, mas você eliminou metade dos números. Agora, você sabe que os números de 1 a 50 são muito baixos. Próximo chute: 75.

você chuta um número intermediário e elimina a metade dos números restantes a cada vez.

“Muito alto”, mas novamente você pode cortar metade dos números restantes. Com a pesquisa binária, você chuta um número intermediário e elimina a metade dos números restantes a cada vez. O próximo número é o 63 (entre 50 e 75). Isso é a pesquisa binária. Você acaba de aprender um algoritmo. Aqui está a quantidade de números que você pode eliminar a cada tentativa.

Seja qual for o número que eu estiver pensando, você pode adivinhá-lo em um máximo de sete tentativas — porque a pesquisa binária elimina muitas possibilidades.

Suponha que você esteja procurando uma palavra em um dicionário. O dicionário tem 240.000 palavras. Na pior das hipóteses, de quantas etapas você acha que a pesquisa precisaria? A pesquisa simples poderia levar 240.000 etapas se a palavra que você estivesse procurando fosse a última do dicionário.

A cada etapa da pesquisa binária, você elimina o número de palavras pela metade até que só reste uma palavra.

Logo, a pesquisa binária levaria apenas 18 etapas — uma grande diferença. De maneira geral, para uma lista de n números, a pesquisa binária precisa de log2n para retornar o valor correto, enquanto a pesquisa simples precisa de n etapas.

Logaritmos

Você pode não se lembrar de logaritmos, mas provavelmente lembra-se de como calcular exponenciais. A expressão log10 100 basicamente diz: “Quantos 10s conseguimos multiplicar para chegar a 100?”.

A resposta é 2: 10 × 10. Então, log10 100 = 2. Logaritmos são o oposto de exponenciais.

Quando você procura um elemento usando a pesquisa simples, no pior dos casos, terá de analisar elemento por elemento, passando por todos. Se for uma lista de oito elementos, precisaria checar no máximo oito números.

Na pesquisa binária, precisa verificar log n elementos para o pior dos casos. Para uma lista de oito elementos, log 8 == 3, porque 23 == 8. Então, para uma lista de oito números, precisaria passar por, no máximo, três tentativas.

Para uma lista de 1.024 elementos, log 1.024 == 10, porque 2**4 == 1.024. Logo, para uma lista de 1.024 números, precisaria verificar no máximo dez deles.

Nota

A pesquisa binária só funciona quando a lista está ordenada. Por exemplo, os nomes em uma agenda telefônica estão em ordem alfabética, então você pode utilizar a pesquisa binária para procurar um nome. A cada tentativa, você testa para o elemento central da parte restante.

Tempo de execução

Geralmente, você escolhe o algoritmo mais eficiente — caso esteja tentando otimizar tempo e espaço.

Voltando à pesquisa simples, quanto tempo se otimiza utilizando-a? Bem, a primeira abordagem seria verificar número por número. Com a Pesquisa Simples, se fosse uma lista de 4 bilhões de números, precisaríamos de 4 bilhões de tentativas. Logo, o número máximo de tentativas é igual ao tamanho da lista. Isso é chamado de tempo linear.

Com a Pesquisa Binára, se a lista tem 4 bilhões de elementos, precisa-se de, no máximo, 32 tentativas. A pesquisa binária é executada com tempo logarítmico. A tabela a seguir resume as nossas descobertas até agora.

Notação Big O

O A notação Big O é uma notação especial que diz o quão rápido é um algoritmo. Mas quem liga para isso? Acontece que você frequentemente utilizará o algoritmo que outra pessoa fez — e quando faz isso, é bom entender o quão rápido ou lento o algoritmo é.

O algoritmo precisa ser tão rápido quanto correto. Por um lado, a pesquisa binária é mais rápida, o que é bom. Por outro lado, é mais fácil escrever a pesquisa simples, o que gera um risco menor de cometer erros.

O problema é que o tempo de execução da pesquisa simples e da pesquisa binária cresce com taxas diferentes.

Tempos de execução crescem com velocidades diferentes.

Sendo assim, conforme o número de itens cresce, a pesquisa binária aumenta só um pouco o seu tempo de execução. Já a pesquisa simples leva muito tempo a mais. Logo, conforme a lista de números cresce, a pesquisa binária se torna muito mais rápida do que a pesquisa simples. Não basta saber quanto tempo um algoritmo leva para ser executado — você precisa saber se o tempo de execução aumenta conforme a lista aumenta. É aí que a notação Big O entra.

A notação Big O informa o quão rápido é um algoritmo. Por exemplo, imagine que você tem uma lista de tamanho n. O tempo de execução na notação Big O é O(n). Onde estão os segundos? Eles não existem — a notação Big O não fornece o tempo em segundos.

A notação Big O permite que você compare o número de operações. Ela informa o quão rapidamente um algoritmo cresce.

Temos outro exemplo disso. A pesquisa binária precisa de log n operações para verificar uma lista de tamanho n. Qual é o tempo de execução na notação Big O? É O(log n). De maneira geral, a notação Big O é escrita da seguinte forma:

A notação Big O estabelece o tempo de execução para a pior hipótese

Suponha que você utiliza uma pesquisa simples para procurar o nome de uma pessoa em uma agenda telefônica. Você sabe que a pesquisa simples tem tempo de execução O(n), o que significa que na pior das hipóteses terá verificado cada nome da agenda telefônica. Nesse caso, você está procurando uma pessoa chamada Adit. Essa pessoa é a primeira de sua lista. Logo, não teve de passar por todos os nomes — você a encontrou na primeira tentativa. Esse algoritmo levou o tempo de execução O(n)? Ou levou O(1) porque encontrou o que queria na primeira tentativa?

A pesquisa simples ainda assim tem tempo de execução O(n). Nesse caso, você encontrou o que queria instantaneamente. Essa é a melhor das hipóteses. A notação Big O leva em conta a pior das hipóteses. Então pode-se dizer que, para o pior caso, você analisou cada item da lista. Esse é o tempo O(n). É uma garantia.

você sabe, com certeza, que a pesquisa simples nunca terá tempo de execução mais lento do que O(n).

Exemplos comuns de tempo de execução Big O

Aqui temos cinco tempos de execução Big O que você encontrará bastante, ordenados do mais rápido para o mais lento.

  • O(log n), também conhecido como tempo logarítmico. Exemplo: pesquisa binária.
  • O(n), conhecido como tempo linear. Exemplo: pesquisa simples.
  • O(n * log n). Exemplo: algoritmo rápido de ordenação, como a ordenação quicksort.
  • O(n2). Exemplo: algoritmo lento de ordenação, como a ordenação por seleção.
  • O(n!). Exemplo: um algoritmo bastante lento.

Contudo, mesmo a par desses detalhes, você não pode converter um tempo de execução na notação Big O para um número de operações.

Recapitulando

- A pesquisa binária é muito mais rápida do que a pesquisa simples.

- O(log n) é mais rápido do que O(n), e O(log n) fica ainda mais rápido conforme os elementos da lista aumentam.

- A rapidez de um algoritmo não é medida em segundos, mas pelo crescimento do número de operações realizadas.

- O tempo de execução de um algoritmo é medido por meio de seu crescimento.

- O tempo de execução dos algoritmos é expresso na notação Big O.

Obrigado.

Composing a repository of books (i bought), authors (i follow) & blogs (direct ones) for my own understanding.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store