# Algorítmos

### 📚 Visão Geral

Este diretório contém uma coleção abrangente de **algoritmos fundamentais** organizados por categoria, desde métodos clássicos de ordenação e busca até técnicas modernas de aprendizado de máquina e compressão de dados.

```
┌─────────────────────────────────────────────────────────────────┐
│                         ALGORITMOS                               │
├─────────────┬─────────────┬─────────────┬─────────────┬─────────┤
│ Aprendizado │   Busca     │ Compressão  │   Grafos    │Ordenação│
│ de Máquina  │             │             │             │         │
├─────────────┼─────────────┼─────────────┼─────────────┼─────────┤
│ Regressão   │ Linear      │ Huffman     │ Dijkstra    │ Quick   │
│ SVM         │ Binária     │ LZ77/78     │ Bellman-Ford│ Merge   │
│ K-Means     │ A*          │ DCT         │ PageRank    │ Heap    │
│ Redes Neurais│ BFS/DFS    │ Zstandard   │ Prim/Kruskal│ Radix   │
└─────────────┴─────────────┴─────────────┴─────────────┴─────────┘
```

***

### 🤖 Aprendizado de Máquina

Algoritmos para reconhecimento de padrões, classificação, regressão e agrupamento.

| Algoritmo               | Tipo                     | Aplicação                        |
| ----------------------- | ------------------------ | -------------------------------- |
| **Regressão Linear**    | Supervisionado           | Previsão de valores contínuos    |
| **Regressão Logística** | Supervisionado           | Classificação binária            |
| **Árvores de Decisão**  | Supervisionado           | Classificação e regressão        |
| **Random Forest**       | Ensemble                 | Classificação robusta            |
| **SVM**                 | Supervisionado           | Classificação com margem máxima  |
| **KNN**                 | Supervisionado           | Classificação por vizinhança     |
| **K-Means**             | Não-supervisionado       | Clusterização                    |
| **PCA**                 | Redução dimensionalidade | Feature extraction               |
| **Apriori**             | Regras de associação     | Market basket analysis           |
| **CNN**                 | Deep Learning            | Visão computacional              |
| **RNN**                 | Deep Learning            | Dados sequenciais (texto, áudio) |
| **Transformers**        | Deep Learning            | NLP, LLMs (GPT, BERT)            |

#### Quando usar cada um

| Cenário                        | Algoritmo                |
| ------------------------------ | ------------------------ |
| Prever preço de imóvel         | Regressão Linear         |
| Classificar spam               | Regressão Logística, SVM |
| Identificar clientes similares | K-Means                  |
| Reconhecer imagens             | CNN                      |
| Processar texto/linguagem      | Transformers             |
| Séries temporais               | RNN, LSTM                |

***

### 🔍 Busca

Algoritmos para localizar elementos em estruturas de dados.

| Algoritmo                       | Complexidade | Tipo               | Uso                                 |
| ------------------------------- | ------------ | ------------------ | ----------------------------------- |
| **Busca Linear**                | O(n)         | Sequencial         | Dados não ordenados                 |
| **Busca Binária**               | O(log n)     | Dividir/conquistar | Dados ordenados                     |
| **Busca por Interpolação**      | O(log log n) | Estimativa         | Dados uniformemente distribuídos    |
| **Busca por Salto**             | O(√n)        | Jump               | Dados ordenados (melhor que linear) |
| **BFS (Busca em Largura)**      | O(V+E)       | Grafo              | Caminho mais curto (não ponderado)  |
| **DFS (Busca em Profundidade)** | O(V+E)       | Grafo              | Exploração, detecção de ciclos      |
| *A (A-Estrela)*\*               | O(E)         | Heurística         | Caminho mais curto (com heurística) |
| **Best-First Search**           | O(E)         | Guloso             | Busca informada                     |

#### Visualização de Complexidades

```
Tamanho    Linear     Binária    Interpolação
n=10       10         4          3
n=100      100        7          5
n=1.000    1.000      10         6
n=1.000.000 1.000.000  20         8
```

***

### 🗜️ Compressão

Algoritmos para reduzir o tamanho de dados.

#### Compressão sem perda (Lossless)

| Algoritmo     | Tipo               | Aplicação                          |
| ------------- | ------------------ | ---------------------------------- |
| **RLE**       | Run-length         | Imagens simples, dados repetitivos |
| **Huffman**   | Entropia           | ZIP, JPEG, MP3                     |
| **LZ77/LZ78** | Dicionário         | GIF, PNG, ZIP                      |
| **LZW**       | Dicionário         | GIF, UNIX compress                 |
| **Deflate**   | Huffman + LZ77     | ZIP, gzip, PNG                     |
| **LZMA**      | Dicionário + range | 7z, xz                             |
| **Brotli**    | LZ77 + Huffman     | WOFF, HTTP compression             |
| **Zstandard** | Entropia + rep     | Moderno (Facebook)                 |

#### Compressão com perda (Lossy)

| Algoritmo               | Aplicação                 |
| ----------------------- | ------------------------- |
| **DCT**                 | JPEG, MP3, MPEG           |
| **Psicoacústica**       | MP3, AAC                  |
| **Predição de quadros** | H.264, H.265, AV1 (vídeo) |

