Seja bem-vindo, Padawan! Hoje vamos embarcar em uma jornada para entender um conceito essencial na programação e na resolução de problemas computacionais: a Complexidade Assintótica. Apesar do nome complicado, prometo que nós vamos simplificar isso para que você se sinta um mestre Jedi em pouco tempo.
O que é Complexidade Assintótica?
Em termos simples, a complexidade assintótica serve para medir como o desempenho de um algoritmo muda conforme o tamanho do problema cresce. Pense assim: se você tem uma lista pequena para ordenar, talvez até um algoritmo ineficiente seja rápido. Mas e se você tiver uma lista com milhões de elementos? Aí entra a complexidade assintótica, que nos ajuda a prever como o tempo de execução ou o uso de memória vai escalar.
Big-O: O Guardião do Crescimento
O Big-O é a notação que usamos para descrever a complexidade assintótica. Ela nos diz, no pior caso, como o algoritmo se comporta. Aqui estão algumas das notações mais comuns:
- O(1): Tempo constante. Embora o algoritmo execute vários passos, o número deles é sempre fixo, independente do tamanho da entrada.
- O(n): Tempo linear. O algoritmo percorre todos os n elementos da entrada no pior caso.
- O(log n): Tempo logarítmico. A cada passo, reduzimos o problema pela metade.
- O(n²): Tempo quadrático. O número de operações cresce ao quadrado do tamanho da entrada.
- O(n log n): Tempo linearítmico. Combina um crescimento linear com logarítmico, comum em algoritmos de ordenação eficientes.
Um Exemplo Prático com Código
Vamos ilustrar isso com um exemplo de código em Python simples para você. Ah, e vou deixar em texto o código, caso queira rodar em algum interpretador online ou no seu compilador. Imagine que queremos verificar se um número está presente em uma lista:
# O(n) – Complexidade Linear
def busca_linear(lista, alvo):
for elemento in lista:
if elemento == alvo:
return True
return False
# Testando
numeros = [1, 3, 5, 7, 9]
print(busca_linear(numeros, 5)) # Saída: True
Aqui, o algoritmo percorre a lista elemento por elemento. Se a lista tiver 10 elementos, ele pode fazer até 10 comparações no pior caso.
E se Melhorarmos?
Agora, imagine que a lista está ordenada. Podemos usar a busca binária, que é muito mais eficiente:
# O(log n) – Complexidade Logarítmica
def busca_binaria(lista, alvo):
inicio = 0
fim = len(lista) – 1
while inicio <= fim:
meio = (inicio + fim) // 2
if lista[meio] == alvo:
return True
elif lista[meio] < alvo:
inicio = meio + 1
else:
fim = meio – 1
return False
# Testando
numeros = [1, 3, 5, 7, 9]
print(busca_binaria(numeros, 5)) # Saída: True
Na busca binária, a cada iteração dividimos a lista pela metade, reduzindo o número de elementos a serem verificados. Isso justifica a complexidade O(log n).
Ordenação com O(n log n)
Algoritmos como o Merge Sort têm uma complexidade O(n log n) porque dividem o problema em partes menores (log n) e depois processam cada parte (n):
# O(n log n) – Complexidade Linearítmica
def merge_sort(lista):
if len(lista) > 1:
meio = len(lista) // 2
esquerda = lista[:meio]
direita = lista[meio:]
merge_sort(esquerda)
merge_sort(direita)
i = j = k = 0
while i < len(esquerda) and j < len(direita):
if esquerda[i] < direita[j]:
lista[k] = esquerda[i]
i += 1
else:
lista[k] = direita[j]
j += 1
k += 1
while i < len(esquerda):
lista[k] = esquerda[i]
i += 1
k += 1
while j < len(direita):
lista[k] = direita[j]
j += 1
k += 1
# Testando
numeros = [38, 27, 43, 3, 9, 82, 10]
merge_sort(numeros)
print(numeros) # Saída: [3, 9, 10, 27, 38, 43, 82]
O Merge Sort divide a lista em sublistas menores (log n) e depois as combina em ordem (n), resultando na complexidade O(n log n).
Lidando com O(n²)
Alguns algoritmos, como o Bubble Sort, têm uma complexidade de O(n²). Veja como ele funciona:
# O(n²) – Complexidade Quadrática
def bubble_sort(lista):
n = len(lista)
for i in range(n):
for j in range(0, n-i-1):
if lista[j] > lista[j+1]:
lista[j], lista[j+1] = lista[j+1], lista[j]
# Testando
numeros = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(numeros)
print(numeros) # Saída: [11, 12, 22, 25, 34, 64, 90]
Embora seja fácil de entender, o Bubble Sort é muito lento para listas grandes. Ele compara cada elemento com todos os outros, resultando em um número de operações proporcional a n².
Questões
Agora é a parte que interessa, vamos colocar em prática o que vimos! Que a força esteja com você!
IBFC – 2024 – IMBEL – Analista Especializado – Analista de Sistemas
O algoritmo MERGE SORT emprega a técnica “divisão e conquista” para ordenar uma lista de valores. A ordem de complexidade deste algoritmo, no pior caso, é:
(A) O(n)
(B) O(n log n)
(C) O(2n)
(D) O(n/2)
(E) O(3n)
A resposta correta é (B) O(n log n).
O Merge Sort utiliza a técnica de “divisão e conquista”. Ele divide a lista em partes menores até chegar em listas com um único elemento (log n divisões) e, em seguida, combina (ou conquista) as partes ordenadas de maneira linear (n operações para cada nível de divisão). Assim, no pior caso, sua complexidade é O(n log n).
FGV – 2023 – TJ-RN – Analista Judiciário – Tecnologia da Informação – Análise de Sistemas
Numa busca por uma chave armazenada numa lista encadeada circular, cujos elementos estão dispostos ordenadamente pelo valor da chave, a complexidade do algoritmo no pior caso é:
(A) 1;
(B) N;
(C) log N;
(D) N log N;
(E) N².
A resposta correta é (B) N.
Uma lista encadeada circular não permite acesso direto a elementos pelo índice, como acontece com arrays. Mesmo que os elementos estejam ordenados, o algoritmo precisa percorrer, no pior caso, todos os N elementos da lista para encontrar a chave desejada. Isso resulta em uma complexidade O(N).
FCC – 2022 – TRT – 14ª Região (RO e AC) – Analista Judiciário – Tecnologia da Informação
Usando a notação Big-O para representar o custo computacional, é correto afirmar que o tempo de execução da busca binária nunca é pior que:
(A) O(n)
(B) O(log2n)
(C) O(n/2)
(D) O(2ⁿ)
(E) O(n³)
A resposta correta é (B) O(log2n).
A busca binária é um algoritmo que funciona dividindo repetidamente o conjunto de dados ao meio até encontrar o elemento desejado ou determinar que ele não está presente. A cada passo, o tamanho do conjunto é reduzido pela metade. Essa característica faz com que o número de passos seja proporcional ao logaritmo do número de elementos na entrada.
Conclusão
Padawan, agora você entende como medir e comparar a eficiência de algoritmos. Seja no mundo real ou em provas de concurso, conhecer a complexidade assintótica é um superpoder. Continue praticando e logo você será o mestre Jedi dos algoritmos!
Quer ficar por dentro dos concursos públicos abertos e previstos pelo Brasil? Clique nos links abaixo:
Receba gratuitamente no seu celular as principais notícias do mundo dos concursos. Clique no link abaixo e inscreva-se:
Participe da conversa