Quais são alguns dos melhores algoritmos?

Não há resposta para isto.

Vamos encontrar a resposta para este problema :

Q. Como encontrar qualquer algoritmo tem um melhor desempenho ?

A. Formas mais comuns de comparar algoritmos:

1) Complexidade temporal

2) Complexidade espacial

3) Qualidade da solução (pode não ser aplicável se se propuser a resolução exacta de um problema). Este pode ser um grande fator se nós're falando algoritmos de aproximação.

4) Facilidade de implementação/ adaptação do algoritmo. Alguns algoritmos podem ter muita sobrecarga para implementar corretamente. Por vezes existem algoritmos mais adequados para a sua aplicação. Por exemplo, em computação paralela, a maioria vai achar Bellman-Ford mais útil que o algoritmo de Dijkstra's devido à forma como Bellman-Ford funciona.

No entanto, o tempo e a complexidade não são *de qualquer forma* a característica desejável para maximizar; vou dar dois exemplos.

Um é a "estabilidade numérica", uma característica dos algoritmos tanto em álgebra linear como em equações diferenciais. Vamos gastar mais tempo algorítmico e mais complexidade algorítmica em algoritmos que são mais estáveis numericamente. Na álgebra linear a instabilidade é geralmente causada quando um algoritmo encontra números muito próximos de zero ou infinito ou ambos, devido à representação finita da resolução dos números pode ser perdida. Em geral, isto causa números muito ligeiramente diferentes, apenas alguns epsilon diferentes um do outro (onde epsilon é o menor número que pode ser adicionado a um, em uma máquina, e obter um resultado != 1), para produzir grandes diferenças na resposta. Assim, por exemplo, gastamos muito tempo e complexidade de espaço "pivotando" na factorização do LU para obter um algoritmo estável; sem pivotar o LU não é estável. Da mesma forma, temos algoritmos que não fazem nada além de matrizes de "condição" para evitar instabilidade.

Um segundo exemplo é "robustez" no seu sentido estatístico técnico. Robustez significa uma medida ou algoritmo que é *não* sensível a outliers. Assim, por exemplo, quando eu ajusto uma linha de mínimos quadrados a um conjunto de pontos, a linha pode ser fortemente enviesada por um único valor extremamente grande. Mesmo que eu tenha 99 pares de números que formam uma linha perfeita de 45 graus, se eu adicionar um único par outlier para o qual o valor Y é cem vezes o que "deveria" ser para cair na mesma linha, a linha ajustada será severamente inclinada para fora da linha de 45 graus. O algoritmo irá "desistir" do ajuste perfeito para 99 pontos, a fim de melhor representar o ponto de outlier. Isto é *não* robusto.

Uma abordagem robusta dos mínimos quadrados é, em vez de encontrar a linha que minimiza a soma dos erros ao quadrado criados pelo uso dessa linha, encontrar a linha que minimiza o *mediano* dos erros ao quadrado criados pelo uso dessa linha. No exemplo, essa linha é a linha de 45 graus, e a mediana dos erros ao quadrado é zero, e o ponto mais distante (e até 98 aberrações mais loucas) seria completamente ignorado. A linha de 45 graus seria encontrada.

Existem algoritmos robustos semelhantes para encaixar curvas estatísticas, encontrar formas, etc. No entanto, eles são caros no tempo, às vezes severamente. Mas o custo do tempo vale a pena porque as estatísticas robustas são efetivamente imunes ao "ruído" em sinais, onde aproximações de erro menos quadráticas não são. O mundo real está cheio de ruído e outliers, alguns deles causados por erro humano ou de máquina, em particular em imagens pixeladas ou som sampleado. Em tais circunstâncias, um algoritmo mais robusto em termos de tempo e custo pode encontrar sinais num ambiente ruidoso onde algoritmos mais rápidos produzem respostas tão corrompidas pelo ruído que são inúteis, ou mesmo perigosas se aceites.

Em alguns casos, a complexidade temporal e espacial não é tão importante como encontrar uma resposta mais provável para modelar o sinal real apesar do ruído e da degradação do sinal.