#### Comparação de Taxas (texto em inglês)

```
Original:   100% (1.000 bytes)
Huffman:    ~60% (600 bytes)
LZ77:       ~50% (500 bytes)
Deflate:    ~40% (400 bytes)
LZMA:       ~35% (350 bytes)
Brotli:     ~30% (300 bytes)
Zstandard:  ~32% (320 bytes)
```

***

### 🔗 Grafos

Algoritmos para processamento de estruturas de grafos.

#### Caminho Mínimo

| Algoritmo          | Complexidade   | Tipo de Grafo                       |
| ------------------ | -------------- | ----------------------------------- |
| **Dijkstra**       | O((V+E) log V) | Ponderado (pesos positivos)         |
| **Bellman-Ford**   | O(V×E)         | Ponderado (permite pesos negativos) |
| **Floyd-Warshall** | O(V³)          | Todos os pares                      |
| **A**\*            | O(E)           | Heurística (com estimativa)         |

#### Árvore Geradora Mínima (MST)

| Algoritmo   | Complexidade   | Característica       |
| ----------- | -------------- | -------------------- |
| **Prim**    | O((V+E) log V) | Para grafos densos   |
| **Kruskal** | O(E log E)     | Para grafos esparsos |

#### Fluxo em Redes

| Algoritmo          | Aplicação             |
| ------------------ | --------------------- |
| **Ford-Fulkerson** | Fluxo máximo em redes |

#### Ordenação Topológica

| Algoritmo | Aplicação                        |
| --------- | -------------------------------- |
| **Kahn**  | Ordenação de tarefas dependentes |

#### Algoritmos de Ranqueamento

| Algoritmo    | Aplicação                            |
| ------------ | ------------------------------------ |
| **PageRank** | Ranqueamento de páginas web (Google) |

#### Exemplo de Aplicações

| Problema              | Algoritmo      |
| --------------------- | -------------- |
| GPS (menor caminho)   | Dijkstra, A\*  |
| Rede de computadores  | Bellman-Ford   |
| Custo mínimo de cabos | Prim, Kruskal  |
| Fluxo de tráfego      | Ford-Fulkerson |
| Busca na web          | PageRank       |

***

### 📊 Ordenação

Algoritmos clássicos de ordenação com suas complexidades.

#### Comparação de Complexidades

| Algoritmo          | Melhor     | Médio      | Pior       | Memória  | Estável |
| ------------------ | ---------- | ---------- | ---------- | -------- | ------- |
| **Bubble Sort**    | O(n)       | O(n²)      | O(n²)      | O(1)     | ✅ Sim   |
| **Selection Sort** | O(n²)      | O(n²)      | O(n²)      | O(1)     | ❌ Não   |
| **Insertion Sort** | O(n)       | O(n²)      | O(n²)      | O(1)     | ✅ Sim   |
| **Merge Sort**     | O(n log n) | O(n log n) | O(n log n) | O(n)     | ✅ Sim   |
| **Quick Sort**     | O(n log n) | O(n log n) | O(n²)      | O(log n) | ❌ Não   |
| **Heap Sort**      | O(n log n) | O(n log n) | O(n log n) | O(1)     | ❌ Não   |
| **Counting Sort**  | O(n+k)     | O(n+k)     | O(n+k)     | O(k)     | ✅ Sim   |
| **Radix Sort**     | O(nk)      | O(nk)      | O(nk)      | O(n+k)   | ✅ Sim   |
| **Bucket Sort**    | O(n+k)     | O(n+k)     | O(n²)      | O(nk)    | ✅ Sim   |

#### Quando usar cada um

| Cenário                            | Algoritmo              |
| ---------------------------------- | ---------------------- |
| Dados pequenos (n < 50)            | Insertion Sort         |
| Dados quase ordenados              | Insertion Sort         |
| Dados grandes (n > 10⁶)            | Quick Sort, Merge Sort |
| Memória limitada                   | Heap Sort              |
| Garantir O(n log n)                | Merge Sort, Heap Sort  |
| Dados com poucos valores distintos | Counting Sort          |
| Dados já quase ordenados           | Insertion Sort (O(n))  |

#### Visualização das Complexidades

```
n=10⁶:
O(n)       → 1,000,000 operações   (1 segundo)
O(n log n) → ~20,000,000 ops       (20 segundos)
O(n²)      → 1,000,000,000,000 ops (1 dia)
```

***

### 🎲 Algoritmos Probabilísticos

Algoritmos que usam aleatoriedade para resolver problemas.

| Algoritmo               | Tipo               | Aplicação                                  |
| ----------------------- | ------------------ | ------------------------------------------ |
| **Monte Carlo**         | Simulação          | Física, finanças, otimização               |
| **Simulated Annealing** | Otimização         | Problemas NP-difíceis (caixeiro viajante)  |
| **Random Walk**         | Caminho aleatório  | Modelagem financeira, algoritmos genéticos |
| **QuickSort Aleatório** | Aleatorizado       | Ordenação (evita pior caso)                |
| **Sherwood**            | Aleatorizado       | Eliminar casos ruins                       |
| **Filtros de Bloom**    | Estrutura de dados | Teste de pertinência (falsos positivos)    |
| **Miller-Rabin**        | Teste primalidade  | Criptografia (RSA)                         |

