Ciências da computação dia 172

Durante nossa aula de número 172, exploramos um tema central para qualquer cientista da computação: a escolha correta de estruturas de dados e algoritmos de busca. Vimos como a organização dos dados na memória e a estratégia de busca impactam drasticamente a performance dos nossos sistemas. Revisamos desde estruturas clássicas como listas encadeadas até o funcionamento interno dos dicionários em Python.

1. Arrays vs Listas Encadeadas

Começamos revisitando a diferença fundamental entre arrays e listas encadeadas.

Arrays armazenam elementos em posições contíguas de memória. Isso permite acesso aleatório em tempo O(1), mas inserções e remoções no meio custam O(n) devido à necessidade de deslocar elementos.

Listas encadeadas, por outro lado, armazenam nós que apontam para o próximo elemento. A inserção e remoção na cabeça da lista é O(1), mas o acesso a um elemento arbitrário é O(n), pois precisamos percorrer a lista sequencialmente.

Vimos um exemplo simples de implementação de um nó em Python:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def insert_at_beginning(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def traverse(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

2. Busca Linear e Busca Binária

Outro tópico importante foram os algoritmos de busca.

A busca linear é a mais simples: percorremos a lista elemento por elemento até encontrar o desejado. Sua complexidade é O(n) no pior caso.

Já a busca binária é muito mais eficiente, com complexidade O(log n), mas exige que a lista esteja ordenada. O algoritmo funciona dividindo o intervalo de busca pela metade a cada iteração, comparando o elemento alvo com o elemento do meio.

Implementamos uma busca binária em Python:

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

# Exemplo de uso
sorted_array = [1, 3, 5, 7, 9, 11, 13]
index = binary_search(sorted_array, 7)
print(f"Elemento 7 encontrado no índice {index}")>

3. Análise de Complexidade e Notação Big-O

Discutimos como a notação Big-O nos ajuda a classificar a eficiência dos algoritmos.

A escolha do algoritmo certo pode significar a diferença entre milissegundos e horas de processamento para grandes volumes de dados.

4. Tabelas Hash (Dicionários)

Por fim, exploramos as tabelas hash, conhecidas em Python como dicionários (dict).

Uma tabela hash usa uma função de espalhamento (hash function) para mapear chaves para índices de um array. O ideal é que a função hash distribua as chaves uniformemente, permitindo busca, inserção e remoção em O(1) na média.

Colisões acontecem quando duas chaves diferentes geram o mesmo índice. Vimos duas estratégias para lidar com colisões:

1. Encadeamento Separado: cada posição do array guarda uma lista encadeada de elementos.
2. Endereçamento Aberto: busca-se a próxima posição vazia no array.

Em Python, o dict é extremamente otimizado e usa uma combinação de técnicas para garantir performance próxima de O(1) na maioria dos casos.

Conclusão

A aula de hoje reforçou como o conhecimento teórico sobre estruturas de dados e algoritmos é fundamental para escrever código eficiente. Dominar a análise de complexidade e saber quando usar uma lista, um array ordenado ou um dicionário é uma habilidade essencial para todo desenvolvedor.

Continue acompanhando as próximas aulas na página inicial do blog ou navegue pelas tags para encontrar tópicos específicos como algoritmos e estruturas de dados.

---

Perguntas Frequentes