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.