Please enable JavaScript.
Coggle requires JavaScript to display documents.
Brute Force, Decrease and Conquer, Divide and Conquer - Coggle Diagram
Brute Force
Brute Force é uma abordagem direta de resolver um problema, geralmente baseada no enunciado do problema e nas definições de conceitos envolvidos.
-
-
Bubble Sort
Outra estratégia brute force de ordenação, compara elementos adjacentes da lista e muda-os se eles tiverem fora de ordem.
Tem complexidade O(N^2) em todos seus casos. Não é um algoritmo eficiente mesmo entre os algoritmos de ordenação menores;
Decrease and Conquer
Insertion Sort
Usando a técnica do Decrease and Conquer, vamos olhar para as menores instâncias do problema de ordenação.
Vamos assumir que o array A[0] a A[n-2] já está ordenado e ,então, só precisaremos percorrer o array a fim de achar a posição apropriada para o A[n-1]
No pior caso, temos o mesmo número de comparações que o Selection sort, que seria o caso de uma lista de elementos somente decrescentes (ou não-crescentes).
-
Técnica baseada na exploração da relação entre a solução de uma dada instância do problema e a solução da sua menor instância.
Podemos, a partir disso, ter soluções Top-Down (Geralmente recursivas) ou Bottom-Up (Geralmente iterativas), também chamamos bottom-up de Abordagem Incremental.
Divide and Conquer
Mergesort
Utilizando a abordagem de dividir e conquistar, vamos dividir o array em duas metades e ordená-los recursivamente e depois juntando as duas partes ordenadas no array final, também ordenado.
Podemos implementar usando dois ponteiros, que seguem as duas metades do arrays para construir um novo array sortado.
O pior caso de mergesort em um array é quando os elementos menores vem alternando de array em array.
A complexidade é O(n log n), o que é melhor do que os outros algoritmos de ordenação vistos até agora. O ônus é a quantidade linear de espaço a mais que o algoritmo precisa.
Um mergesort que divide a lista em mais de duas partes e resolve recursivamente é chamado Multiway mergesort.
É uma das técnicas mais conhecidas de design de algoritmos. Vamos subdividir um problema maior em problemas menores do mesmo tipo, mas que tem mais ou menos o mesmo tamanho.
-