Hausaufgaben - Big O Notation und Rechenzeit

Question

lassen Sie sich sagen, dass ich einen Algorithmus, die 0,5 ms für n = 20, und ich möchte, um herauszufinden, dauert wie lange es dauert, wenn n = 40 für O (n^2).

Zu meinem Verständnis ist das Verfahren wie folgt:

t = 0,5 * (40^2/20^2)

Aber warum ist das? Ich verstehe die Mechanik dahinter nicht. Ich weiß, dass Big O eine obere Schranke ist, und für jedes n ist es eine Ausgabe einiger Instruktionen. Aber die Zeit zu berechnen macht keinen Sinn.

Answer 1

lassen Sie uns sagen, dass ich einen Algorithmus, die 0,5 ms für n = 20, und ich möchte, um herauszufinden, dauert wie lange es dauert, wenn n = 40 für O (n^2).

Leider kann man über das Verhalten folgern für n = 40 fast nichts.

Die Aussage, dass der Algorithmus O (n) bedeutet, dass es ein konstantes c> 0, für die, für die groß genug n, die Laufzeit existiert, ist nicht größer als cn. Folglich Sie wissen nicht, ob 20, 40 oder 4.000.000 fällt in „groß genug“ n, und selbst wenn es der Fall ist, können Sie nur wissen, dass es von oben etwas begrenzt ist.

Aber die Berechnung der Zeit macht keinen Sinn.

Das ist eine logische Schlussfolgerung, leider.

---

bearbeiten

Dank der hervorragenden Kommentar von Anmol Singh Jaggi (vielen Dank!), Hier ist die Figur, die er zusammen, dass das Problem