Bonjour à tous,

Est-ce quelqu'un sait exactement quelle est la complexité de l'algorithme des k-moyennes (K-means) ?

J'ai beau cherché, j'ai rien trouvé de vraiment clair.

Merci

si j'ai encore quelques souvenirs de maths et de complexité algo (et wikipedia) :

• si on tente de le résoudre c'est NP-difficile : pas de moyen efficace(/prédictible) de déterminer la résultat, NP-difficile est sa classe de complexité (et c'est moche)
• à k et d fixés, c'est du n^(dk+1)*log(n)
• dans un espace euclidien, il y des algos d'approximation de complexité polynomiale (dont l'algorithme de Lloyds)

Réponse courte : l'algo k-means est NP-difficile

-
Edité par Titi2.01 26 avril 2016 à 16:27:16