Hoje, vamos falar sobre um conceito fundamental em ciência da computação e análise de algoritmos: a notação Big O. Se você já teve contato com programação ou estudos relacionados, provavelmente já ouviu falar sobre esse termo. Mas o que exatamente ele significa e por que é tão importante? Vamos descobrir juntos!

A notação Big O é uma forma de descrever a complexidade de um algoritmo, ou seja, a medida de quanta memória ou tempo computacional ele requer à medida que o tamanho da entrada aumenta. É uma ferramenta essencial para analisar e comparar algoritmos, permitindo-nos escolher a melhor solução para um determinado problema.

"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." — Definição da Wikipédia de notação Big O

Ao utilizar a notação Big O, expressamos a eficiência de um algoritmo em termos de seu crescimento assintótico. Em outras palavras, estamos interessados no comportamento do algoritmo quando a quantidade de dados aumenta consideravelmente. A notação Big O nos permite identificar o crescimento mais significativo em relação ao tamanho da entrada e descrevê-lo de forma simplificada.

Você pode perguntar: mas quem liga para isso?. Bem, acontece que você frequentemente utilizará o algoritmo feitos por outras pessoas, e quando faz isso, é bom entender o quão rápido ou lento o algoritmo é.

Para exemplificar o que é a notação Big O, vamos dar uma olhada em um caso típico, O(n²), que geralmente é chamada também de "Big O quadrática". A letra n representa o tamanho da entrada, enquanto a função "g(n) = n²" interna ao "O()" nos dá a ideia da complexidade do algoritmo em relação ao tamanho da entrada.

Outro exemplo é da pesquisa binária, que precisa de log n operações para verificar uma lista de tamanho n. A complexidade desse algoritmo é da ordem de O(log2 n), em que n é o tamanho do vetor de busca.

Vamos examinar alguns exemplos comuns de notações Big O:

• O(1): Tempo de execução constante: Independentemente do tamanho da entrada, o algoritmo sempre leva o mesmo tempo para ser executado. É o cenário ideal, onde a eficiência não é afetada pelo aumento dos dados.

• O(log n): Tempo de execução logarítmico: O tempo de execução aumenta de forma logarítmica à medida que o tamanho da entrada aumenta. Algoritmos com essa complexidade são geralmente muito eficientes, como é o caso de árvores balanceadas e algoritmos de busca binária.

• O(n): Tempo de execução linear: O tempo de execução cresce proporcionalmente ao tamanho da entrada. Algoritmos lineares percorrem cada elemento da entrada uma vez. Exemplos incluem busca linear e algumas formas de ordenação.

• O(n * log n): Exemplo: um algoritmo rápido de ordenação, como a ordenação quicksort.

• O(n^2): Tempo de execução quadrático: O tempo de execução é o quadrado do tamanho da entrada. Algoritmos com essa complexidade são menos eficientes e podem levar muito tempo para processar grandes conjuntos de dados. Exemplos comuns são algoritmos de ordenação como o Bubble Sort e o Insertion Sort.

• O(n!): Exemplo: um algoritmo bastante lento, como o do caixeiro-viajante.

Esses são apenas alguns exemplos das muitas possibilidades da notação Big O. Existem notações mais complexas, como O(n log n) e O(2^n), que descrevem algoritmos com diferentes níveis de eficiência. É importante lembrar que a notação Big O descreve o pior caso possível de um algoritmo e nos dá uma visão geral de sua eficiência relativa.

Ao analisar algoritmos e escolher a melhor abordagem para um problema, é fundamental considerar a complexidade temporal e espacial. Um algoritmo com complexidade O(n) pode ser mais eficiente do que um algoritmo com complexidade O(log n), dependendo do contexto e dos requisitos do problema.

Algoritmos e suas respectivas notações Big O:

1 - Busca linear: Este algoritmo percorre todos os elementos de uma lista até encontrar o elemento desejado ou chegar ao final da lista.

• Tempo de execução: O(n)

• Descrição: O tempo de execução aumenta linearmente com o tamanho da entrada, pois cada elemento precisa ser verificado.

2 - Busca binária: Este algoritmo é aplicável apenas a listas ordenadas. Ele divide repetidamente a lista ao meio e verifica se o elemento desejado está na metade esquerda ou direita.

• Tempo de execução: O(log n)

• Descrição: O tempo de execução cresce logaritmicamente com o tamanho da entrada, pois a lista é dividida pela metade a cada iteração.

