Base de Conhecimento - Vinicius Koiti

Entendendo Algoritmos

Leitura de 4 min

Capítulo 1 - Introdução aos Algoritmos

Livro: Aprendendo Algoritmos
Data: 08/12/2024
Tags: algoritmos livros

Conceito Principal

  • Algoritmo: Uma sequência finita de instruções bem definidas para resolver um problema ou realizar uma tarefa.

Pontos-Chave

  1. O que é um algoritmo?
    Um conjunto de passos que descrevem como resolver um problema ou executar uma tarefa. Deve ser:

    • Claro: Cada passo é bem definido.
    • Finito: Deve terminar em algum ponto.
    • Eficiente: Desempenha a tarefa com o menor custo de tempo e espaço possível.

  2. Por que estudar algoritmos?

    • Eficiência: Escolher o algoritmo certo pode reduzir drasticamente o tempo de execução e uso de recursos.
    • Escalabilidade: Algoritmos ajudam a lidar com grandes volumes de dados.
    • Compreensão de Problemas: A análise de algoritmos ensina a resolver problemas de forma estruturada.

Aplicação Prática

  • Cenário:
    Um cliente precisa buscar um produto em uma base de dados com milhões de registros.
    • Solução com algoritmo: Implementar busca binária ao invés de busca linear para reduzir o tempo de pesquisa.

Busca Linear vs. Busca Binária:

  • Busca Linear: Examina cada elemento. Tempo: ( O(n) ).
  • Busca Binária: Divide os dados ordenados pela metade em cada iteração. Tempo: ( O(\log n) ).

Problemas Resolvidos

  • Facilita a organização e escalabilidade de sistemas.
  • Permite lidar com grandes volumes de dados com eficiência.

Referência Cruzada

Capítulo 2 - Ordenação de Seleção

Tags: estruturas_dados arrays listas_encadeadas

Conceito de Array e Lista Encadeada

Como Funciona

  1. Processo Base:
    • Encontra o menor elemento no array
    • Troca com o primeiro elemento
    • Repete para o restante do array
  2. Características:
    • Simples de entender e implementar
    • Performance consistente O(n²)
    • Ordenação in-place (não usa memória extra)

Complexidade

  • Temporal: *O(n^2)
    • Sempre faz n * (n-1)/2 comparações
    • Independe da ordenação inicial
  • Espacial: *O(1)
    • Usa apenas algumas variáveis auxiliares

Capítulo 3 - Recursão

Tags: estruturas_dados arrays listas_encadeadas

Conceito

A recursão é a utilização da função dentro dela mesmo, onde passamos parâmetros diferentes, para que ele para que chegue até um caso de exceção para sair desse looping.

Memória na Recursão

Pilha de Chamadas (Call Stack)

  • Empilha um novo quadro na pilha de execução
  • Mantém seu próprio conjunto de variáveis locais
  • Aguarda a resolução das chamadas mais profundas
  • Desempilha após retornar seu resultado

Capítulo 4 - QuickSort

Tags: ordenacao dividir_conquistar recursao

Conceito Principal

O QuickSort funciona assim:

Primeiro, você escolhe uma carta qualquer (que o autor chama de pivô). No livro, ele sugere usar sempre a primeira carta, mas explica que existem outras estratégias para essa escolha. Depois, você vai separando as outras cartas em dois grupos: as menores que seu pivô vão para um lado, as maiores para outro. É como se você estivesse organizando suas cartas na mesa, com o pivô no meio. O autor destaca que é aí que está a mágica da recursão - você continua dividindo e organizando até que todos os grupos estejam ordenados.

Capítulo 5 - Tabelas Hash

Tags: estruturas_dados hash busca colisao

Conceito Principal

É uma estrutura utilizada pra organizar objetos similares, dentro de gavetas enumeradas, isto é ele, parecendo uma união entre arrays e lista encadeiadas, fazemos, ele dentro da estrutura e enumera com um identificador que que utilizamos, isso facilita e reduz a complexidade a para inserção/remoção e busca

Funcionamento Básico

  1. A função hash transforma a chave em um índice da tabela
  2. O valor é armazenado na posição indicada pelo índice
  3. Para recuperar um valor, aplica-se novamente a função hash à chave

Técnicas de Resolução de Colisões

  1. Encadeamento (chaining):
    • Cada posição da tabela mantém uma lista de elementos
    • Elementos com mesmo índice são armazenados na mesma lista
  2. Endereçamento aberto:
    • Procura próxima posição livre na tabela
    • Métodos comuns: sondagem linear, quadrática e hash duplo

Visão de gráfico

Backlinks