2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
Es gibt viele Möglichkeiten und Methoden, das gleiche Algorithmusproblem zu lösen. Das Endergebnis ist dasselbe und korrekt, aber die Effizienz kann variieren.
Genauso wie man von demselben Ort aus startet und an einem anderen Ort ankommt, sind auch die Wege, um den Ort zu erreichen, Flugzeuge, Züge, Privatautos... aber die benötigte Zeit ist unterschiedlich und auch die Wirtschaftlichkeit ist unterschiedlich.
Nachdem der Algorithmus in ein ausführbares Programm geschrieben wurde, benötigt er Zeitressourcen und Platzressourcen (Speicherressourcen), um ausgeführt zu werden. Daher wird die Qualität eines Algorithmus im Allgemeinen anhand von zwei Dimensionen gemessen: Zeit und Raum, nämlich Zeitkomplexität und Raumkomplexität.
Die Zeitkomplexität misst hauptsächlich, wie schnell ein Algorithmus ausgeführt wird, während die Raumkomplexität hauptsächlich den zusätzlichen Platz misst, der zum Ausführen eines Algorithmus erforderlich ist.
In den Anfängen der Computerentwicklung verfügten Computer über eine sehr geringe Speicherkapazität. Daher legen wir großen Wert auf die Komplexität des Weltraums. Nach der rasanten Entwicklung der Computerindustrie hat die Speicherkapazität von Computern jedoch ein sehr hohes Niveau erreicht. Jetzt müssen wir der räumlichen Komplexität eines Algorithmus keine besondere Aufmerksamkeit mehr schenken.
Wenn ich einige Spiele spiele, wird mein Telefon sehr heiß, wenn ich sie spiele, und einige Spiele werden nicht heiß, wenn ich sie spiele, was untrennbar mit der Komplexität verbunden ist. Mein Telefon führt einen einfachen Algorithmus aus und es läuft schnell, aber es Der Algorithmus ist kompliziert auszuführen. Um sicherzustellen, dass weniger Zeit verbraucht wird, muss die volle Leistung aktiviert werden, damit es heiß wird.
Definition: In der Informatik ist die Zeitkomplexität eines Algorithmus eine Funktionsformel T(N), die die Laufzeit des Algorithmus quantitativ beschreibt. Zeitkomplexität misst die Zeiteffizienz eines Programms. Warum also nicht die Laufzeit des Programms berechnen?
- Da die Programmlaufzeit mit der Konfiguration der Kompilierungsumgebung und der laufenden Maschine zusammenhängt. Wenn beispielsweise ein Algorithmusprogramm mit einem alten Compiler oder mit einem neuen Compiler kompiliert wird, ist die Laufzeit auf derselben Maschine unterschiedlich.
- Das gleiche Algorithmusprogramm hat unterschiedliche Laufzeiten, wenn eine alte Maschine mit niedriger Konfiguration und eine neue Maschine mit hoher Konfiguration verwendet wird.
- Und die Zeit kann erst getestet werden, nachdem das Programm geschrieben wurde, und nicht durch theoretisches Denken berechnet und bewertet werden, bevor das Programm geschrieben wird.
Daher wird bei der Beurteilung des Zeitzuweisungsgrads eines Algorithmus nicht die Zeit zur Ausführung des Algorithmus berücksichtigt, sondern nur die Anzahl der ausgeführten Anweisungen.
Fall:
// 请计算⼀下Func1中++count语句总共执⾏了多少
次？
void Func1(int N)
{
int count = 0;
for (int i = 0; i < N ; ++ i)
{
for (int j = 0; j < N ; ++ j)
{
++count;
}
}
for (int k = 0; k < 2 * N ; ++ k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
}
Durch Beobachtung:
Anzahl der von Func1 ausgeführten Grundoperationen:
T(N) = N2+ 2*N + 10
In der Praxis ist es bei der Berechnung der Zeitkomplexität immer noch sehr mühsam, die genaue Anzahl der Ausführungen des Programms zu berechnen (verschiedene Sätze des Programmcodes haben eine unterschiedliche Anzahl kompilierter Anweisungen (z. B.). Die Berechnung der genauen Anzahl der Ausführungen ist von geringer Bedeutung, da wir bei der Berechnung der Zeitkomplexität nur den Wachstumsgrad des Algorithmusprogramms vergleichen möchten, dh den Unterschied in T(N), wenn N weiter zunimmt Ich habe oben gesehen, dass Konstanten und Terme niedriger Ordnung nur geringe Auswirkungen auf die Ergebnisse haben, wenn N weiter wächst. Daher müssen wir nur die ungefähre Anzahl der Ausführungen berechnen, die das Programm darstellen kann, um die Größenordnung zu erhöhen Wird normalerweise verwendet. Verwenden Sie die asymptotische Notation von Big O.
Raumkomplexität ist auch ein mathematischer Ausdruck, bei dem es sich um den zusätzlichen Raum handelt, der aufgrund der Anforderungen des Algorithmus während des Betriebs eines Algorithmus vorübergehend zugewiesen wird.
Die Speicherplatzkomplexität gibt nicht an, wie viele Bytes Speicherplatz das Programm einnimmt. Da sich die Größe der einzelnen Objekte unter normalen Umständen nicht stark unterscheidet, wird die Speicherplatzkomplexität anhand der Anzahl der Variablen berechnet.
Die Regeln zur Berechnung der Raumkomplexität ähneln im Wesentlichen der praktischen Komplexität, und es wird auch die asymptotische Big-O-Notation verwendet.
Hinweis: Der beim Ausführen der Funktion erforderliche Stapelspeicherplatz (Speichern von Parametern, lokalen Variablen, einigen Registerinformationen usw.) wurde während der Kompilierung bestimmt, sodass die Speicherplatzkomplexität hauptsächlich durch den zusätzlichen Speicherplatz bestimmt wird, den die Funktion während der Laufzeit explizit beantragt . Sicher
Bei der aktuellen Computerentwicklung spielt Platz keine zentrale Rolle, aber übermäßiger Abfall muss vermieden werden. Zu viel Abfall führt zu unnötigen Problemen.
Big-O-Notation: Es handelt sich um ein mathematisches Symbol, das zur Beschreibung des asymptotischen Verhaltens von Funktionen verwendet wird.
Regeln für die Umstellung auf die asymptotische Big-O-Notation:
- 1. In der Zeitkomplexitätsfunktionsformel T(N) werden nur die Terme höchster Ordnung beibehalten und die Terme niedriger Ordnung entfernt, denn wenn N weiter zunimmt,
Der Einfluss von Termen niedriger Ordnung auf die Ergebnisse wird immer geringer, und wenn N unendlich ist, können sie ignoriert werden.- 2. Wenn der Term höchster Ordnung existiert und nicht 1 ist, entfernen Sie den konstanten Koeffizienten dieses Termes, da dieser Koeffizient mit zunehmendem N weiter zunimmt
Der Einfluss auf die Ergebnisse wird immer geringer, und wenn N unendlich ist, kann er ignoriert werden.- 3. Wenn es in T(N) keine N-bezogenen Elemente, sondern nur konstante Elemente gibt, ersetzen Sie alle additiven Konstanten durch die Konstante 1.
Schlimmster Fall: maximale Anzahl von Läufen (Obergrenze) für jede Eingabegröße
Durchschnittsfall: erwartete Anzahl von Läufen für jede Eingabegröße
Bester Fall: Mindestanzahl von Läufen (Untergrenze) für jede Eingabegröße
In der Praxis konzentriert sich die asymptotische Darstellung von Big O im Allgemeinen auf die Obergrenze des Algorithmus, die die schlechteste Betriebssituation darstellt.
void Func1(int N)
{
int count = 0;
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j)
{
++count;
}
}
for (int k = 0; k < 2 * N; ++k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
}
Zeitkomplexität:
Lassen Sie den Code weg, der einmal ausgeführt wird, z. B. count = 0, diesen Code.
Behalten Sie die Anzahl der Codeausführungen bei, die einen großen Einfluss auf die Laufzeit haben
Die Anzahl der Ausführungen der ersten Schleife entspricht einer Doppelschleifenausführung von NN
Die zweite Schleife ist eine Schicht mit Schleifenausführungszeiten 2N
Der dritte Zyklus dauert 10 Mal
Die Summe der Anzahl der Ausführungen beträgt T(N)=N2+2*N+10
Big O steht für zeitliche Komplexität. Verwerfen Sie die kleinen Auswirkungen und nehmen Sie das Limit
AN2)
Raumkomplexität:
Die Funktion Func1 gilt für die Größe des Leerzeichens. Beispielsweise gilt int count = 0, sie gilt für die Leerzeichengröße des Typs int M=10, sie gilt auch für die Leerzeichengröße des Typs int.
Diese beiden Leerzeichen werden auch in der Schleife verwendet, ohne dass zusätzlicher Anwendungsraum erforderlich ist.
Die Größe des Anwendungsspeichers ist konstant
Die in Big O ausgedrückte Raumkomplexität ist:
O (1)
void Func2(int N)
{
int count = 0;
for (int k = 0; k < 2 * N; ++k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
printf("%dn", count);
}
Zeitkomplexität:
Die Häufigkeit, mit der der Code ausgeführt wird, ist größer als die der ersten Schleife, nämlich N*2.
Die zweite Schleife läuft 10 Mal
Verwenden Sie großes O, um die Zeitkomplexität darzustellen. Der größte Einfluss ist 2*N. Der vorherige Koeffiziententerm wird weggelassen:
AN)
void Func3(int N, int M)
{
int count = 0;
for (int k = 0; k < M; ++k)
{
++count;
}
for (int k = 0; k < N; ++
k)
{
++count;
}
printf("%dn", count);
}
Zeitkomplexität
Es gibt zwei Unbekannte, und die größeren Auswirkungen wirken sich auf die beiden Schleifen aus
Die erste Schleife läuft M-mal
Die zweite Schleife wird N-mal ausgeführt
Es sollte eine unbekannte Zahl sein. Ich bin mir nicht sicher, welche größer und welche kleiner ist.
O (M+N)
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++k)
{
++count;
}
printf("%dn", count);
}
Zeitkomplexität:
Die größte Auswirkung hier ist ein Zyklus
Die Anzahl der Schleifendurchläufe beträgt 100
ist eine feste Konstante
O (1)
const char* strchr(const char* str, int character)
{
const char* p_begin = str;
while (*p_begin != character)
{
if(*p_begin == '0')
return NULL;
p_begin++;
}
return p_begin;
}
Die Funktion dieser Funktion besteht darin, den Index eines Zeichens in einem Array zu finden.
Die Anzahl der Läufe ist hier ungewiss
Es ist möglich, F(N)=1 auf einmal zu finden
Es ist möglich, F(N)=N/2 in der Mitte zu finden
Es kann am Ende gefunden werden, oder NULL wird zurückgegeben, wenn es nicht gefunden wird, F(N)=N
Big O geht vom Worst-Case-Szenario aus:
Die Zeitkomplexität ist O(N)
void func5(int n)
{
int cnt = 1;
while (cnt < n)
{
cnt *= 2;
}
}
Diese Anzahl von Durchläufen hängt von der Größe von n ab, aber es wird nicht n-mal wiederholt. Dies sollte daran liegen, dass die Schleifenvariable während der Schleife mit 2 multipliziert wird und die Schleife schnell herausspringt Der Wert der Schleifenvariablen cnt erreicht 1024.
Angenommen, die Anzahl der Zyklen ist x, dann 2X=n
x=logn
Die Zeitkomplexität ist also: O(longn)
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; ++i)
{
if (a[i - 1] > a[i])
{
Swap(&a[i - 1], &a[i]);
exchange = 1;
}
}
if(exchange == 0)
break;
}
}
Diese Funktion vervollständigt die aufsteigende Blasensortierung
Hier gibt es eine Schleife. Diese Schleife ist eine zweistufige verschachtelte Schleife.
Die Anzahl der Schleifen ist undefiniert
Im schlimmsten Fall läuft die äußere Schleife n-mal
Dann wird die innere Schleife (n-1)+(n-2)+(n-3)+……+2+1+0 ausführen
ist eine arithmetische Folge und die Summe ist:
Zeitkomplexität ist: O(N)
Raumkomplexität:
Es gibt keinen zusätzlichen Anwendungsraum und der angewandte Raum ist konstant.
O (1)
long long Fac(size_t N)
{
if (0 == N)
return 1;
return Fac(N - 1) * N;
}
Zeitkomplexität:
N-mal rekursiv
Die Zeitkomplexität ist also: O(N)
Raumkomplexität:
Jedes Mal, wenn Sie rekursiv sind, müssen Sie sich um einen Platz bewerben.
N-mal rekursiv und für N-mal Raum angewendet.
Die Raumkomplexität ist: O(N)
Er widmet sich seit mehr als 30 Jahren der Technologieforschung und beherrscht verschiedene Sprachen wie Java, Linux, Javascript, PHP, CSS usw. Er hat viele Beiträge im Open-Source-Bereich geleistet Entwicklerdokumentationsstation, um einige Themen in der Technologieentwicklung als zukünftige Referenz zu teilen
