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.

function checkEvenOrOdd(number) {
  if (number % 2 === 0) {
    return "Even";
  } else {
    return "Odd";
  }
}

console.log(checkEvenOrOdd(4)) // "Even"
console.log(checkEvenOrOdd(5)) // "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 (const grade of grades) { // grades is an array
  console.log(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.

const n = 3;

for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    console.log("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.

Implementação de Arrays Dinâmicos em Javascript

let numbers = [3, 4, 5, 6];
// Access elements
console.log(numbers[0])  // 3

// Update elements
numbers[2] = 16
console.log([...numbers]);  // [3, 4, 16, 6]

// Add elements
numbers.push(7)
console.log([...numbers]);  // [3, 4, 16, 6, 7] 

// Add at a specific index
numbers.splice(3, 0, 15);
console.log([...numbers]);  // [3, 4, 16, 15, 6, 7]

// Remove elements
numbers.splice(2, 1);  // Remove at specific index
console.log([...numbers]);  // [3, 4, 15, 6, 7]

numbers.pop()   // Remove last element
console.log([...numbers]); // [3, 4, 15, 6]

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 JavaScript array as a stack

let stack = [];

// Push operations
stack.push(1);
stack.push(2);
stack.push(3);
console.log([...stack]);  // [1, 2, 3]

// Pop operations
let topElement = stack.pop();
console.log(topElement);  // 3
console.log([...stack]);  // [1, 2]

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).

// Using JavaScript array as a queue
let queue = [];

// Enqueue operations
queue.push(1);
queue.push(2);
queue.push(3);
console.log([...queue]);  // [1, 2, 3]

// Dequeue operations
let firstElement = queue.shift();
console.log(firstElement);  // 1
console.log([...queue]);  // [2, 3]

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.
• Tail Node: Último nó na lista, aponta para null.

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.

Quando Usar Cada Estrutura de Dados

• Arrays (arrays dinâmicos): 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