Wie ermittle ich die Laufzeit bei gegebener Algorithmus- und Computer-Geschwindigkeit?

Question

Ich arbeite gerade an einer Aufgabe, die sich mit Big-O und Laufzeiten beschäftigt. Mir wurde eine Frage vorgelegt, die sehr einfach zu sein scheint, aber ich bin mir nicht sicher, ob ich sie richtig löse. Die restlichen Aufgaben waren ziemlich schwierig, und ich habe das Gefühl, dass ich hier etwas übersehe.

Erstens: Sie haben diese Dinge: Algorithmus A, der eine Laufzeit von 50n^3 hat. Computer A, der eine Geschwindigkeit von 1 Millisekunde pro Operation hat. Computer B, der eine Geschwindigkeit von 2 Millisekunden pro Operation hat. Eine Instanz der Größe 300.

Ich möchte herausfinden, wie lange Algorithmus A braucht, um diesen Fall auf Computer A zu lösen, und wie lange er auf Computer B braucht.

Ich möchte n durch 300 ersetzen, so dass Sie 50*(300^2) = 4500000 erhalten.

Dann multiplizieren Sie diesen Wert mit 1 für den ersten Computer und mit 2 für den zweiten Computer.

Das kommt mir allerdings seltsam vor, weil es heißt, die "Laufzeit" sei 50n^3, nicht "die Anzahl der Operationen ist 50n^3", so dass ich das Gefühl habe, dass ich Zeit mit Zeit multipliziere und am Ende Einheiten von Millisekunden zum Quadrat hätte, was überhaupt nicht richtig erscheint.

Ich würde gerne wissen, ob ich richtig liege, und wenn nicht, was die Frage eigentlich bedeutet.

Answer 1

Es würde keinen Sinn machen, wenn Sie O(n^3) hätten, aber Sie verwenden in Ihrem Beispiel keine Big-O-Notation. D.h. wenn Sie O(n^3) hätten, wüssten Sie die Komplexität Ihres Algorithmus, aber nicht die genaue Anzahl der Operationen, wie Sie sagten.

Stattdessen sieht es so aus, als ob Sie die genaue Anzahl der Operationen erhalten, die durchgeführt werden. (Auch wenn dies nicht ausdrücklich angegeben ist). Es wäre also sinnvoll, n zu ersetzen.

Die Big-O-Notation beschreibt, wie sich die Größe der Eingabe auf die Laufzeit oder den Speicherverbrauch auswirkt. Mit Big O kann man jedoch keine genaue Laufzeit ableiten, selbst wenn man die Geschwindigkeit der einzelnen Operationen kennt.

Eine Erklärung, warum Ihre Antwort so einfach aussieht (wie ich es oben beschrieben habe), wäre auch ein sicherer Weg. Aber ich bin mir sicher, dass Sie die Frage auch ohne diese Erklärung gut bewerten können.

Answer 2

Nun, abgesehen davon, dass es sinnlos ist, auf diese Weise herauszufinden, wie lange etwas auf den meisten modernen Computern dauern wird, obwohl es vielleicht eine einige Bedeutung in einem eingebetteten System, sieht es für mich richtig aus, so wie Sie es gemacht haben.

Wenn der Algorithmus 50n^3 Operationen benötigt, um etwas abzuschließen, wobei n die Anzahl der zu verarbeitenden Elemente ist, dann erhält man, wenn man 300 für n einsetzt, die Anzahl der auszuführenden Operationen und nicht eine Zeiteinheit.

Multiplizieren Sie also mit der Zeit pro Vorgang und Sie erhalten die benötigte Zeit.

Sieht für mich richtig aus.

Answer 3

Ihre 50*n^3-Daten werden als "Laufzeit" bezeichnet, aber das liegt daran, dass das für die Geschwindigkeitsbewertung verwendete Modell von einer Maschine mit mehreren Grundoperationen ausgeht, wobei jede dieser Operationen 1 Zeiteinheit benötigt.

In Ihrem Fall dauert die Ausführung des Algorithmus 50*500^3 Zeiteinheiten. Auf Computer A beträgt jede Zeiteinheit 1 ms und auf Computer B 2 ms.

Ich hoffe, dass dies den Einheiten zu denken gibt,
Asaf.