Analyse lisse d'algorithme
De Wikipedia, l'encyclopédie encyclopedia
En informatique théorique, l'analyse lisse d'algorithme (smoothed analysis) est une manière de mesurer la complexité d'un algorithme, c'est-à-dire ses performances. Elle complète et améliore les mesures classiques de complexité : la complexité dans le pire des cas, la complexité en moyenne et la complexité amortie. Elle a été inventée dans les années 2000 par Daniel Spielman et Shang-Hua Teng.