Ordnung der Komplexität ist ein Begriff, der in der Informatik verwendet wird, um die Effizienz eines Algorithmus oder eines Programms zu messen. Es bezieht sich auf die Menge an Zeit und Ressourcen, die erforderlich sind, um ein Problem zu lösen oder eine Aufgabe auszuführen. In der Programmierung wird die Ordnung der Komplexität normalerweise in Form von ausgedrückt Big O Notation, die eine Obergrenze für den Zeit- oder Platzbedarf eines Algorithmus angibt. In diesem Artikel werden wir die Ordnung der Komplexität in der Programmiersprache C und ihre Bedeutung diskutieren.
Reihenfolge der Komplexität in der Programmiersprache C:
Bei der C-Programmierung hängt die Komplexitätsordnung eines Algorithmus von der Anzahl der vom Programm ausgeführten Operationen ab. Wenn wir beispielsweise ein Array der Größe n haben und nach einem bestimmten Element im Array suchen möchten, hängt die Komplexitätsordnung des Algorithmus von der Anzahl der Elemente im Array ab. Wenn wir eine durchführen Lineare Suche Durch das Array wird die Reihenfolge der Komplexität sein An) , was bedeutet, dass die Zeit, die für die Suche nach dem Element benötigt wird, linear mit der Größe des Arrays zunimmt. Wenn wir a verwenden Binärer Suchalgorithmus stattdessen wird die Ordnung der Komplexität sein O(log n) , was bedeutet, dass die Zeit, die für die Suche nach dem Element benötigt wird, logarithmisch mit der Größe des Arrays zunimmt.
Ebenso ist die Ordnung der Komplexität anderer Algorithmen, wie z Sortieralgorithmen , Graphalgorithmen , Und Dynamische Programmieralgorithmen hängt auch von der Anzahl der Operationen ab, die das Programm ausführt. Die Komplexitätsordnung dieser Algorithmen kann mit ausgedrückt werden Big O Notation.
Werfen wir einen Blick auf einige gängige Komplexitätsordnungen und die entsprechenden Algorithmen:
Das bedeutet, dass der Algorithmus unabhängig von der Eingabegröße eine konstante Zeit benötigt. Der Zugriff auf ein Element in einem Array dauert beispielsweise O(1) Zeit, da auf das Element direkt über seinen Index zugegriffen werden kann.
Dies bedeutet, dass die vom Algorithmus benötigte Zeit logarithmisch mit der Eingabegröße zunimmt. Dies wird häufig beobachtet in Divide-and-Conquer-Algorithmen wie Binäre Suche , die die Eingabe in kleinere Teile aufteilen, um das Problem zu lösen.
Dies bedeutet, dass die benötigte Zeit des Algorithmus linear mit der Eingabegröße zunimmt. Beispiele für solche Algorithmen sind Lineare Suche Und Blasensortierung .
Das bedeutet, dass sich die benötigte Zeit des Algorithmus um n multipliziert mit dem Logarithmus von n erhöht. Beispiele für solche Algorithmen sind Schnelle Sorte Und Zusammenführen, sortieren .
Dies bedeutet, dass die benötigte Zeit des Algorithmus quadratisch mit der Eingabegröße zunimmt. Beispiele für solche Algorithmen sind Blasensortierung Und Sortieren durch Einfügen .
Dies bedeutet, dass sich die Zeit, die der Algorithmus benötigt, mit jeder Vergrößerung der Eingabegröße verdoppelt. Dies wird häufig beobachtet in Rekursive Algorithmen wie Fibonacci-Reihe .
Es ist wichtig zu wissen, dass die Ordnung der Komplexität nur eine Obergrenze für die vom Algorithmus benötigte Zeit darstellt. Die tatsächlich benötigte Zeit kann abhängig von den Eingabedaten und der Implementierung des Algorithmus viel kürzer als diese Grenze sein.
SIM-Karte eingelegt, aber kein Service-Android
Bei der C-Programmierung kann die Komplexitätsordnung eines Algorithmus durch die Analyse des Codes und das Zählen der Anzahl der durchgeführten Operationen bestimmt werden. Wenn wir beispielsweise eine Schleife haben, die ein Array der Größe n durchläuft, beträgt die zeitliche Komplexität der Schleife An) . Wenn wir eine rekursive Funktion haben, die sich selbst k-mal aufruft, beträgt die zeitliche Komplexität der Funktion ebenfalls O(2^k) .
Um die Leistung eines Programms zu optimieren, ist es wichtig, Algorithmen mit einer niedrigeren Komplexitätsordnung auszuwählen. Wenn wir beispielsweise ein Array sortieren müssen, sollten wir einen Sortieralgorithmus mit einer geringeren Komplexität verwenden, z Schnelle Sorte oder Zusammenführen, sortieren , statt Blasensortierung , was eine höhere Komplexitätsordnung aufweist.
Reihenfolge der Komplexität analysieren:
Um die Komplexitätsordnung eines Algorithmus zu analysieren, müssen wir bestimmen, wie seine Laufzeit oder sein Speicherplatzbedarf mit zunehmender Eingabegröße zunimmt. Die gebräuchlichste Methode hierfür besteht darin, die Anzahl der vom Algorithmus ausgeführten Grundoperationen zu zählen.
Eine Grundoperation ist eine Operation, deren Ausführung eine konstante Zeit in Anspruch nimmt, beispielsweise das Addieren zweier Zahlen oder der Zugriff auf ein Array-Element. Indem wir die Anzahl der vom Algorithmus durchgeführten Grundoperationen als Funktion der Eingabegröße zählen, können wir seine Komplexitätsordnung bestimmen.
Betrachten Sie beispielsweise die folgende C-Funktion, die die Summe der ersten n ganzen Zahlen berechnet:
C-Code:
int sum(int n) { int total = 0; for (int i = 1; i <= n; i++) { total +="i;" } return total; < pre> <p>In this function, the loop runs n times, and each iteration performs a constant amount of work (adding i to the total). Therefore, the number of basic operations performed by this algorithm is proportional to n, and its time complexity is <strong>O(n)</strong> .</p> <hr></=>