Dividir e Conquistar Algoritmo
Um paradigma algorítmico muito popular, um algoritmo típico de Divide and Conquer resolve um problema usando os três passos seguintes:
- Divide: Dividir o problema dado em subproblemas do mesmo tipo.
- Conquer: Resolver recursivamente estes sub-problemas
- Combinar: Combinar apropriadamente as respostas
Seguir: Algoritmos padrão que são algoritmos de Divide e Conquer:
1 – A Pesquisa Binária é um algoritmo de pesquisa. Em cada passo, o algoritmo compara o elemento de entrada x com o valor do elemento médio na matriz. Se os valores corresponderem, devolver o índice do meio. Caso contrário, se x for menor que o elemento médio, então o algoritmo recursa para o lado esquerdo do elemento médio, ou recursa para o lado direito do elemento médio.
2 – O Quicksort é um algoritmo de ordenação. O algoritmo escolhe um elemento pivot, rearranja os elementos da matriz de tal forma que todos os elementos mais pequenos do que o elemento pivot escolhido se movem para o lado esquerdo do pivot, e todos os elementos maiores se movem para o lado direito. Finalmente, o algoritmo ordena recursivamente as subarrays à esquerda e à direita do elemento pivot.
3 – Merge Sort é também um algoritmo de ordenação. O algoritmo divide a matriz em duas metades, ordena-as recursivamente e finalmente funde as duas metades ordenadas.
4 – Par de pontos mais próximo: O problema é encontrar o par de pontos mais próximo num conjunto de pontos no plano x-y. O problema pode ser resolvido no tempo O(n²) calculando as distâncias de cada par de pontos e comparando as distâncias para encontrar o mínimo. O algoritmo Divide and Conquer resolve o problema no tempo O(nLogn).
5 – O Algoritmo de Strassen é um algoritmo eficiente para multiplicar duas matrizes. Um método simples para multiplicar duas matrizes necessita de 3 laços aninhados e é O(n³). O algoritmo de Strassen multiplica duas matrizes no tempo O(n².8974).
6 – Algoritmo Cooley-Tukey Fast Fourier Transform (FFT) é o algoritmo mais comum para FFT. É um algoritmo de divisão e conquista que funciona no tempo O(nlogn).
7 – algoritmo de Karatsuba para multiplicação rápida: Faz multiplicação de dois números de n dígitos no máximo em 3n^(log 3) multiplicações de um dígito em geral (e exactamente n^(log3) quando n é uma potência de 2). É portanto mais rápido do que o algoritmo clássico, que requer n² produtos de um dígito.
Problema de Inversões de Contagem
Consideraremos um problema que surge na análise das classificações, que estão a tornar-se importantes para uma série de aplicações actuais. Por exemplo, vários sites na Web utilizam uma técnica conhecida como filtragem colaborativa, na qual tentam fazer corresponder as suas preferências (para livros, filmes, restaurantes) com as de outras pessoas na Internet. Uma vez que o sítio Web tenha identificado pessoas com gostos “semelhantes” aos seus – com base numa comparação de como você e eles classificam várias coisas – pode recomendar coisas novas de que essas outras pessoas tenham gostado. Outra aplicação surge em ferramentas de pesquisa na Web, que executam a mesma pesquisa em muitos motores de busca diferentes e depois tentam sintetizar os resultados procurando semelhanças e diferenças entre as várias classificações que os motores de busca retornam.
Uma questão central em aplicações como esta é o problema de comparar duas classificações. Classifica-se um conjunto de filmes rt, e depois um sistema de filtragem colaborativa consulta a sua base de dados para procurar outras pessoas que tinham classificações “semelhantes”. Mas qual é uma boa maneira de medir, numericamente, quão semelhantes são as classificações de duas pessoas? Claramente uma classificação idêntica é muito semelhante, e uma classificação completamente invertida é muito diferente; queremos algo que interpola através da região do meio.
Vamos considerar comparar a sua classificação e a classificação de um estranho com o mesmo conjunto de n filmes. Um método natural seria rotular os filmes de 1 a n de acordo com a sua classificação, depois ordenar estas etiquetas de acordo com a classificação do desconhecido, e ver quantos pares estão “fora de ordem”. Mais concretamente, vamos considerar o seguinte problema. É-nos dada uma sequência de n números a1, …, an; vamos assumir que todos os números são distintos. Queremos definir uma medida que nos diga até que ponto esta lista está longe de estar em ordem ascendente; o valor da medida deve ser 0 se a1 < a2 << an, e deve aumentar à medida que os números se tornam mais embaralhados.
Uma forma natural de quantificar esta noção é através da contagem do número de inversões. Dizemos que dois índices i < j formam uma inversão se ai > aj, ou seja, se os dois elementos ai e aj estiverem “fora de ordem”. Vamos procurar determinar o número de inversões na sequência a1, …, an.