Technologieaustausch

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Vorwort

Wenn Sie wissen möchten, was Raum-Zeit-Komplexität ist, müssen Sie wissen, was eine Datenstruktur ist.

Dies kann auf zwei Ebenen verstanden werden. Daten existieren überall in unserem Leben, wie zum Beispiel internationale Ereignisse, die ein heißes Thema bei Douyin sind, Yongzhengs Rüstungsentfernung usw. Was unsere Benutzer sehen können, sind die Daten, die Douyin auf dem Backend-Server speichert. Diese Daten haben jedoch alle ein Merkmal: Sie befinden sich alle auf der Hot-Search-Liste von Douyin. Diese Liste ist so strukturiert, dass sichergestellt ist, dass sich die Daten an einem festen Ort befinden, damit Benutzer sie durchsuchen können.

Darüber hinaus sind Algorithmen untrennbar mit Datenstrukturen verbunden. Nun, wie wir gerade gesagt haben, speichert eine Datenstruktur regelmäßig Daten in einer Struktur. Der effiziente Zugriff auf Daten aus der Struktur ist also ein Algorithmus.

Zeitkomplexität

Bei Algorithmen gibt es Zeitkomplexität und Raumkomplexität. Da der Speicher von Computern immer größer wird, ist die zeitliche Komplexität wichtiger als die räumliche Komplexität.Lassen Sie uns zunächst die zeitliche Komplexität verstehen

Konzept

Zeitkomplexität, das wichtigste Wort ist Zeit. Die Zeit bezieht sich hier auf die Zeit, in der ein Programm ausgeführt wird. Wenn die Zeitkomplexität geringer ist, hat sich der Algorithmus als besser erwiesen.Die Berechnung der Zeitkomplexität wird durch die Funktionsformel T(N) ausgedrückt.

Warum berechnen wir also nicht die zeitliche Komplexität dieses Programms im Voraus und schreiben den Code für die optimale Lösung? Dabei handelt es sich um Computerprobleme.

1. Da die Programmlaufzeit mit der Kompilierungsumgebung und der Konfiguration der laufenden Maschine zusammenhängt, verwendet beispielsweise ein Algorithmusprogramm einen alten Compiler
   Das Kompilieren mit einem neuen Compiler und das Kompilieren mit einem neuen Compiler haben unterschiedliche Laufzeiten auf demselben Computer.
2. Das gleiche Algorithmusprogramm hat unterschiedliche Laufzeiten, wenn eine alte Maschine mit niedriger Konfiguration und eine neue Maschine mit hoher Konfiguration verwendet wird.
3. 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.

Schauen wir uns einen Code an:

// 请计算⼀下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;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

Wenn Sie diesen Code anhand der Anzahl der Ausführungen von count betrachten, sollte er wie folgt lauten:
T (N) = N2 + 2 ∗ N + 10
• N = 10 T(N) = 130
• N = 100 T(N) = 10210
• N = 1000 T(N) = 1002010

Zu diesem Zeitpunkt sagte jemand, dass int count=0 nicht zählt;

Hier unterschätzen wir unseren Computer zu sehr. Die CPU unseres Computers kann Hunderte Millionen Mal pro Sekunde ausgeführt werden. Diese kleine Zeit kann natürlich ignoriert werden. Daher ist die von uns berechnete Zeitkomplexität nicht genau, sondern nur eine grobe Schätzung. Zu diesem Zeitpunkt verwenden wir ein neues Symbol, um sie darzustellen.

Asymptotische Darstellung von Big O

Big-O-Notation: Es handelt sich um ein mathematisches Symbol zur Beschreibung des asymptotischen Verhaltens einer Funktion. Es wird hier zur Darstellung der geschätzten Zeitkomplexität verwendet.

Zählt es hier also immer noch wie T(N)? Wenn ja, müssen wir kein anderes Symbol verwenden, um es darzustellen. Dabei handelt es sich um die Regeln zum Zählen von O:

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, wird der Einfluss von Termen niedriger Ordnung auf das Ergebnis immer kleiner. Wenn N unendlich ist, kann es 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 immer weniger Einfluss auf das Ergebnis hat. 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.

