Pular para o conteúdo principal

Algoritmos

· Leitura de 10 minutos

Pense em algoritmos como instruções para resolver problemas. Esses problemas podem ser resolvidos de várias formas, mas existem formas melhores que gastam menos tempo, menos repetição e exigem menos trabalho.

E cada algoritmo tem seu melhor caso de uso, ou seja, o melhor lugar onde pode ser usado.

Ordenação​

Bubble Sort​

Prós ✅

  1. Fácil de implementar: O algoritmo é direto e ideal para ensinar conceitos de ordenação.

  2. Ordenação in-place: Requer apenas uma quantidade constante de memória adicional $O(1)$.

  3. Ordenação estável: Mantém a ordem relativa de elementos iguais, o que é útil em certas aplicações.

  4. Otimização possível para melhor caso: Com uma condição de saída antecipada (quando não ocorrem trocas), pode ter desempenho O(n) para dados quase ordenados.

Contras ❌

  1. Muito ineficiente para grandes conjuntos de dados: Possui complexidade de tempo média e pior caso de O(n²), tornando-o impraticável para listas grandes.

  2. Muitas trocas: Realiza mais trocas do que o necessário comparado a algoritmos mais eficientes como insertion sort ou quicksort.

  3. Não adaptativo por padrão: Sem otimização, sempre percorre todas as iterações mesmo se a lista ficar ordenada prematuramente.

  4. Raramente usado na prática: Existem algoritmos com melhor desempenho como Merge Sort, Quick Sort e Tim Sort usados em aplicações reais.

info

Pior caso: O(n²) | Melhor caso: O(n)

Youtube - Bubble Sort por Michael Sambol

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

sorted_arr = bubble_sort([64, 34, 25, 12, 22, 11, 90])

print(sorted_arr)

Insertion Sort​

Prós ✅

  1. Simples e intuitivo: O algoritmo é fácil de entender e implementar.

  2. Melhor desempenho no melhor caso: Pode atingir complexidade de tempo O(n) para dados quase ordenados.

  3. Ordenação estável: Mantém a ordem relativa de elementos iguais, o que é útil em certas aplicações.

Contras ❌

  1. Muito ineficiente para grandes conjuntos de dados: Possui complexidade de tempo média e pior caso de O(n²), tornando-o impraticável para listas grandes.

  2. Não adaptativo por padrão: Sem otimização, sempre percorre todas as iterações mesmo se a lista ficar ordenada prematuramente.

  3. Raramente usado na prática: Existem algoritmos com melhor desempenho como Merge Sort, Quick Sort e Tim Sort usados em aplicações reais.

info

Pior caso: O(n²) | Melhor caso: O(n)

Youtube - Insertion Sort por Michael Sambol

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

sorted_arr = insertion_sort([64, 34, 25, 12, 22, 11, 90])

print(sorted_arr)

Merge Sort​

Prós ✅

  1. Ordenação estável: Mantém a ordem relativa de elementos iguais, o que é útil em certas aplicações.

  2. Melhor desempenho no melhor caso: Pode atingir complexidade de tempo O(n) para dados quase ordenados.

  3. Não adaptativo por padrão: Sem otimização, sempre percorre todas as iterações mesmo se a lista ficar ordenada prematuramente.

Contras ❌

  1. Não é ordenação in-place: Requer memória adicional proporcional ao tamanho do array de entrada.

  2. Não adaptativo por padrão: Sem otimização, sempre percorre todas as iterações mesmo se a lista ficar ordenada prematuramente.

info

Pior caso: O(n log n) | Melhor caso: O(n log n)

Youtube - Algoritmo Merge Sort por Michael Sambol

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

sorted_arr = merge_sort([64, 34, 25, 12, 22, 11, 90])

print(sorted_arr)

Ordenação Rápida​

Prós ✅

  1. Melhor desempenho no melhor caso: Pode atingir complexidade de tempo O(n) para dados quase ordenados.

  2. Ordenação in-place: Requer apenas uma quantidade constante de memória adicional $O(1)$.

  3. Não adaptativo por padrão: Sem otimização, sempre percorre todas as iterações mesmo se a lista ficar ordenada prematuramente.

Contras ❌

  1. Não é estável por padrão: Elementos iguais podem ser reordenados, o que não é útil em certas aplicações.

  2. Não adaptativo por padrão: Sem otimização, sempre percorre todas as iterações mesmo se a lista ficar ordenada prematuramente.

info

Pior caso: O(n²) | Melhor caso: O(n log n)

Youtube - Algoritmo Quick Sort por Michael Sambol

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

sorted_arr = quick_sort([64, 34, 25, 12, 22, 11, 90])

print(sorted_arr)

Busca​

Busca Linear​

Prós ✅

  1. Simples e intuitivo: O algoritmo é fácil de entender e implementar.

  2. Melhor desempenho no melhor caso: Pode atingir complexidade de tempo O(n) para dados quase ordenados.

Contras ❌

  1. Muito ineficiente para grandes conjuntos de dados: Possui complexidade de tempo média e pior caso de O(n²), tornando-o impraticável para listas grandes.

  2. Não adaptativo por padrão: Sem otimização, sempre percorre todas as iterações mesmo se a lista ficar ordenada prematuramente.

info

Pior caso: O(n) | Melhor caso: O(1)

Youtube - Algoritmo de Busca Linear por Bro Code

def linear_search(arr, target):
    for i, value in enumerate(arr):
        if value == target:
            return i
    return -1

