Please enable JavaScript.
Coggle requires JavaScript to display documents.
Ordenação, Dividir para conquistar, Diminuir para conquistar - Coggle…
Ordenação
Sorteio em bolhas
Compara elementos adjacentes
Troca o maior elemento até a última posição
Θ(n²)
Sorteio por seleção
Varre o vetor até a posição n - 1
Crescente
Troca o maior elemento com o menor
decrescente
Troca o menor elemento com o maior
Θ(n)
Dividir para conquistar
Divide o problema em 2 partes
Soluciona a parte 1
Soluciona a parte 2
Soluciona o problema
Mais eficiente que a força bruta
T(n) = aT(n/b) + f(n)
Recorrência geral
Θ(n)
Mergesort
Concatenação por recursão
Múltiplos caminhos
Pior caso
n log2 n n + 1
C(1)=0
Diminuir para conquistar
Definição recursiva
Top down
F(n) = a^n
Problema de tamanho n
Subproblema de tamanho n-1
Soluciona o subproblema
Soluciona o problema
Bottom up
a^n = (a^n)²
Divide o problema ao meio
Soluciona metade do problema
Soluciona o problema
Θ(log n)
Sorteio por inserção
Depende do tamanho da entrada
Pior caso
Θ(n)²
Melhor caso
Θ(n)