Introdução a algoritmos — Notação Big O

Irei escrever sobre algoritmos e estruturas de dados em paralelo com o livro Entendendo Algoritmos: Um Guia Ilustrado Para Programadores e Outros Curiosos de Aditya Y. Bhargava.

Estou usando o livro para aprender sobre algoritmos e estruturas de dados, e escrever sobre o que estou aprendendo, pois acredito que assim eu consiga fixar melhor o conteúdo.

Capítulo 1 — Introdução a algoritmos

Notação Big O

A notação Big O é usada para descrever a complexidade de um algoritmo. Ela é usada para descrever o pior caso de um algoritmo, ou seja, o caso em que ele vai demorar mais para ser executado.

Com essa notação, podemos comparar a complexidade de dois algoritmos e dizer qual deles é mais eficiente.

O que é complexidade de um algoritmo?

A complexidade de um algoritmo é uma medida da quantidade de tempo e espaço que ele usa para executar.

Vale lembrar que a eficiência de um algoritmo não é medida em segundos, mas sim em operações. Por exemplo, se um algoritmo demora 1 segundo para executar, mas usa 10 operações, ele é mais eficiente que um algoritmo que demora 1 segundo para executar, mas usa 1000 operações.

Exemplos do livro

No livro, o autor dá alguns exemplos de algoritmos e como eles são descritos usando a notação Big O.

Um dos exemplos é o algoritmo de busca linear, usado para procurar um elemento em um array. Ele é descrito como O(n), onde n é o tamanho do array.

Outro exemplo é o algoritmo de busca binária, usado para procurar um elemento em um array ordenado. Ele é descrito como O(log n), onde n é o tamanho do array.

Para saber mais sobre pesquisa binária, veja o meu post sobre o assunto: pesquisa binária.

Tempo de execução de um algoritmo

O tempo de execução de um algoritmo é a quantidade de tempo que ele leva para ser executado.

Tempo de execução difere de complexidade de um algoritmo. A complexidade de um algoritmo é uma medida da quantidade de tempo e espaço que ele usa para executar. Já o tempo de execução é a quantidade de tempo que ele leva para ser executado.

O tempo de execução cresce a taxas diferentes para diferentes algoritmos.

Por exemplo, o tempo de execução de um algoritmo de busca linear cresce linearmente, enquanto o tempo de execução de um algoritmo de busca binária cresce logaritmicamente.

Vamos ver isso em gráficos:

Gráfico de tempo de execução de um algoritmo de busca linear

Gráfico de tempo de execução de um algoritmo de busca binária

Créditos das Imagens: 101computing.net

Podemos ver que o tempo de execução de um algoritmo de busca linear cresce linearmente, enquanto o tempo de execução de um algoritmo de busca binária cresce logaritmicamente.

Mas o que isso significa?

Quando falamos que o tempo de execução de um algoritmo cresce linearmente, queremos dizer que o tempo de execução do algoritmo aumenta conforme o tamanho do input.

Vou usar um exemplo do livro para explicar isso.

Em uma lista com 100 elementos, o algoritmo de busca linear vai precisar percorrer todos os 100 elementos para encontrar o elemento que estamos procurando. Já em uma lista com 1000 elementos, o algoritmo de busca linear vai precisar percorrer todos os 1000 elementos para encontrar o elemento que estamos procurando.

Ou seja, o tempo de execução do algoritmo de busca linear cresce linearmente conforme o tamanho do input.

Já quando falamos que o tempo de execução de um algoritmo cresce logaritmicamente, queremos dizer que o tempo de execução do algoritmo aumenta conforme o tamanho do input, mas de forma mais lenta.

Em uma lista com 100 elementos, o algoritmo de busca binária vai precisar percorrer 7 elementos para encontrar o elemento que estamos procurando. Já em uma lista com 1000 elementos, o algoritmo de busca binária vai precisar percorrer 10 elementos para encontrar o elemento que estamos procurando.

Ou seja, o tempo de execução do algoritmo de busca binária cresce logaritmicamente conforme o tamanho do input.

Se formos considerar que leva um 1ms para percorrer um elemento, podemos ver que o algoritmo de busca linear leva 100ms para percorrer uma lista com 100 elementos, enquanto o algoritmo de busca binária leva 7ms para percorrer uma lista com 100 elementos.

Viu como o algoritmo de busca binária é mais eficiente que o algoritmo de busca linear?

