Mathematik online lernen im Mathe-Forum. Nachhilfe online
Startseite » Forum » O-Kalkül und Schleifeninvariante

O-Kalkül und Schleifeninvariante

Universität / Fachhochschule

Finanzmathematik

Sonstiges

Tags: Sonstig

 
Antworten Neue Frage stellen Im Forum suchen
Neue Frage
SideKick555

SideKick555

22:24 Uhr, 27.04.2020

Antworten
Ich habe folgenden Algorithmus:

Data:p,q∈N>0
Result:(d,f)∈N0xN0

d←0
f←q
g←1
while q-g⋅p≥0do
w--- d←g
w--- g←g+1
w--- f←q-d⋅p
return(d,f)

Dabei gehören die drei Zeilen nach dem while Befehl zur Schleife (mit w--- markiert).

1. Berechne das O-Kalkül für den Worst-Case für die Laufzeit in Abhängigkeit von q.
2. Nenne und beweise eine Schleifeninvariante für die while-Schleife. Diese soll q in Abhängigkeit von p beschreiben. q≥p.
Bitte helft mir schnellstmöglich, ich habe leider absolut keine Ahnung was ich tun soll.
Ich habe angefangen mich in die Themen einzulesen, jedoch hat es nichts gebracht.
Vielen Dank.
Liebe Grüße Ari.

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich bräuchte bitte einen kompletten Lösungsweg." (setzt voraus, dass der Fragesteller alle seine Lösungsversuche zur Frage hinzufügt und sich aktiv an der Problemlösung beteiligt.)
Online-Nachhilfe in Mathematik
Antwort
gaubes

gaubes aktiv_icon

21:00 Uhr, 29.04.2020

Antworten
Du weißt was das O-Kalkül ist? Du berechnest damit quasi die Anzahl der nötigen Rechenschritte.
Worst-case heißt hierbei, du musst von den maximal notwendigen Schritten ausgehen und diese Zählen.

Ein kurzes Beispiel dazu mit offensichtlicheren Zahlen:

summe = 0
i=0
while i < q do
summe = 1+summe
i= i+1
end while


hierbei hast du einen Schritt für die Zuweiseungen vor der While-Schleife, also O(1)+O(1)=O(1)
und die While-schleife durchläufst du im worst-case q-mal, was dich zu O(q) führt. Das innere der While-Schleife musst du jedesmal durchlaufen was dann zu
O(q)⋅(O(1)+O(1))=O(q) führt.

Ich hoffe das Beispiel veranschaulicht das vorgehen etwas.
Was ist dir noch unklar?
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.