Please enable JavaScript.
Coggle requires JavaScript to display documents.
Recursividade e estrutura de dados - Coggle Diagram
Recursividade e estrutura de dados
Tipos de algoritmos
Quadráticos
Quanto maior 'n', menos performance
Bubble sort
O(n²)
Insertion sort
Pior caso: O(n²)
Melhor caso: O(n)
Selection sort
O(n²)
Melhores para aprendizado
Gastam mais CPU
Eficientes
"Dividir para conquistar"
Quebra problema em pedaços menores
:one: Dividir
:two: Conquistar
:three: Combinar
Gasta mais memória por usar recursão
Tipos
Merge sort
O(n log n)
Quick sort
Melhor caso: O(n log n)
Pior caso: O(n²)
Casos de uso
Bubble sort
Apenas para aprendizado
Selection sort
Merge sort
Performance consistente
Quick sort
Listas grandes e desordenadas
Insertion sort
Listas pequenas ou quase ordenadas
O que é um bom algoritmo
Quantificação
errada
:one: Quantidade de linhas
:two: Números de testes e condições
:three: Número de laços
Quantificação correta
:star2: Tempo de execução
Depende de dois fatores
:one: Tamanho da entrada
:two: Características da máquina
Análise assintótica
Definição matemática do tempo de execução do algoritmo
Em função do tamanho da entrada
Melhor caso vs pior caso
Pior caso é o mais importante
Classes de complexidade (mais rápido para o mais lento)
:one: Constante: c
:two: Logarítmica: log n
:three: Linear: n
:four: Polinomial: n², n³, ...
:five: Exponencial: 2^n
Notações assintóticas
O
Limite superior (pior caso) ou igual
Ω (ômega)
Limite inferior (melhor caso) ou igual
θ (téta)
Limite inferior (melhor caso) e superior (pior caso)
Recursividade
Quebrar problemas em coisas triviais
Composição geral
:one: Condição de parada
:two: Casos gerais
Chamadas ficam na pilha de execução