Berechnung der Laufzeit aus Zeitkomplexität

Ich habe von groß gelesen Ö Notation für Zeitkomplexität und für Zählfunktionen wie die für Primzahlen. Kürzlich las ich auf StackOverflow:

Das Problem bei der Definition der Ausführungsdauer eines Algorithmus besteht darin, dass Sie normalerweise keine Antwort in Millisekunden geben können, da dies von der Maschine abhängt, und Sie können keine Antwort in Taktzyklen oder als Anzahl der Operationen geben, da dies der Fall wäre zu spezifisch für bestimmte Daten, um nützlich zu sein.

https://stackoverflow.com/questions/11806021/how-does-one-calculate-the-runtime-of-an-algorithm

Meine Frage ist, wenn wir einen Algorithmus betrachten, der mit einer bekannten Zeitkomplexität (Polynom, linear usw.) auf einer Maschine läuft, deren Parameter bekannt sind, wie können wir die Laufzeit in Sekunden berechnen? Wie kann im Wesentlichen die Zeitkomplexität für eine bestimmte Maschine in Echtzeit übersetzt werden?

Ich frage, weil ich Fälle gesehen habe, in denen Leute gesagt haben X Algorithmus dauert j Zeit zu rennen.

Nach dem, was ich nach dem Lesen der Wikipedia-Seite zur Zeitkomplexität verstehe, würde ich denken, dass es sich um den Polynomwert oder die Anzahl der Berechnungen geteilt durch die Anzahl der Berechnungen handelt, die eine bestimmte Maschine pro Zeiteinheit verarbeiten kann. Ist das richtig? Gibt es eine allgemeine Antwort?

Die mit Big-O bezeichnete Komplexität sagt nur etwas über das Wachstum der Rechenzeit aus, wenn die Eingabegröße wächst. Dies reicht nicht aus, um auf die genaue Laufzeit zu schließen.

Antworten (1)

Grundsätzlich entstand das Konzept der Zeitkomplexität, als man die Zeitabhängigkeit eines Algorithmus von der Eingabegröße wissen wollte, es aber nie beabsichtigt war, die genaue Laufzeit des Algorithmus zu berechnen. Da es von einer Reihe von Faktoren abhängt, wie Prozessor, Betriebssystem, Prozesse und vielen vielen mehr ..., die nicht alle in Big-O-Notation berücksichtigt werden können, da alle Terme niedrigeren Grades ignoriert werden.

Das macht Sinn. Daraus schließe ich, dass es systemabhängig ist und nicht verallgemeinert werden kann. Was ist jedoch mit konstanter Zeit, wo es keine Terme niedrigeren Grades mehr gibt?
@Gnumbertester Es ist schwer, sich einen Algorithmus vorzustellen, der unabhängig von seiner Eingabe ist, aber wenn es einen solchen Algorithmus gab, muss diese Konstante wieder mit dem System variiert haben. und muss für jedes System individuell bestimmt werden. ich hoffe es hat geholfen :)
es gibt auch solche algorithmen, die unabhängig von ihrer eingabegröße sind
Berechnung der Laufzeit aus Zeitkomplexität
AntwortenHierDatenschutz-Bestimmungen1y, 0v