Laufzeit berechnen (Informatik)

Question

Ein Computerprogramm führe auf einer Eingabe der Länge n ∈ N genau T(n) Rechenschritte aus. Ein Rechenschritt dauert 

10^{-9} sekunden. Berechnen Sie für jeden Eintrag, wie groß die Eingabegröße n maximal sein darf, damit ein Programm mit der gegebenen Laufzeitfunktion im angegebenen Zeitraum terminiert.

Ich soll jetzt die Laufzeit für 10^{-10} berechnen. Berechne log_{2}n für die Zeiträume 1 sek, 1 min, 1 Std, 1 Tag, 1 Monat

Ich weiß jetzt nicht wie ich das berechnen muss. Kann mir das jemand an einem Beispiel zeigen 

Comments

Vom Duplikat:

Titel: Laufzeitberechnung (Informatik)

Stichworte: informatik,logarithmus

Ein Computerprogramm führe auf einer Eingabe der Länge n ∈ N genau T(n) Rechenschritte aus. Wir gehen davon aus, dass ein Rechenschritt 10^-9 Sekunden dauert. In der unten stehenden Tabelle sind in der ersten Spalte Laufzeitfunktionen T(n) und in der ersten Zeile Zeiträume angegeben. Berechnen Sie für jeden Eintrag, wie groß die Eingabegröße n maximal sein darf, damit ein Programm mit der gegebenen Laufzeitfunktion im angegebenen Zeitraum terminiert.

Laut Vorlesung soll es so berechnet werden: Operationen / Operationen pro Sek. = Zeit

Ich habe eine etwas größere Tabelle, aber schon bei der ersten Berechnung hab ich etas gestutzt. Meine Rechnung sieht wie folgt aus:

Operation: log₂n ; Zeit: 1Sekunde  => log₂n / 10^9 = 1 <=> n = 2^{10^9}

Kann das sein ?

---

wenn du die Aufgabe nochmal liest, wirst du sehen, dass du die Tabelle für 10^-9 UND für 10^-10 berechnen sollst.

wenn du dir mal die Folien von Mittwoch anguckst, dann erkennst die, wie du das berechnen sollst. ich glaube Folie 17+18 war das Beispiel mit dem PC und dem supercomputer.

---

Wäre das für Log n für 1 sek.

(Log 10^9)/10^9 =9*10^{-9} richtig?

Und wäre die Operation für 1min 6*10^{-8}?

Answer 1

Hallo,

kommt mir auch sehr groß vor, aber ich kann in deiner Vorgehensweise keinen Fehler finden.

T(n) = log₂(n)  liefert natürlich auch recht kleine Werte für die Anzahl der benötigten Operationen.

Gruß Wolfgang

Comments

Alles klar, danke!

Answer 2

Da steht log₂n und nicht nur log n.

wenn du mal die daten aus der aufgabe so schreibst wie sie in der Tabelle stehen, dann hast du folgendes: Operation: log₂n ; Geschwindigkeit: 1 Operation dauert 10^{-9} sek, macht also 10^9 Operationen pro sek

also: log₂n / 10^9 = 1 und jetzt nach n umstellen

so haben wir es jedenfalls gemacht

Comments

mit "Tabelle" meinte ich die Tabelle aus den Folien mit dem zugehörigen Beispiel

---

Warum hast du Geschwindigkeit 1, wegen 1 sek oder hat das einen anderen Grund ??

Also muss ich alles in Sekunden umwandeln

---

ich hab es nach der "Formel" aus der Vorlesung gemacht und wenn du guckst, siehst du, dass im Nenner steht "Operationen / Sekunde ", mit anderen Worten: Geschwindigkeit pro sekunde. hab es dann einfach auch so umgerechnet. war ja nicht sehr aufwendig.

Geschwindigkeit ist nicht 1!!! da steht:

Geschwindigkeit : 1 operation, also ein rechenschritt, dauert 10^-9 Sekunden.

---

Ich bekomm aber so hohe Werte raus zB bei n^3 1sek n= 1000Kann das überhaupt sein

---

wenn du bei n^3 = 1000 hast, was hattest du denn bei log₂n raus ?

große werte hatten wir auch raus. das Ergebnis  ist ja die große, die n maximal annehmen kann, um mit der angegeben Geschwindigkeit zu rechnen. würde n zb um nur eine stelle größer werden, würde das Programm nicht mehr 10^-9 sek pro rechenschritt brauchen sondern länger

---

Bei log kam 2^{10⁹} raus, ich bekomm die ganze Zeit komische Werte raus

Habt ihr die anderen Werte in der Wurzel stehen gelassen ??

Muss ich denn das n irgendwo einsetzten nein oder ??

---

ja das hatten wir auch raus. haben uns aber sehr lange gewundert über die ganzen werte.

wir haben alles so stehen gelassen unter der wurzel. waren uns einfach zu große werte und zu viele 0-en um das noch weiterzurechnen.

du sollst doch das n berechnen. wo willst du das denn danach noch einsetzen ?

---

Müssen bei den Ergebnissen - stehen?

Habe jetzt bei den ersten Werten der Tabelle die Werte ausgerechnet und Frage mich ob es dann 2^10^-9 oder 2^10^9 sein müsste.

---

hast du in deiner Rechnung eine "10^-9" benutzt ?

wenn ja, dann sollte die irgendwo auftauchen, falls du sie nicht weggekürzt hast.

wenn nicht, dann nicht.