Complexidade de Tempo dos Algoritmos

Recentemente, aprendi sobre a complexidade de algoritmos. Achei bem interessante e vim aqui compartilhar com vocês.

Saber sobre complexidade de algoritmo te permite saber a eficiência de um algoritmo em uma determinada situação sem antes mesmo executá-lo.
Algoritmos mais eficientes conseguem realizar tarefas com menos operações, o que é super importante quando lidamos com grandes conjuntos de dados.

ps: usarei Python para explicar alguns conceitos

Notação Big O

Começarei falando de forma bem rápida sobre Big O, o que é e pra que serve. Segundo o Wikipédia:

"A notação Big O é uma notação matemática que descreve o comportamento limitante de uma função quando o argumento tende a um valor específico ou ao infinito. Ela pertence a uma família de notações inventadas por Paul Bachmann, Edmund Landau e outros, coletivamente chamadas de notação Bachmann–Landau ou de notação assintótica."

Imagine que estamos em uma corrida de carros meio doida, onde cada carro representa um algoritmo. Agora, a pergunta é: quão rápido esses carros podem ir?

A notação Big O é como uma etiqueta que colocamos em cada um dos carros para mostrar quão rápido eles podem correr em diferentes situações. Mas, ao invés de medir velocidades em quilômetros por hora, medimos a eficiência de um algoritmo.

A ideia chave aqui é que essa notação Big O nos ajuda a entender quão rápido um algoritmo é em relação ao tamanho dos dados que é fornecido como entrada.

O que é complexidade de tempo?

Complexidade de tempo é sobre como o tempo de execução de um algoritmo aumenta à medida que a quantidade de dados de entrada cresce.

É importante lembrarmos que quando falamos em complexidade de tempo, não estamos nos referindo ao tempo exato de execução, mas sim à taxa de crescimento desse tempo em relação aos diferentes tamanhos de entrada que podemos fornecer.

Alice no país da Complexidade de tempo

Falar de complexidade de tempo dos algoritmos pode parecer um termo técnico e complicado, mas ele é fundamental para um desenvolvimento de software eficiente e otimizado. Antes de começar falar sobre complexidades, vou criar um cenário usando Alice no país das maravilhas que nos permitirá entender essa ideia de maneira mais compreensível.

Alice está com um grande problema e precisamos entender qual a forma mais eficiente de resolver.

O Chapeleiro Maluco trouxe alguns coelhos impostores com aparência idêntica ao do Coelho Branco para o país da Complexidade. Precisamos identificar quais deles são impostores e enviá-los de volta aos seus respectivos países!

O Coelho branco tem sempre um relógio guardado no bolso.

Alice teve algumas ideias de como resolver, vejamos:

1. Verificar individualmente cada coelho

Inicialmente, Alice considerou verificar cada um dos coelhos. Ela inspecionaria o bolso de cada um dos coelhos um de cada vez para verificar a presença de um relógio

def pega_coelho_impostor(coelhos):
    for coelho in coelhos:
        if not relogioNoBolso:
            print('o coelho é falso')

Neste caso, Alice examina cada coelho sequencialmente, conferindo se há um relógio em seu bolso. A complexidade de tempo é linear, representada como O(n), onde n é o número de coelhos. Cada coelho exige uma verificação, e o tempo total necessário para essa verificação é diretamente proporcional ao número de coelhos. Em outras palavras, quanto mais coelhos estiverem presentes, mais tempo será necessário para concluir as verificações.

2. Verificar todos os coelhos de uma só vez

Percebendo que a opção anterior seria demorada, Alice decidiu tentar algo diferente:

Ela decidiu reunir todos os coelhos, sacudi-los e observar se algum relógio cai. O coelho que for sacudido e cair um relógio seria o verdadeiro, os demais seriam impostores!

def pega_coelho_impostor(coelhos):
    juntar(coelhos) # Função fictícia para ilustração
    sacudir(coelhos) # Função fictícia para ilustração
    if caiuRelogio:
        print('Encontrou o Coelho Branco (o verdadeiro)')

Aqui, Alice reúne todos os coelhos de uma só vez, independentemente do número total de coelhos. Depois, ela os sacode e observa qual coelho deixa cair um relógio. Nessa abordagem, a complexidade de tempo é constante, representada como O(1), porque o tempo de execução permanece inalterado, independentemente do número de coelhos. Sejam 10 coelhos ou 20, o tempo de execução será o mesmo.

Complexidade quadrática

Agora, Alice precisa urgentemente devolver cada coelho impostor à sua casa, e ela recebeu uma lista com as localizações exatas de cada coelho impostor.