Schauen Sie sich dann das obige T(N)=N^ 2 + 2 ∗ N + 10 an. Die höchste Ordnung ist hier N2. Wenn Sie also andere niedrige Ordnungen entfernen, beträgt die Komplexität (ON^2).

Kleiner Zerkleinerer

// 计算Func3的时间复杂度？
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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Hier ist T(N)=M+N, dann berechnen wir noch einmal O(N), M und N liegen hier beide in der gleichen Reihenfolge, entsprechen also nicht der ersten Regel und entsprechen nicht der zweiten und dritten Regel , also o(N+M), dann fragte jemand: Was ist, wenn N größer als M ist, sollte es O(N) sein? Die Frage hier ist: Woher weiß man, dass N größer als M ist? Was ist, wenn M größer als N ist, also bleiben wir hier, nur um auf der sicheren Seite zu sein.

// 计算strchr的时间复杂度？
const char * strchr ( const char
 * str, int character)
{
const char* p_begin = s;
while (*p_begin != character)
{
if (*p_begin == '0')
return NULL;
p_begin++;
}
return p_begin;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

Hier suchen wir nach der Position des Charakters in str. Hier füge ich einen Wissenspunkt hinzu:

• Unsere O-Berechnung ist im Allgemeinen die Worst-Case-Komplexität eines Algorithmus.
  Dabei lässt es sich in drei Komplexitätsstufen einteilen:
  1. Best-Case-Szenario
  Um das Zeichen an der ersten Position der Zeichenfolge zu finden, gehen Sie wie folgt vor:
  F (N) = 1, Komplexität ist o(1)

2. Durchschnittssituation:
Um das Zeichen in der Mitte der Zeichenfolge zu finden, gehen Sie wie folgt vor:
F (N) = N/2,O(N/2)

3. Worst-Case-Szenario
Um das Zeichen an der letzten Position der Zeichenfolge zu finden, gehen Sie wie folgt vor:
F (N) = N,O(N)

// 计算BubbleSort的时间复杂度？
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;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Im schlimmsten Fall ist es ON^2, da die hohe Ordnung beibehalten wird und n/2 entfernt wird (das erste Element) und der Koeffizient (das zweite Element) ignoriert wird

void func5(int n)
{
int cnt = 1;
while (cnt < n)
{
cnt *= 2;
}
}
1
2
3
4
5
6
7
8

Wenn n=2, beträgt die Anzahl der Ausführungen 1
Bei n=4 beträgt die Anzahl der Ausführungen 2
Bei n=16 beträgt die Anzahl der Ausführungen 4
Angenommen, die Anzahl der Ausführungen beträgt x, dann 2
x = n
Daher ist die Anzahl der Ausführungen: x = log n
Daher: Die zeitliche Komplexität von func5 im schlimmsten Fall ist:
O(log2 ^n)

Verschiedene Bücher haben unterschiedliche Ausdrucksmethoden. Die oben genannten Schreibmethoden sind nicht sehr unterschiedlich. Wir empfehlen die Verwendung von log n

Raumkomplexität

Bei der Raumkomplexität ist zu beachten, dass ihre Berechnungsdarstellung ebenfalls durch O dargestellt wird und ihre Regeln denselben drei Regeln folgen wie die Zeitkomplexität.

Beachten

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 beim Ausführen explizit beantragt .

Beispiel 1:

// 计算BubbleSort的时间复杂度？
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;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Der Funktionsstapelrahmen wurde während der Kompilierung ermittelt.
Sie müssen lediglich auf den zusätzlichen Speicherplatz achten, den die Funktion zur Laufzeit anfordert.
Zusätzlicher Anwendungsraum für BubbleSort ist
Es gibt eine begrenzte Anzahl lokaler Variablen, z. B. Exchange, die konstant viel zusätzlichen Speicherplatz beanspruchen.
Die Raumkomplexität ist also O(1)