Tipos de algoritmos e suas complexidades

Já vimos dois exemplos de algoritmos e suas complexidades: o algoritmo de busca linear e o algoritmo de busca binária.

O algoritmo de busca linear é descrito como O(n), onde n é o tamanho do array. Já o algoritmo de busca binária é descrito como O(log n), onde n é o tamanho do array.

Vamos ver mais alguns exemplos de algoritmos e suas complexidades:

O(1) — Constante

O algoritmo com complexidade O(1) é um algoritmo que sempre vai executar o mesmo número de operações, independente do tamanho do input.

Um exemplo de algoritmo com complexidade O(1) é o algoritmo de busca sequencial, usado para procurar um elemento em um array.

O gráfico abaixo mostra o tempo de execução do algoritmo de busca sequencial:

Gráfico de tempo de execução de um algoritmo de busca sequencial

Créditos da Imagem: 101computing.net

Como podemos ver, o tempo de execução do algoritmo de busca sequencial é constante, independente do tamanho do input.

O(n2) — Quadrático

O algoritmo com complexidade O(n2) é um algoritmo que vai executar o número de operações igual ao quadrado do tamanho do input.

Um exemplo de algoritmo com complexidade O(n2) é o algoritmo de ordenação por seleção, usado para ordenar um array.

O gráfico abaixo mostra o tempo de execução do algoritmo de ordenação por seleção:

Gráfico de tempo de execução de um algoritmo de ordenação por seleção

Créditos da Imagem: 101computing.net

Como podemos ver, o tempo de execução do algoritmo de ordenação por seleção cresce quadraticamente, ou seja, o tempo de execução do algoritmo de ordenação por seleção é igual ao quadrado do tamanho do input.

O(2n) — Exponencial

O algoritmo com complexidade O(2n) é um algoritmo que vai executar o número de operações igual a 2 elevado ao tamanho do input.

Um exemplo de algoritmo com complexidade O(2n) é o algoritmo de busca exaustiva, usado para procurar um elemento em um array.

O gráfico abaixo mostra o tempo de execução do algoritmo de busca exaustiva:

Gráfico de tempo de execução de um algoritmo de busca exaustiva

Créditos da Imagem: 101computing.net

Como podemos ver, o tempo de execução do algoritmo de busca exaustiva cresce exponencialmente, ou seja, o tempo de execução do algoritmo de busca exaustiva é igual a 2 elevado ao tamanho do input.

Caixeiro Viajante

Um problema muito comum em algoritmos é o problema do caixeiro viajante, sendo um problema de otimização.

O problema do caixeiro viajante é um problema em que temos um conjunto de cidades e queremos encontrar a rota mais curta para visitar todas as cidades uma única vez e voltar para a cidade de origem.

Vamos ver um exemplo de problema do caixeiro viajante:

Problema do caixeiro viajante

Créditos da Imagem: optimoroute.com

Como podemos ver, temos um conjunto de cidades e queremos encontrar a rota mais curta para visitar todas as cidades uma única vez e voltar para a cidade de origem.

Uma solução para esse problema seria percorrer todas as cidades e calcular a distância entre elas, e depois escolher a rota com a menor distância.

Seguindo do princípio que teríamos somente 5 cidades, teríamos 5! = 120 combinações possíveis de rotas.

Mas se tivéssemos 6 cidades, teríamos 6! = 720 combinações possíveis de rotas.

Esse problema é chamado de problema de otimização combinatória, pois temos um conjunto de combinações possíveis e queremos encontrar a melhor combinação.

Segue a tabela com o número de combinações possíveis para cada número de cidades:

Como podemos ver, o número de combinações possíveis cresce exponencialmente, ou seja, o número de combinações possíveis é igual a 2 elevado ao número de cidades.

Como o número de combinações possíveis cresce exponencialmente, não é possível calcular todas as combinações possíveis para um número grande de cidades.

Esse problema é chamado de problema NP-Completo, sendo um problema que não é possível calcular todas as combinações possíveis.

Dessa forma, não é possível encontrar a melhor solução para esse problema, mas podemos encontrar uma solução aproximada para esse problema.

Deixei esse problema para o final, por ser um problema que é muito comum em algoritmos e gera muita curiosidade pela sua complexidade.

Finalização

Essa foi uma pequena documentação dos meus estudos, espero que possa ajudar mais pessoas.
Qualquer dúvida, correção ou sugestão pode deixar nos comentários.