review-data-structures
Voltar à Trilha

Revisão de Estruturas de Dados

--- id: 67f39dc7129b092b27099d8c title: Revisão de Estruturas de Dados challengeType: 31 dashedName: review-data-structures --- # --description--

Algoritmos e Notação Big O

  • Algoritmos: Um conjunto de instruções inequívocas para resolver um problema ou executar uma tarefa. Algoritmos devem terminar em um número finito de etapas e cada etapa deve ser precisa e inequívoca.
  • Notação Big O: Descreve o desempenho no pior caso, ou taxa de crescimento, de um algoritmo conforme o tamanho da entrada aumenta. Ela foca em como o uso de recursos cresce com o tamanho da entrada, ignorando fatores constantes e termos de ordem inferior.

Complexidades de Tempo Comuns

  • O(1) - Tempo Constante: O algoritmo leva a mesma quantidade de tempo independentemente do tamanho da entrada.
def check_even_or_odd(number):
    if number % 2 == 0:
        return 'Even'
    else:
        return 'Odd'
  • O(log n) - Tempo Logarítmico: O tempo aumenta lentamente conforme a entrada cresce. Comum em algoritmos que reduzem repetidamente o tamanho do problema por uma fração (como Binary Search).
  • O(n) - Tempo Linear: O tempo de execução aumenta proporcionalmente ao tamanho da entrada.
for grade in grades:
    print(grade)
  • O(n log n) - Tempo Log-Linear: Complexidade de tempo comum de algoritmos de ordenação eficientes como Merge Sort e Quick Sort.
  • O(n²) - Tempo Quadrático: O tempo de execução aumenta quadraticamente. Frequentemente visto em loops aninhados.
for i in range(n):
    for j in range(n):
        print("Hello, World!")

Complexidade de Espaço

  • O(1) - Espaço Constante: Algoritmo usa a mesma quantidade de memória independentemente do tamanho da entrada.
  • O(n) - Espaço Linear: O uso de memória cresce proporcionalmente ao tamanho da entrada.
  • O(n²) - Espaço Quadrático: O uso de memória cresce quadraticamente com o tamanho da entrada.

Técnicas de Resolução de Problemas

  • Entendendo o Problema: Leia a declaração do problema várias vezes. Identifique a entrada, a saída esperada e como transformar a entrada na saída.
  • Pseudocódigo: Descrição em alto nível da lógica do algoritmo que é independente de linguagem. Usa linguagem escrita comum misturada com construções de programação como IF, ELSE, FOR e WHILE.
GET original_string
SET reversed_string = ""
FOR EACH character IN original_string:
  ADD character TO THE BEGINNING OF reversed_string
DISPLAY reversed_string
  • Casos de Borda: Entradas específicas e válidas que ocorrem nos limites do que um algoritmo deve tratar. Sempre considere e teste casos de borda.

Arrays

  • Arrays Estáticos: Têm um tamanho fixo determinado na inicialização. Elementos armazenados em locais de memória adjacentes. O tamanho não pode ser alterado durante a execução do programa.
  • Arrays Dinâmicos: Podem crescer ou encolher automaticamente durante a execução do programa. Gerencie o redimensionamento por meio da cópia automática para arrays maiores quando necessário.

Listas Python (Arrays Dinâmicos)

numbers = [3, 4, 5, 6]

# Access elements
numbers[0]  # 3

# Update elements
numbers[2] = 16

# Add elements
numbers.append(7)
numbers.insert(3, 15)  # Insert at specific index

# Remove elements
numbers.pop(2)  # Remove at specific index
numbers.pop()   # Remove last element

Complexidades de Tempo para Arrays Dinâmicos

  • Acesso: O(1)
  • Inserir no final: O(1) em média, O(n) quando for necessário redimensionar
  • Inserir no meio: O(n)
  • Delete: O(n) para meio, O(1) para fim

Pilhas

  • Pilhas: estrutura de dados Last-In, First-Out (LIFO). Elementos adicionados e removidos apenas do topo.
  • Operação Push: Adicionando um elemento ao topo da pilha. Complexidade de tempo: O(1).
  • Operação Pop: Removendo um elemento do topo da pilha. Complexidade de tempo: O(1).
# Using Python list as stack
stack = []

# Push operations
stack.append(1)
stack.append(2)
stack.append(3)

# Pop operations
top_element = stack.pop()  # Returns 3

Filas

  • Filas: estrutura de dados First-In, First-Out (FIFO). Elementos adicionados na parte de trás e removidos da frente.
  • Operação Enqueue: Adicionando um elemento ao final da fila. Complexidade de tempo: O(1).
  • Operação Dequeue: Removendo um elemento da frente da fila. Complexidade de tempo: O(1).
from collections import deque

# Using deque for efficient queue operations
queue = deque()

