Laufzeitverhalten
-
Sorry, ihr habt recht, zur Quersummenermittlung müsste man auch meiner Logik nach div und mod vertauschen. Ist eine alte Informatikprüfung. Fehler in einer Prüfung??? Naja, macht die Fragestellung trotzdem nicht einfacher.
-
Ist doch logisch, daß das Laufzeitverhalten dann O(log10(n)) beträgt (zumindestens bei der normalen Quersummenberechnung).
Und bei diesem Algorithmus gibt es kein Worst-Case, Average-Case oder Best-Case, da der Algorithmus eineindeutig für jedes n ist.
Diese Unterscheidung ist z.B. bei Algorithmen für Feldern der Länge N nötig, da die einzelnen Werte nicht definiert sind und somit z.B. eine Sortierung unterschiedliche Zeit benötigen kann.
-
Ja, aber was gibt es dann zu entwickeln, zu schätzen und zu beweisen. Wo ist der Unterschied zwischen den drei Teilaufgaben?
-
Johannes_meyer schrieb:
Ja, aber was gibt es dann zu entwickeln, zu schätzen und zu beweisen. Wo ist der Unterschied zwischen den drei Teilaufgaben?
-> exakt entwickeln:
du gibst das EXAKTE Laufzeitverhalten an, ohne O-Notation:
du hast 1 Operation zur Initialisierung
du hast pro Schleifendurchlauf 1 Vergleichsoperation, 1 Addition, 1 Div, 1 Mod und 2 Zuweisungen.Egal wie n ausschaut, es wird in jedem Schleifendurchlauf um 1 Zehnerpotenz kleiner => du hast log10(n) + 1 Schleifendurchlaeufe.
Du hast 1 Return-Anweisung.
Um die Sache zu vereinfachen, sagen wir, dass alle Maschinenoperationen gleich lang brauchen. Dann hast du genau
Anzahl Operationen = Initialisierung + Schleifendurchlaeufe * Anzahl_Schleifenoerationen + Return = 1 + (log10(n) + 1)* 6 + 1 = 2 + 6(log10(n) +1)Operationen.
-> schaetzen:
Na ja, die Schaetzung laut O-Notation von obigem Ergebnis ist offensichtlich O(log10(n)).-> beweisen (nur Beweisskizze):
Der Laufzeitterm wird durch die Schleife dominiert.
Schleifeninvariante: n > 0, in der Schleife: n := n / 10. ==> die Schleife terminiert offensichtlich nach ~ log10(n) Schritten. QED
-
Meiner Meinung nach ist es nicht gut für alle Operationen nur eine Zeiteinheit zu veranschlagen. Aber dann wird die Aufgabe ungleich schwieriger und war wohl deswegen so gestellt.
Wenn man damit argumentiert, dass das für tatsächliche Rechner konstante Operationen sind, dann muss man aber auch sagen, dass n für diese Rechner nach oben beschränkt ist und somit ist das ganze in O(1).
-
Ponto schrieb:
Meiner Meinung nach ist es nicht gut für alle Operationen nur eine Zeiteinheit zu veranschlagen.
Begründung?
-
Weil man für eine Zahl mit n Bits log(n) Bit-Operationen braucht um sie zu addieren. Das bleibt O-kalkülmäßig natürlich auch, wenn man größere Register (mit konstanter Größe) hat. Stichwort: Real RAM Model vs. Bit cost model.
Btw. würde ich das die 10 beim log im O-Kalkül weglassen.
-
Bashar schrieb:
Ponto schrieb:
Meiner Meinung nach ist es nicht gut für alle Operationen nur eine Zeiteinheit zu veranschlagen.
Begründung?
Weil eine Addition nun mal worst-case linear in der Eingabe ist. Es hat doch wenig Sinn sich auf Zahlen bis 2^64 oder ähnlich zu beschränken, wenn man einen Algorithmus analysiert.
-
Du meinst, man muss entweder beliebig große Zahlen zulassen oder andernfalls die Laufzeit generell mit O(1) ansetzen? Nette Theorie, sie erspart es einem, sich mit der Wirklichkeit auseinanderzusetzen, die irgendwo in der Mitte liegt.
-
Du hast natürlich recht. Mir wird nur sowas immer unter den Tisch gekehrt. In allen Informatikvorlesungen, die ich gehört habe, wurde sowas gar nicht erwähnt. Das ist als ob man in Analysis die Definition der verschiedenen Zahlenräume weglassen würde.
Die Wirklichkeit kommt aber rein, wenn man versucht sowas in möglichst schnelle Hardware zu giessen. Denn da ist das Carrybit doch ein entscheidender Faktor.
-
Ich sag einfach mal danke für die vielen Kommentare übers Wochenende, besonders an Blue-Tiger.
Mfg
Johannes
-
Wo wir gerade bei Quersumme sind hätte ich nochmal ne Frage:
Diesmal Rekursiv:
Quersumme(n)=n für n<10 und n mod 10 + Quersumme(n div 10) für n>=10Eine Teilaufgabe:
Diskutieren Sie die Sicherheit des Rekursionsabbruchs.Ich entdecke da keine Ausnahmen, für die es ein Problem mit den Rekursionsabbruch geben könnte, oder übersehe ich da etwas?
Mfg
Johannes
-
Ponto schrieb:
Du hast natürlich recht. Mir wird nur sowas immer unter den Tisch gekehrt. In allen Informatikvorlesungen, die ich gehört habe, wurde sowas gar nicht erwähnt. Das ist als ob man in Analysis die Definition der verschiedenen Zahlenräume weglassen würde.
Wie gesagt gibt es verschiedene Modelle mit denen man arbeiten kann. Je nach Anwendungs sind unterschiedliche Maße relevant. Wenn ich Computer-Geometrie mache, dann arbeite ich eher im Real RAM Modell, wo ich Operationen wie +,-,*,/ in konstanter Zeit durchführen kann und sogar relle Zahlen exakt speichere. Wenn ich meinen Algorithmus mit Fließkommazahlen implementiere ist das auch eine recht vernünftige Näherung.
Geht's dagegen um echte Komplexitätstheorie oder eben etwas in Hardware gießen wird auf einmal die Bit-Komplexität das Maß der Dinge.
Ich denke, dass letztere nur selten behandelt wird hat zwei Gründe: Zum einen fällt ein großer Anteil der Praxis auf den ersten Fall (etwa arbeiten mit Fließkommazahlen) und zweitens ist die Bitkomplexität oft deutlich schwieriger zu handhaben.
Mach doch mal ne schöne Analyse für den zweiten Fall, das ist schon garnicht mehr so einfach. Da tauchen ein Haufen Kodierungsfragen auf, die anders eben nicht vorkommen.
Etwa wie lange braucht es n div 10 auszurechnen? In Binärdarstellung braucht man dafür wohl etwa O(log n) Zeit (die Zahl hat ja log n bits). Haben wir dagegen die Zahl im Zehnersystem gespeichert kann ich das in konstanter Zeit erledigen: einfach die letzte Stelle abschneiden. Wieviele Bits muß denn nun die Variable haben, die die Quersumme aufnimmt? offensichtlich ist 10*log_10 n eine obere Schranke für die Quersumme. Um einen Wert diese Größe speichern zu können muß die Variable O(log log n ) Bits haben, das heißt die Addition müßte auch diesen Zeitaufwand benötigten. Oder doch nicht? Schließlich addieren wir immer nur kleine Werte, so dass im Schnitt vielleicht nur konstant viele Bits angefasst werden müssen? Ich denke, dass man da bequem für O(log ^2 n) über O(log n * log log n), evtl sogar bis O(log n) argumentieren könnte, je nach Kodierung und exakter Implementierung.