target = 25

index = linear_search([64, 34, 25, 12, 22, 11, 90], target)

print(index)

Busca Binária​

Prós ✅

  1. Melhor desempenho no melhor caso: Pode atingir complexidade de tempo O(n) para dados quase ordenados.

  2. Ordenação in-place: Requer apenas uma quantidade constante de memória adicional $O(1)$.

Contras ❌

  1. Não é estável por padrão: Elementos iguais podem ser reordenados, o que não é útil em certas aplicações.

  2. Não adaptativo por padrão: Sem otimização, sempre percorre todas as iterações mesmo se a lista ficar ordenada prematuramente.

info

Pior caso: O(log n) | Melhor caso: O(1)

Youtube - Busca Binária por Michael Sambol

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

target = 25

index = binary_search([64, 34, 25, 12, 22, 11, 90], target)

print(index)

Recursão​

Prós ✅

  1. Simples e intuitivo: O algoritmo é fácil de entender e implementar.

  2. Melhor desempenho no melhor caso: Pode atingir complexidade de tempo O(n) para dados quase ordenados.

Contras ❌

  1. Não é estável por padrão: Elementos iguais podem ser reordenados, o que não é útil em certas aplicações.

  2. Não adaptativo por padrão: Sem otimização, sempre percorre todas as iterações mesmo se a lista ficar ordenada prematuramente.

info

Pior caso: O(n) | Melhor caso: O(1)

Youtube - Recursão em 100 segundos por Fireship

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

result = factorial(5)

print(result)

BFS (Busca em Largura)​

A Busca em Largura (BFS - Breadth-First Search) é um algoritmo para percorrer ou pesquisar estruturas de dados em árvore ou grafo. Ele começa no nó raiz e explora todos os nós vizinhos no nível atual antes de se mover para os nós do próximo nível.

Prós ✅

  1. Completo: Garante encontrar o caminho mais curto em grafos não ponderados.

  2. Ótimo para grafos não ponderados: Encontra o caminho com menor número de arestas.

  3. Simples de implementar: Usa uma estrutura de dados de fila (queue).

Contras ❌

  1. Uso de memória: Pode consumir muita memória em grafos muito grandes.

  2. Não é ideal para caminhos longos: Pode ser ineficiente quando o caminho é muito longo.

info

Complexidade de tempo: O(V + E) | Complexidade de espaço: O(V)

Youtube - BFS por William Fiset

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    
    while queue:
        vertex = queue.popleft()
        print(vertex, end=' ')
        
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# Exemplo de uso
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

bfs(graph, 'A')

DFS (Busca em Profundidade)​

A Busca em Profundidade (DFS - Depth-First Search) é um algoritmo para percorrer ou pesquisar estruturas de dados em árvore ou grafo. Ele explora o máximo possível ao longo de cada ramo antes de retroceder.

Prós ✅

  1. Eficiente em memória: Usa menos memória que BFS em grafos muito grandes.

  2. Bom para caminhos longos: Pode ser mais eficiente quando o caminho é muito longo.

  3. Útil para backtracking: Ideal para problemas que requerem backtracking.

Contras ❌

  1. Não garante o caminho mais curto: Pode não encontrar o caminho mais curto em grafos não ponderados.

  2. Pode ficar preso em ciclos: Requer marcação de nós visitados para evitar ciclos infinitos.

info

Complexidade de tempo: O(V + E) | Complexidade de espaço: O(V)

Youtube - DFS por William Fiset

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    
    visited.add(start)
    print(start, end=' ')
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

# Exemplo de uso
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

dfs(graph, 'A')

Algoritmo de Dijkstra​

O algoritmo de Dijkstra é um algoritmo para encontrar o caminho mais curto entre dois vértices em um grafo com arestas de peso não negativo.

Prós ✅

  1. Garante o caminho mais curto: Encontra o caminho com menor peso total.

  2. Eficiente: Usa uma fila de prioridade para otimizar a busca.

  3. Versátil: Pode ser usado em diversos tipos de problemas de roteamento.

Contras ❌

  1. Não funciona com pesos negativos: Requer que todas as arestas tenham peso não negativo.

  2. Complexidade de implementação: Mais complexo que BFS ou DFS.

info

Complexidade de tempo: O((V + E) log V) | Complexidade de espaço: O(V)

Youtube - Dijkstra's Algorithm por Computer Science Lessons

import heapq

def dijkstra(graph, start):
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    pq = [(0, start)]
    
    while pq:
        current_distance, current_node = heapq.heappop(pq)
        
        if current_distance > distances[current_node]:
            continue
            
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
                
    return distances

# Exemplo de uso
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

distances = dijkstra(graph, 'A')
print(distances)

Conclusão​

Cada algoritmo tem seu lugar e propósito específico. A escolha do algoritmo correto depende do problema que você está tentando resolver e das características dos seus dados. Entender as complexidades e trade-offs de cada algoritmo é crucial para escrever código eficiente e escalável.

Lembre-se:

  • Use algoritmos simples (como Bubble Sort) para conjuntos pequenos de dados ou para fins educacionais
  • Algoritmos mais complexos (como Quick Sort) são melhores para conjuntos grandes de dados
  • BFS e DFS são fundamentais para problemas de grafos
  • Dijkstra é a escolha certa para encontrar caminhos mais curtos em grafos ponderados

A prática constante e a compreensão profunda desses algoritmos ajudarão você a se tornar um programador mais eficiente e capaz de resolver problemas complexos de forma elegante.