Estruturas de Dados e Controle de Fluxo

Estruturas de Dados

• Definição: Formatos para organizar, gerenciar e armazenar dados para eficiência.
• Tipos Comuns:
  • Arrays: Coleções de elementos do mesmo tipo; acesso rápido via índice.
  • Listas Ligadas: Estruturas compostas de nós; cada nó contém um valor e um ponteiro para o próximo.
  • Pilhas: Estrutura LIFO (Last In, First Out); operações principais: push e pop.
  • Filas: Estrutura FIFO (First In, First Out); operações principais: enqueue e dequeue.
  • Dicionários (Tabelas Hash): Armazenamento de pares chave-valor para acesso rápido.

Controle de Fluxo

• Definição: Mecanismos que controlam a ordem de execução de instruções em um programa.
• Estruturas Comuns:
  • Condicionais:
    • if, else, switch/case
  • Laços de Repetição:
    • for, while, do while
  • Desvios:
    • break (interrompe laços), continue (passa para a próxima iteração).

Algoritmos de Ordenação

• Definição: Métodos para reorganizar elementos em uma determinada ordem.
• Algoritmos Comuns:
  • Bubble Sort: Troca repetida de elementos adjacentes; ineficiente para grandes listas.
  • Selection Sort: Seleciona o menor elemento e o move para a posição correta; simples, mas lento.
  • Insertion Sort: Insere elementos em uma sub-lista ordenada; eficiente para listas pequenas.
  • Merge Sort: Método divide e conquista; eficiente, com complexidade O(n log n).
  • Quick Sort: Baseado em partição; geralmente rápido, mas pode degradar para O(n²) em casos ruins.

Complexidade de Algoritmos

• Definição: Mede a eficiência de algoritmos em termos de tempo e espaço.
• Notações Comuns:
  • O (Notação Big O): Descreve o pior caso ou a complexidade de tempo máxima.
  • Ω (Notação Big Omega): Representa o melhor caso.
  • Θ (Notação Theta): Representa a complexidade média, se os limites superior e inferior coincidirem.
• Exemplos:
  • Linear: O(n)
  • Quadrática: O(n²)
  • Logarítmica: O(log n)
  • Exponencial: O(2^n)

Programação Recursiva

• Definição: Método onde uma função chama a si mesma para resolver um problema.
• Componentes:
  • Caso Base: Condição que termina a recursão.
  • Caso Recursivo: A função chama a si mesma com um subconjunto do problema.
• Exemplos Comuns:
  • Cálculo de fatorial: n! = n * (n-1)!
  • Sequência de Fibonacci: F(n) = F(n-1) + F(n-2)
• Vantagens e Desvantagens:
  • Vantagens: Simplificação de soluções para problemas complexos, estrutura clara.
  • Desvantagens: Pode causar estouro de pilha (stack overflow) se a profundidade da recursão for excessiva.

Estruturas de Dados

• Definição: Estruturas de dados são maneiras de organizar, gerenciar e armazenar dados para otimizar a eficiência.
• Tipos Comuns:
  • Arrays: Coleções de elementos do mesmo tipo, acessíveis rapidamente por índice.
  • Listas Ligadas: Estruturas formadas por nós, cada nó contendo um valor e um ponteiro para o próximo.
  • Pilhas (Stacks): Seguem o princípio LIFO (Last In, First Out). As principais operações são push (adicionar um elemento no topo) e pop (remover o elemento do topo).
  • Filas (Queues): Seguem o princípio FIFO (First In, First Out). As principais operações são enqueue (adicionar um elemento na fila) e dequeue (remover o elemento do início da fila).
  • Dicionários (Tabelas Hash): Armazenam pares chave-valor, permitindo acesso rápido aos dados.

Controle de Fluxo

• Definição: Mecanismos que controlam a ordem de execução das instruções em um programa.
• Estruturas Comuns:
  • Condicionais:
    • if, else, switch/case.
  • Laços de Repetição:
    • for, while, do while.
  • Desvios:
    • break (encerra laços), continue (pula para a próxima iteração).

Algoritmos de Ordenação

• Definição: Métodos para reorganizar elementos em uma lista em uma determinada ordem (crescente ou decrescente).
• Algoritmos Comuns:
  • Bubble Sort: Compara e troca elementos adjacentes repetidamente. Ineficiente para listas maiores.
  • Selection Sort: Encontra o menor elemento da lista e coloca na posição correta. Simples, mas lento para listas grandes.
  • Insertion Sort: Insere elementos em uma sub-lista ordenada. Eficiente para listas pequenas.
  • Merge Sort: Utiliza o método divide e conquista. Eficiente, com complexidade O(n log n).
  • Quick Sort: Funciona através do processo de partição. Geralmente rápido, mas pode ter complexidade O(n²) em casos ruins.

Complexidade de Algoritmos

• Definição: Avalia a eficiência de algoritmos em termos de tempo e espaço utilizado.
• Notações Comuns:
  • O (Notação Big O): Representa o pior caso ou a complexidade de tempo máxima.
  • Ω (Notação Big Omega): Representa o melhor caso.
  • Θ (Notação Theta): Representa a complexidade média, quando o limite superior e inferior coincidem.
• Exemplos:
  • Linear: O(n)
  • Quadrática: O(n²)
  • Logarítmica: O(log n)
  • Exponencial: O(2^n)

Programação Recursiva

• Definição: Método em que uma função chama a si mesma para resolver um problema.
• Componentes:
  • Caso Base: Condição que finaliza a recursão.
  • Caso Recursivo: A função chama a si mesma com um subconjunto do problema.
• Exemplos Comuns:
  • Cálculo de Fatorial: n! = n * (n-1)!
  • Sequência de Fibonacci: F(n) = F(n-1) + F(n-2)
• Vantagens e Desvantagens:
  • Vantagens: Simplifica soluções para problemas complexos e oferece uma estrutura clara.
  • Desvantagens: Pode causar estouro de pilha (stack overflow) se a profundidade da recursão for muito grande.