Maison > Périphériques technologiques > IA > le corps du texte

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

王林
Libérer: 2023-05-15 21:19:04
avant
854 Les gens l'ont consulté

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²).

Résumé de la complexité informatique de huit algorithmes dapprentissage automatique courants

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!

Étiquettes associées:
source:51cto.com
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal
À propos de nous Clause de non-responsabilité Sitemap
Site Web PHP chinois:Formation PHP en ligne sur le bien-être public,Aidez les apprenants PHP à grandir rapidement!