Ela precisa combinar os coelhos impostores e suas respectivas localizações, dessa forma ela consegue determinar onde cada um deles reside. Para isso, ela deve comparar cada coelho com cada localização da lista.

def levar_coelho_para_casa(coelhos_impostores, localizacoes):
    for coelho in coelhos_impostores:
        for localizacao in localizacoes:
            if verifica_localizacao(coelho) == localizacao:
                envia_para_casa()

# verifica_localizacao() é uma função fictícia para ilustração

Nessa função, cada coelho é comparado com todas as localizações usando dois loops "for". Para cada coelho, há uma iteração completa sobre a lista de localizações para realizar a comparação. Isso resulta em uma complexidade de tempo quadrática, representada como O(n^2), pois o tempo de execução aumenta quadraticamente com o aumento do número de coelhos.

Se tivesse 10 coelhos impostores e 10 locais para verificar, o número total de iterações seria 10 * 10 = 100, por exemplo.

Essa situação ilustra como a complexidade de tempo quadrática pode causar um aumento significativo no tempo de execução ao comparar elementos entre si.

Resumo das Complexidades:

• O(n) - Linear: O tempo de execução aumenta de forma constante à medida que a lista cresce. Exemplo: verificar itens um por um.
• O(1) - Constante: O tempo de execução permanece constante, independentemente do tamanho da lista.
• O(n^2) - Quadrática: O tempo de execução aumenta quadraticamente à medida que a lista cresce. Geralmente ocorre com dois loops aninhados.
• O(n^3) - Cúbica: O tempo de execução aumenta ainda mais rapidamente do que a complexidade quadrática. Comum em três loops aninhados, percorrendo a lista repetidamente.

Talvez você esteja assim:

E tá tudo bem! Primeiro: dê tempo a si mesmo, já que assimilar um conteúdo leva um tempinho, junto com a prática. A ideia é você ir adquirindo esse olhar mais atento ao escrever um algoritmo

Para finalizar, vamos falar sobre Complexidade Logarítmica.

Complexidade Logarítmica

Depois de resolver o problema de enviar os coelhos impostores de volta para casa, Alice se depara com um novo desafio: o Chapeleiro Maluco precisa de informações que apenas o coelho impostor com a idade de 32 anos possui. Para ajudar Alice em sua busca, o Chapeleiro pediu que os coelhos fossem organizados em uma fila em ordem crescente.

Busca binária

Para essa missão, Alice vai usar o método conhecido como Busca Binária para encontrar o coelho com exatamente 32 anos de idade.

O procedimento é simples: com todos os coelhos alinhados, Alice começa perguntando a idade do coelho do meio e a compara com a idade desejada. Se o coelho questionado tiver exatamente 32 anos, Alice terá encontrado o coelho que procura, podendo assim informar ao Chapeleiro Maluco.

No entanto, ao observarmos a imagem acima, notamos que o coelho do meio possui 26 anos, o que é menor do que a idade buscada. Nesse caso, Alice precisará concentrar-se na metade direita da fila, onde as idades são maiores.

Caso contrário, se o coelho do meio tiver mais de 32 anos, Alice entenderá que precisa concentrar-se na metade esquerda da fila, onde as idades são menores.

Pegando a lista da direta, temos os coelhos com as seguintes idades:

29 - 32 - 50

Ao dividirmos essa lista pela metade, encontramos o número 32. Parece que Alice finalmente encontrou o coelho com 32 anos.

E se, por exemplo, Alice estivesse buscando o coelho de 50 anos?

Nesse caso, ela continuaria repetindo esse processo de dividir a fila de coelhos pela metade e escolher a metade apropriada até encontrar a idade desejada ou até perceber que nenhum coelho possui aquela idade.

Conclusão:

Nesse contexto, a complexidade de tempo torna-se logarítmica, pois a cada iteração, Alice reduz pela metade o número de coelhos cujas idades precisam ser verificadas. Isso resulta em um processo de busca muito mais eficiente em comparação com uma abordagem linear, na qual Alice teria que verificar a idade de cada coelho individualmente.

Preciso necessariamente saber o que é função logarítmica para entender isso?

Não necessariamente. Compreender sobre função logarítmica pode aprofundar ainda mais o seu entendimento sobre a complexidade de tempo, mas não é algo essencial para entender os conceitos básicos de complexidade de tempo e como ela se aplica a algoritmos.

👀 Dica: Depois da uma olhada nesse gráfico de complexidade do site bigocheatsheet.

Espero ter ajudado! 😊

bjs bjs e até a próxima 💟