Aufwandsberechnung

Computer: Software & Programmierung Programmierung allgemein
#1

Gesucht ist der Aufwand für die folgenden beiden Algorithmen. (ein Aufwand im Sinne von z.B. O(1) oder O(x²)

int berechnung1(int n) {
if (n

#2

Moin, scochet,

in B1 steht eine Addition anstelle der Multiplikation in B2. Grundsätzlich lässt sich jede Multiplikation auf fortgesetztes Addieren zurückführen. Manche Compiler haben Optimizer, die den Sourcecode ändern; ob jeder Optimizer erkennt, dass eine Multiplikation mit 2 ein simpler Linksshift ist, weiß ich allerdings nicht.

Bevor ich mich weiter verlustiere, solltest Du mal ein Tönchen zu Deinem Wissensstand und den bisherigen Erkenntnissen sagen.

Gruß Ralf

#3

Hallo,

ich habe bisher gedacht, dass berechnung1 einen Aufwand von O(n²) und berechnung2 nur einen Aufwand von O(n) hat.
berechnung1 scheint jedoch einen viel höheren Aufwand zu haben. Ich weiß aber nicht warum. (ist ne ganze Weile her, dass ich diese Aufwandsberechnung im Studium hatte)

Gruß

#4

Da muss ich passen.
Hi scochet,

mit O(n) ist die Anzahl der Operationen abhängig von der Länge des Operanden gemeint? Mein Studium ist noch viel länger her, deshalb habe ich die Rekursivität erstmal nicht erkannt :frowning: Und ich gestehe, dass mir dieses Thema immer viel zu mühsam war - man schreibt 3 Zeilen höchst eleganten Code und weiß 5 Minuten später nicht mehr, was man sich dabei gedacht hat. Die Türme von Hanoi waren mein erster und letzter Versuch.

Während meiner 30 Jahre Berufstätigkeit ist mir übrigens die Rekursivität nie wieder begegnet. Nie wieder. NIE WIEDER.

Tut mir leid, dass ich Dir da nicht weiterhelfen kann.

Gruß Ralf

#5

Hallo scochet.

int berechnung1(int n) {
if (n

int berechnung2(int n) {
if (n

Für beide Funktionen gilt: Auf jeder Rekusionsebene verringert sich der Wert des Parameters um einen konstanten Betrag, auch das Abbruchkriterium ist konstant. Die Rekursionstiefe liegt damit in O(n).

Bei berechnung2() erfolgt auf jeder Rekursionsebene nur ein rekusiver Aufruf, d.h. der Aufwand ist auf jeder Rekursionsebene konstant. Daher liegt die Funktion in der Aufwandsklasse O(n).

Bei berechnung1() hingegen erfolgen auf der ersten Ebene zwei rekursive Aufrufe, aus denen auf der zweiten Ebene wieder jeweils zwei Aufrufe hervorgehen und so weiter. Wir haben also auf den Ebenen nacheinander 2, 4, 8, … Aufrufe, der Aufwand verdoppelt sich von Ebene zu Ebene. Also liegt die Funktion in der Aufwandsklasse O(2n).

Gruß,
Ralf

#6

Danke für die ausführliche Antwort! Konnte die Ergebnisse nachvollziehen.