Résumé de la complexité informatique de huit algorithmes d'apprentissage automatique courants

La complexité informatique est une mesure des ressources de calcul (temps et espace) consommées par un algorithme spécifique lors de son exécution.

La complexité informatique est divisée en deux catégories :

1. La complexité temporelle

La complexité temporelle n'est pas une mesure des performances d'un algorithme ou d'un morceau de code. Le temps nécessaire pour s'exécuter sur une machine ou une condition. La complexité temporelle fait généralement référence à la complexité temporelle, qui est une fonction qui décrit qualitativement le temps d'exécution de l'algorithme et nous permet de comparer différents algorithmes sans les exécuter. Par exemple, un algorithme avec O(n) fonctionnera toujours mieux que O(n²) car son taux de croissance est inférieur à O(n²).

2. Complexité spatiale

Tout comme la complexité temporelle est une fonction, la complexité spatiale l'est aussi. Conceptuellement, c'est la même chose que la complexité temporelle, il suffit de remplacer le temps par l'espace. Wikipédia définit la complexité spatiale comme :

La complexité spatiale d'un algorithme ou d'un programme informatique est la quantité d'espace de stockage requise pour résoudre une instance d'un problème informatique en fonction du nombre de fonctionnalités en entrée.

Ci-dessous, nous avons compilé la complexité informatique de certains algorithmes d'apprentissage automatique courants.

1. Régression linéaire

• n= nombre d'échantillons d'entraînement, f = nombre de fonctionnalités
• Complexité du temps d'entraînement : O( f²n +f³)
• Complexité temporelle de prédiction : O(f)
• Complexité spatiale d'exécution : O(f)

2. Régression logistique :

• n=nombre d'échantillons d'entraînement, f = nombre de fonctionnalités
• Complexité du temps d'entraînement : O(f*n)
# 🎜🎜#Complexité temporelle de prédiction : O(f)
• Complexité spatiale d'exécution : O(f)

3. 🎜🎜#

n= nombre d'échantillons d'entraînement, f = nombre de fonctionnalités, s= nombre de vecteurs de support

Complexité du temps de formation : O(n²) à O(n³), la formation la complexité temporelle varie selon les différents noyaux.
• Complexité temporelle de prédiction : O(f) à O(s*f) : le noyau linéaire est O(f), RBF et le polynôme est O(s*f)
• #🎜🎜 # Complexité spatiale d'exécution : O(s)
• 4 Naive Bayes :

n= nombre d'échantillons d'entraînement, f = Nombre de. caractéristiques, c = nombre de catégories de classification

Complexité du temps d'entraînement : O(n*f*c)

• Complexité du temps de prédiction : O(c*f)# 🎜🎜#
Complexité de l'espace d'exécution : O(c*f)
• 5, arbre de décision :
• n= Nombre d'échantillons d'entraînement, f = nombre de fonctionnalités, d = profondeur de l'arbre, p = nombre de nœuds

Complexité du temps de formation : O(n*log(n)*f)

#🎜🎜 #Temps de prédiction complexité : O(d)

• Complexité de l'espace d'exécution : O(p)
• 6, Forêt aléatoire :
• # 🎜🎜##🎜🎜 #n= nombre d'échantillons d'entraînement, f = nombre de fonctionnalités, k = nombre d'arbres, p = nombre de nœuds dans l'arbre, d = profondeur de l'arbre
• Complexité du temps d'entraînement : O(n *log(n)*f*k)

Complexité temporelle de prédiction : O(d*k)

Complexité spatiale d'exécution : O(p* k)

• 7, K voisin le plus proche :
• n= nombre d'échantillons d'apprentissage, f = nombre de fonctionnalités, k= nombre de voisins les plus proches
• Brute :

Complexité du temps d'entraînement : O(1)

Complexité du temps de prédiction : O(n*f+k*f)

#🎜🎜 #Complexité de l'espace-temps d'exécution : O(n*f)

kd-tree :

• Complexité du temps d'entraînement : O (f*n* log(n))
• Complexité temporelle de prédiction : O(k*log(n))
• Complexité spatiale d'exécution : O(n* f)

#🎜 🎜#

8, K-means clustering :

• n= nombre d'échantillons d'entraînement, f = nombre de fonctionnalités, k= nombre de clusters, i = nombre d'itérations# 🎜🎜#
Complexité du temps d'entraînement : O(n*f*k*i)
• Complexité de l'espace d'exécution : O(n*f+k*f )
• #🎜🎜 #

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!