Effizienzschätzer
Berechnen Sie die Zeitkomplexität von Funktionen und Algorithmen.
Kopieren Sie diese Aufforderung in unsere Entwickler-Konsole, um es selbst auszuprobieren!
Inhalt | |
---|---|
System | Ihre Aufgabe ist es, die bereitgestellte Funktion oder den Algorithmus zu analysieren und dessen Zeitkomplexität mit der Big-O-Notation zu berechnen. Erklären Sie Ihre Überlegungen Schritt für Schritt und beschreiben Sie, wie Sie zur endgültigen Zeitkomplexität gelangt sind. Berücksichtigen Sie bei der Bestimmung der Zeitkomplexität den ungünstigsten Fall. Wenn die Funktion oder der Algorithmus mehrere Schritte oder verschachtelte Schleifen enthält, geben Sie die Zeitkomplexität für jeden Schritt an und nennen Sie dann die Gesamtzeitkomplexität für die gesamte Funktion oder den gesamten Algorithmus. Gehen Sie davon aus, dass alle verwendeten eingebauten Funktionen oder Operationen eine Zeitkomplexität von O(1) haben, sofern nicht anders angegeben. |
User | def example_function(n): for i in range(n): print(i) for j in range(n): for k in range(n): print(j, k) |
Beispielausgabe
Um die Zeitkomplexität der gegebenen Funktion
example_function(n)
zu analysieren, werden wir sie in Schritte unterteilen und den ungünstigsten Fall betrachten.Schritt 1: Analyse der ersten Schleife
for i in range(n): print(i)
Diese Schleife wird
n
mal durchlaufen und führt bei jeder Iteration eine Operation mit konstanter Zeit (print(i)
) aus. Daher beträgt die Zeitkomplexität dieses Schritts O(n).Schritt 2: Analyse der verschachtelten Schleifen
for j in range(n): for k in range(n): print(j, k)
Die äußere Schleife wird
n
mal durchlaufen, und für jede Iteration wird die innere Schleife ebenfallsn
mal durchlaufen. Bei jeder Iteration der inneren Schleife wird eine Operation mit konstanter Zeit (print(j, k)
) ausgeführt. Daher beträgt die Zeitkomplexität der verschachtelten Schleifen O(n * n) = O(n^2).Schritt 3: Kombination der Zeitkomplexitäten
Die Funktionexample_function(n)
besteht aus zwei Schritten: der ersten Schleife und den verschachtelten Schleifen. Die Gesamtzeitkomplexität ist die Summe der Zeitkomplexitäten jedes Schritts.Zeitkomplexität der ersten Schleife: O(n)
Zeitkomplexität der verschachtelten Schleifen: O(n^2)Um die Gesamtzeitkomplexität zu bestimmen, betrachten wir den dominanten Term, d.h. den Term mit der höchsten Wachstumsordnung. In diesem Fall dominiert O(n^2) gegenüber O(n).
Daher beträgt die Gesamtzeitkomplexität der Funktion
example_function(n)
O(n^2).Im ungünstigsten Fall, wenn
n
groß ist, werden die verschachtelten Schleifen die Ausführungszeit dominieren und die Funktion eine quadratische Zeitkomplexität aufweisen.
API-Anfrage
Hinweis: Claude 3 Opus wird bald für die Bedrock API verfügbar sein.