Zusammenfassung der Rechenkomplexität von acht gängigen Algorithmen für maschinelles Lernen

Rechenkomplexität ist ein Maß für die Rechenressourcen (Zeit und Raum), die ein bestimmter Algorithmus bei der Ausführung verbraucht.

Rechenkomplexität wird in zwei Kategorien unterteilt:

1. Zeitkomplexität

Zeitkomplexität ist kein Maß für die Leistung eines Algorithmus oder eines Die Zeit, die zum Ausführen auf einer Maschine oder Bedingung benötigt wird. Zeitkomplexität bezieht sich im Allgemeinen auf Zeitkomplexität, eine Funktion, die die Laufzeit des Algorithmus qualitativ beschreibt und es uns ermöglicht, verschiedene Algorithmen zu vergleichen, ohne sie auszuführen. Beispielsweise wird ein Algorithmus mit O(n) immer eine bessere Leistung als O(n²) erbringen, da seine Wachstumsrate geringer als die von O(n²) ist.

2. Raumkomplexität

So wie Zeitkomplexität eine Funktion ist, ist auch Raumkomplexität eine Funktion. Vom Konzept her ist es dasselbe wie Zeitkomplexität, ersetzen Sie einfach Zeit durch Raum. Wikipedia definiert Raumkomplexität als:

Die Raumkomplexität eines Algorithmus oder Computerprogramms ist die Menge an Speicherplatz, die erforderlich ist, um eine Instanz eines Rechenproblems als Funktion der Anzahl der eingegebenen Features zu lösen.

Nachfolgend haben wir die Rechenkomplexität einiger gängiger Algorithmen für maschinelles Lernen zusammengestellt.

1. Lineare Regression

• n= Anzahl der Trainingsbeispiele, f = Anzahl der Features
• Trainingszeitkomplexität: O( f²n +f³)
• Vorhersagezeitkomplexität: O(f)
• Laufzeitraumkomplexität: O(f)

2. Logistische Regression:

• n=Anzahl der Trainingsbeispiele, f = Anzahl der Features
• Trainingszeitkomplexität: O(f*n)
# 🎜🎜#Vorhersagezeitkomplexität: O(f)
• Laufzeitraumkomplexität: O(f)

3. Unterstützungsvektormaschine: # 🎜🎜## 🎜🎜#

n= Anzahl der Trainingsbeispiele, f = Anzahl der Features, s= Anzahl der Unterstützungsvektoren

Trainingszeitkomplexität: O(n²) bis O(n³), das Training Die Zeitkomplexität variiert je nach Kernel.
• Vorhersagezeitkomplexität: O(f) bis O(s*f): Der lineare Kern ist O(f), RBF und das Polynom ist O(s*f)
• #🎜🎜 # Laufzeitkomplexität: O(s)
• 4. Naive Bayes:

n= Anzahl der Trainingsbeispiele, f = Anzahl der Merkmale, c = Anzahl der Klassifizierungskategorien

Trainingszeitkomplexität: O(n*f*c)

• Vorhersagezeitkomplexität: O(c*f)# 🎜🎜#
Laufzeitraumkomplexität: O(c*f)
• 5, Entscheidungsbaum:
• n= Anzahl der Trainingsbeispiele, f = Anzahl der Features, d = Tiefe des Baums, p = Anzahl der Knoten

Trainingszeitkomplexität: O(n*log(n)*f)

#🎜🎜 #Vorhersagezeit Komplexität: O(d)

• Laufzeitraumkomplexität: O(p)
• 6, Random Forest:
• # 🎜🎜##🎜🎜 #n= Anzahl der Trainingsbeispiele, f = Anzahl der Features, k = Anzahl der Bäume, p = Anzahl der Knoten im Baum, d = Tiefe des Baumes
• Trainingszeitkomplexität: O(n *log(n)*f*k)

Vorhersagezeitkomplexität: O(d*k)

Laufzeitraumkomplexität: O(p* k)

• 7, K nächster Nachbar:
• n= Anzahl der Trainingsbeispiele, f = Anzahl der Features, k= Anzahl der nächsten Nachbarn
• Brute :

Trainingszeitkomplexität: O(1)

Vorhersagezeitkomplexität: O(n*f+k*f)

#🎜🎜 #Laufzeit-Raumkomplexität: O(n*f)

kd-tree:

• Trainingszeitkomplexität: O (f*n* log(n))
• Vorhersagezeitkomplexität: O(k*log(n))
• Laufzeitraumkomplexität: O(n* f)

#🎜 🎜#

8, K-bedeutet Clustering:

• n= Anzahl der Trainingsbeispiele, f = Anzahl der Features, k= Anzahl der Cluster, i = Anzahl der Iterationen# 🎜🎜#
Trainingszeitkomplexität: O(n*f*k*i)
• Laufzeitraumkomplexität: O(n*f+k*f)
• #🎜🎜 #

Das obige ist der detaillierte Inhalt vonZusammenfassung der Rechenkomplexität von acht gängigen Algorithmen für maschinelles Lernen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!