# Enqueue operations
queue.append(1)
queue.append(2)
queue.append(3)

# Dequeue operations
first_element = queue.popleft()  # Returns 1

Listas Ligadas

  • Listas Ligadas: Estrutura de dados linear onde cada nó contém dados e uma referência para o próximo nó. Os nós estão conectados como uma corrente.

Listas Ligadas Simples

  • Estrutura: Cada nó possui dados e uma referência para o próximo nó.
  • Travessia: Só pode mover-se para frente da cabeça até a cauda.
  • Head Node: Primeiro nó na lista, geralmente o único nó acessível diretamente.
  • Nó Final: Último nó na lista, aponta para None.

Operações e Complexidades de Tempo

  • Inserir no início: O(1)
  • Inserir no final: O(n) - deve percorrer até o final
  • Inserir no meio: O(n) - deve percorrer até a posição
  • Excluir do início: O(1)
  • Excluir do final: O(n) - é necessário percorrer para encontrar o nó anterior
  • Excluir do meio: O(n) - é necessário percorrer para encontrar o nó

Listas Duplamente Ligadas

  • Estrutura: Cada nó possui dados e duas referências: próximo nó e nó anterior.
  • Travessia: Pode se mover em ambas as direções.
  • Memória: Requer mais memória do que listas simplesmente encadeadas devido à referência extra.

Hash Maps e Sets

Mapas e Hash Maps

  • Map (Abstract Data Type): Gerencia coleções de pares chave-valor. Cada chave deve ser única, mas os valores podem ser repetidos.
  • Hash Map: Implementação concreta do ADT map usando técnica de hashing. Usa função hash para gerar valores hash para as chaves, que determinam o local de armazenamento no array subjacente.

Dicionários Python (Hash Maps)

# Creating dictionaries
my_dictionary = {
    "A": 1,
    "B": 2, 
    "C": 3
}

# Alternative creation
my_dictionary = dict(A=1, B=2, C=3)

# Access and modify
value = my_dictionary["A"]  # 1
my_dictionary["A"] = 4      # Update value
del my_dictionary["A"]      # Remove key-value pair

# Check membership
"C" in my_dictionary

# Get keys, values, items
my_dictionary.keys()
my_dictionary.values()
my_dictionary.items()

Complexidades de Tempo para Hash Maps

  • Caso médio: O(1) para insert, get, delete
  • Pior caso: O(n) quando muitas colisões de hash ocorrem

Conjuntos

  • Conjuntos: Coleções não ordenadas de elementos únicos. Não são permitidos duplicados e nenhuma ordem específica é mantida.
  • Apenas Elementos Imutáveis: Conjuntos só podem conter tipos de dados imutáveis (números, strings, tuplas) porque os valores de hash devem permanecer constantes.
# Creating sets
numbers = {1, 2, 3, 4}
empty_set = set()  # Must use set(), not {}

# Add and remove elements
numbers.add(5)
numbers.remove(4)      # Raises KeyError if not found
numbers.discard(4)     # No error if not found

# Set operations
set_a = {1, 2, 3, 4}
set_b = {2, 3, 4, 5, 6}

# Union, intersection, difference, symmetric difference
set_a.union(set_b)                    # or set_a | set_b
set_a.intersection(set_b)             # or set_a & set_b
set_a.difference(set_b)               # or set_a - set_b
set_a.symmetric_difference(set_b)     # or set_a ^ set_b

# Subset and superset checks
set_a.issubset(set_b)
set_a.issuperset(set_b)
set_a.isdisjoint(set_b)

# Membership testing
5 in numbers

Complexidades de Tempo para Conjuntos

  • Caso médio: O(1) para add, remove e membership testing
  • Pior caso: O(n) devido a colisões de hash

Colisões de Hash

  • Colisão de Hash: Ocorre quando duas chaves diferentes produzem o mesmo valor de hash.
  • Estratégias de Resolução de Colisões:
  • Encadeamento: Cada índice do array aponta para uma lista encadeada que armazena todos os elementos com o mesmo valor de hash
  • Open Addressing: Procure pelo próximo índice disponível usando uma sequência predefinida

Quando Usar Cada Estrutura de Dados

  • Listas: Quando você precisa de acesso ordenado, indexado e não sabe o tamanho antecipadamente
  • Pilhas: Para operações LIFO (funcionalidade de desfazer, avaliação de expressões, retrocesso)
  • Filas: Para operações FIFO (agendamento de tarefas, busca em largura)
  • Listas Ligadas: Quando inserções/remoções frequentes no início, tamanho desconhecido, sem necessidade de acesso aleatório
  • Hash Maps: Para buscas rápidas de chave-valor, contagem de ocorrências e cache
  • Conjuntos: Para verificação de unicidade, operações matemáticas de conjunto, remoção de duplicatas
# --assignment-- Revise os tópicos e conceitos de Data Structures.