3 - Ordenação por Bubble Sort: Neste algoritmo de ordenação, os elementos são comparados em pares e trocados se estiverem fora de ordem. O processo se repete até que a lista esteja ordenada.

• Tempo de execução: O(n^2)

• Descrição: O tempo de execução é quadrático em relação ao tamanho da entrada, pois são necessárias iterações múltiplas e cada elemento pode precisar ser comparado com todos os outros.

4 - Ordenação por Merge Sort: Este é um algoritmo de ordenação baseado em dividir para conquistar. A lista é dividida em sublistas menores, ordenadas separadamente e, em seguida, mescladas para obter a lista final ordenada.

• Tempo de execução: O(n log n)

• Descrição: O tempo de execução cresce em uma taxa logarítmica com o tamanho da entrada para dividir as sublistas e, em seguida, linearmente com o tamanho da entrada para mesclá-las.

5 - Cálculo da soma de uma lista de números: Este algoritmo simples percorre uma lista de números e calcula a soma total.

• Tempo de execução: O(n)

• Descrição: O tempo de execução é linear em relação ao tamanho da entrada, pois cada elemento da lista precisa ser visitado uma vez.

6 - Busca em uma tabela de dispersão (hash table): Ao procurar um elemento em uma tabela de dispersão, a função hash é aplicada para determinar sua posição na tabela.

• Tempo de execução médio (em caso ideal): O(1)

• Descrição: O tempo de execução é constante, independentemente do tamanho da entrada, desde que não ocorram muitas colisões.

Problema do caixeiro viajante

O problema do caixeiro viajante é um desafio clássico de otimização combinatória, em que o objetivo é encontrar o menor caminho possível que passe por todas as cidades (ou pontos) visitando cada uma delas exatamente uma vez e retornando à cidade de origem.

A complexidade do problema do caixeiro viajante depende da abordagem utilizada para resolver o problema. Existem diferentes algoritmos para isso, e vou apresentar dois exemplos com suas respectivas notações Big O:

1 - Força bruta (Brute Force):

• Tempo de execução: O(n!)

• Descrição: O tempo de execução cresce fatorialmente com o número de cidades. Esse algoritmo testa todas as permutações possíveis das cidades para encontrar o caminho mais curto.

2 - Algoritmo heurístico (Algoritmo do vizinho mais próximo):

• Tempo de execução: O(n^2)

• Descrição: Neste algoritmo, cada cidade é visitada a partir da cidade atual escolhendo a cidade vizinha mais próxima que ainda não foi visitada. O tempo de execução é quadrático em relação ao número de cidades, pois em cada iteração é necessário encontrar a cidade mais próxima.

A Big O estabelece o pior caso para o tempo de execução

Vamos imaginar que você queira encontrar um nome em um lista ordenada e para isso vamos usar uma busca simples para percorrer. Um busca simples tem uma complexidade de O(n) vezes para ser executada, isso quer dizer que, no pior caso, terá que examinar cada registro até um determinado nome. Vamos supor que temos que buscar o nome Adriano se ele for o primeiro da lista então levará O(1) agora se o nome for o _Zairro _sendo o ultimo da lista temos O(n) sendo o pior caso.

Neste caso, O(1) é o melhor cenário, teve a sorte de achar Adriano no começo da lista. Mas a notação Big O leva em conta o pior dos casos, que é O(n) então a complexidade do algoritmo de busca simples é de O(n). É uma reafirmação de que a busca simples nunca será mais lenta que O(n).

Conclusão

Em resumo, a notação Big O é uma ferramenta poderosa para medir a eficiência dos algoritmos, permitindo-nos comparar e selecionar a melhor solução para um determinado problema. Compreender e utilizar corretamente a notação Big O é essencial para os desenvolvedores de software, pois nos ajuda a escrever algoritmos eficientes e otimizados.

Espero que esta postagem tenha sido útil para vocês! Se tiverem mais dúvidas sobre a notação Big O ou qualquer outro tópico relacionado à ciência da computação, fiquem à vontade para perguntar.

Fontes:

Grande-O - wikipedia
Notação Big-O
Quantum Computing in Complexity Theory and Theory of Computation
Know Thy Complexities!
Definição da notação "Big O"
Pesquisa binária
A Busca Binária
Busca Linear
Problema do Caixeiro Viajante
Problema do caixeiro-viajante - wikipedia