#### Características

| Algoritmo               | Tempo       | Espaço   | Probabilidade de Erro |
| ----------------------- | ----------- | -------- | --------------------- |
| **Filtros de Bloom**    | O(k)        | O(m)     | \~(1-e^{-kn/m})ᵏ      |
| **Miller-Rabin**        | O(k log³ n) | O(1)     | 4⁻ᵏ                   |
| **Monte Carlo**         | Variável    | Variável | Configurável          |
| **Simulated Annealing** | O(t)        | O(1)     | Heurística            |

***

### 🎯 Guia Rápido por Problema

#### "Preciso encontrar um elemento em uma lista..."

| Se seus dados são...             | Use                    |
| -------------------------------- | ---------------------- |
| Não ordenados                    | Busca Linear           |
| Ordenados                        | Busca Binária          |
| Uniformemente distribuídos       | Busca por Interpolação |
| Em um grafo (não ponderado)      | BFS                    |
| Em um grafo (ponderado positivo) | Dijkstra               |
| Em um grafo (com heurística)     | A\*                    |

#### "Preciso ordenar meus dados..."

| Se seu cenário é...        | Use            |
| -------------------------- | -------------- |
| n < 50                     | Insertion Sort |
| n grande, memória ok       | Quick Sort     |
| n grande, memória limitada | Heap Sort      |
| Garantia de O(n log n)     | Merge Sort     |
| Dados com faixa pequena    | Counting Sort  |

#### "Preciso comprimir dados..."

| Se seus dados são... | Use                       |
| -------------------- | ------------------------- |
| Texto                | Deflate (gzip), Zstandard |
| Imagem               | PNG (Deflate), JPEG (DCT) |
| Áudio                | MP3 (psicoacústica + DCT) |
| Vídeo                | H.264, H.265, AV1         |
| Alta velocidade      | Zstandard, LZ4            |
| Máxima compressão    | LZMA (7z), Brotli         |

#### "Preciso classificar/agrupar dados..."

| Se seu problema é...            | Use                               |
| ------------------------------- | --------------------------------- |
| Prever valor numérico           | Regressão Linear                  |
| Classificar (2 classes)         | Regressão Logística, SVM          |
| Classificar (múltiplas classes) | Árvores de Decisão, Random Forest |
| Agrupar dados similares         | K-Means                           |
| Reconhecer imagens              | CNN                               |
| Processar texto                 | Transformers (BERT, GPT)          |

***

### 📊 Complexidades por Categoria

#### Busca

| Algoritmo | Melhor | Médio    | Pior     |
| --------- | ------ | -------- | -------- |
| Linear    | O(1)   | O(n/2)   | O(n)     |
| Binária   | O(1)   | O(log n) | O(log n) |
| Salto     | O(√n)  | O(√n)    | O(√n)    |

#### Ordenação

| Algoritmo  | Melhor     | Médio      | Pior       |
| ---------- | ---------- | ---------- | ---------- |
| Quick Sort | O(n log n) | O(n log n) | O(n²)      |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) |
| Heap Sort  | O(n log n) | O(n log n) | O(n log n) |

#### Grafos

| Algoritmo               | Complexidade   |
| ----------------------- | -------------- |
| Dijkstra (binário heap) | O((V+E) log V) |
| Bellman-Ford            | O(V×E)         |
| Floyd-Warshall          | O(V³)          |
| Prim (heap)             | O((V+E) log V) |
| Kruskal                 | O(E log E)     |

***

### 🔗 Links Úteis

#### Geral

* [Visualgo - Visualização de Algoritmos](https://visualgo.net/)
* [Big-O Cheat Sheet](https://www.bigocheatsheet.com/)
* [Algorithm Visualizer](https://algorithm-visualizer.org/)

#### Aprendizado de Máquina

* [Scikit-learn Documentation](https://scikit-learn.org/)
* [Fast.ai - Deep Learning](https://www.fast.ai/)

#### Grafos

* [Graph Algorithms (Stanford)](https://web.stanford.edu/class/cs97si/08-graph-algorithms.pdf)

#### Compressão

* [Compression Wiki](https://compression.wiki/)
* [Lossless Compression Benchmark](https://github.com/inikep/lzbench)

***

### 📚 Leitura Recomendada

| Livro                             | Autor              | Foco                    |
| --------------------------------- | ------------------ | ----------------------- |
| Introduction to Algorithms (CLRS) | Cormen et al.      | Algoritmos fundamentais |
| The Algorithm Design Manual       | Steven Skiena      | Aplicações práticas     |
| Pattern Recognition and ML        | Christopher Bishop | Machine Learning        |
| Understanding Compression         | Colt McAnlis       | Compressão de dados     |


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://0xmorte.gitbook.io/bibliadopentestbr/conceitos/algoritmos.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.