Algoritmos e Estruturas de Dados - A Base da Programação

0 Marcos 12:19

Algoritmos e Estruturas de Dados - A Base da Programação

⚙️📊

ALGORITMOS E ESTRUTURAS DE DADOS

# const { resolucao } = await problemas.solucionar()

{ A&ED }

📘 Introdução ⚡ Algoritmos 🗂️ Estruturas ⏱️ Complexidade 🔍 Busca e Ordenação

Algoritmos e estruturas de dados são a base fundamental da ciência da computação. Um algoritmo é uma sequência finita de passos para resolver um problema, enquanto uma estrutura de dados é uma forma de organizar e armazenar informações para que possam ser usadas eficientemente.

                    // Exemplo simples de algoritmo: soma de dois números
                    function somar(a, b) {
                        return a + b;
                    }
                    
                    // Complexidade: O(1) - tempo constante
                

A escolha da estrutura de dados e do algoritmo adequado pode significar a diferença entre um programa que roda em segundos e outro que leva dias para executar.

⚙️ PRINCIPAIS ALGORITMOS

🔍

Busca Binária

Algoritmo eficiente para encontrar um elemento em uma lista ordenada. Divide repetidamente o intervalo de busca pela metade.

function buscaBinaria(arr, alvo) {
    let esq = 0, dir = arr.length - 1;
    while (esq <= dir) {
        const meio = Math.floor((esq + dir) / 2);
        if (arr[meio] === alvo) return meio;
        if (arr[meio] < alvo) esq = meio + 1;
        else dir = meio - 1;
    }
    return -1;
}
                        

⏱️ Complexidade: O(log n) - logarítmica

🔄

Quick Sort

Algoritmo de ordenação eficiente que usa a estratégia "dividir para conquistar". Escolhe um pivô e particiona o array em elementos menores e maiores.

function quickSort(arr) {
    if (arr.length <= 1) return arr;
    const pivo = arr[0];
    const menores = arr.slice(1).filter(x => x <= pivo);
    const maiores = arr.slice(1).filter(x => x > pivo);
    return [...quickSort(menores), pivo, ...quickSort(maiores)];
}
                        

⏱️ Complexidade: O(n log n) médio, O(n²) pior caso

🗺️

Dijkstra

Algoritmo para encontrar o caminho mais curto entre nós em um grafo com arestas de peso não negativo. Fundamental para sistemas de navegação.

⏱️ Complexidade: O((V + E) log V) com heap

🌐

BFS e DFS

BFS (Breadth-First Search): explora vizinhos primeiro. DFS (Depth-First Search): explora até o fundo antes de voltar.

⏱️ Complexidade: O(V + E) para ambos

🗂️ ESTRUTURAS DE DADOS FUNDAMENTAIS

📦 Array (Vetor)

[ 5, 8, 2, 9, 1 ]

Coleção ordenada de elementos acessíveis por índice. Acesso O(1), inserção/remoção O(n).

🔗 Lista Ligada

5 → 8 → 2 → 9 → 1

Sequência de nós onde cada um aponta para o próximo. Inserção/remoção O(1) no início, busca O(n).

📚 Pilha (Stack)

[ 1 ← 9 ← 2 ]
(LIFO - Last In, First Out)

Operações push (inserir) e pop (remover) apenas no topo. Usada em recursão e undo/redo.

🧍 Fila (Queue)

[ 5 ] → [ 8 ] → [ 2 ]
(FIFO - First In, First Out)

Inserção no final, remoção no início. Usada em processamento de tarefas e buffers.

🌳 Árvore Binária

8
├─ 3
│ ├─ 1
│ └─ 6
└─ 10

Estrutura hierárquica com raiz e nós filhos. Busca eficiente em árvores balanceadas (O(log n)).

🔑 Tabela Hash

{"chave": "valor"}
{"nome": "João", "idade": 30}

Mapeia chaves para valores usando função hash. Inserção, remoção e busca O(1) médio.

⏱️ ANÁLISE DE COMPLEXIDADE (Big O)

A notação Big O descreve o comportamento assintótico de um algoritmo em relação ao tamanho da entrada (n).

O(1) - Constante

10%

O(log n) - Logarítmica

20%

O(n) - Linear

40%

O(n log n) - Linearítmica

60%

O(n²) - Quadrática

80%

O(2ⁿ) - Exponencial

100%

Estrutura	Acesso	Busca	Inserção	Remoção
Array	O(1)	O(n)	O(n)	O(n)
Lista Ligada	O(n)	O(n)	O(1)*	O(1)*
Pilha	O(n)	O(n)	O(1)**	O(1)**
Fila	O(n)	O(n)	O(1)***	O(1)***
Árvore Binária	O(log n)	O(log n)	O(log n)	O(log n)
Tabela Hash	O(1)	O(1)	O(1)	O(1)

📊 COMPARAÇÃO DE ALGORITMOS DE ORDENAÇÃO

🫧 Bubble Sort

O(n²) - Simples, mas ineficiente para grandes conjuntos.

⚡ Merge Sort

O(n log n) - Estável, divide e conquista.

🔀 Quick Sort

O(n log n) médio - Muito rápido na prática.

📥 Insertion Sort

O(n²) - Eficiente para dados quase ordenados.

🎯 Problema Real: Busca em Lista Telefônica

Imagine uma lista telefônica com 1 milhão de nomes:

Busca Linear: Percorre nome por nome → até 1 milhão de comparações (O(n)).
Busca Binária: Divide a lista repetidamente → no máximo 20 comparações (O(log n)).

                    // Busca binária encontra em 20 passos
                    // Busca linear levaria até 1.000.000 passos
                    // 1.000.000 vs 20 = 50.000x mais rápido!
                