Na ciência da computação teórica, o algoritmo de análise suave ( smoothed analysis ) é uma forma de medir a complexidade de um algoritmo , ou seja, seu desempenho. Complementa e aprimora as medidas tradicionais de complexidade: a complexidade no pior caso , a complexidade média e a complexidade amortizada . Foi inventado na década de 2000 por Daniel Spielman e Shang-Hua Teng .
A introdução desta nova medida de complexidade foi motivada, por um lado, pela existência de certos algoritmos que funcionam muito bem na prática, mas cuja análise no pior caso não mostrou a eficácia, e por outro lado partilhada pela dificuldade de análise em média em geral.
O princípio da análise suave é medir o desempenho do algoritmo nos piores casos, mas com uma leve perturbação das instâncias. Portanto, calculamos uma expectativa de desempenho. De certa forma, é um método "local".
Mais precisamente, adiciona- se às entradas um ruído gaussiano , ou seja, uma variação aleatória dos dados que segue uma lei normal. A complexidade medida então depende de dois parâmetros: o tamanho da entrada, mas também o desvio padrão do Gaussiano usado.
Se a análise suave anuncia um algoritmo de bom desempenho entre o espaço de valores centrado em torno de um datum adicionando ruído (Gaussiano) a este datum, isso significa que, na prática, também deve haver bom desempenho para este algoritmo em todos casos.
Conceitualmente, a análise suave situa-se entre a análise da complexidade no pior caso, uma vez que estamos interessados nos piores desempenhos, e a análise da complexidade média, uma vez que consideramos uma perturbação aleatória.
Este método nem sempre pode ser facilmente colocado em prática: é necessário ser capaz de definir uma perturbação gaussiana, o que é bastante natural para o caso de otimização linear por exemplo, mas é muito menos natural para outros problemas mais combinatórios.
Uma das principais aplicações da análise suave é a demonstração da eficiência do simplex , um algoritmo usado na otimização linear e conhecido por sua eficiência prática e por sua complexidade exponencial no pior caso. A complexidade suave do simplex mostrou ser polinomial ( Spielman e Teng 2004 ).
Mais precisamente, um problema de otimização linear é escrito na forma:
Estamos, então, interessados em instâncias do problema do formulário
onde a matriz e o vetor são os resultados de uma perturbação gaussiana de e , desvio padrão .
O tempo máximo de cálculo em , e , esperança no simplex e no vetor , é polinomial no tamanho de e .
Foi mostrado anteriormente que o simplex tem uma complexidade polinomial na expectativa (para várias distribuições naturais de instâncias).
A análise suave foi usada, entre outros, nas áreas de aprendizado de máquina (por exemplo, para o problema k-means e no contexto de aprendizado do PAC ) e mineração de dados .
Em algoritmos mais clássicos, permitiu uma nova abordagem para certos algoritmos conhecidos, como o pivô gaussiano ou classificação rápida .
A análise suave foi inventada em 2000 por Daniel Spielman e Shang-Hua Teng ( Spielman e Teng 2004 ). Por isso, eles receberam o prestigioso Prêmio Gödel de 2008 e o Prêmio Fulkerson de 2009. Spielman também recebeu o Prêmio Nevanlinna em 2010, por seu trabalho em análises suaves.
O nome análise suavizada foi proposto por Alan Edelman .