Aufwandsabschätzung-Aufgabe

[drpingoo]

Hallo zusammen, ich hab da so eine Aufgabe, bei der man deren Aufwand abschätzen muss. Das Ergebnis kenne ich bereits, es wäre nämlich a+3/2*b, aber ich weiss nicht ,wie ich darauf kommen soll. Hier wäre die Augabe dazu:

static boolean gerade( int x ) {
if( x == 0 ) return true;
return !gerade( x - 1 );
}
static int verdopple( int x ) {
if( x == 0 ) return 0;
return 2 + verdopple( x-1 );
}
static int halbiere( int x ) {
if( x == 0 ) return 0;
if( x == 1 ) return 0;
return halbiere( x - 2 ) + 1;
}
static int f(int a, int b) {
if (b == 0) return 0;
if (gerade(b)) return f(verdopple(a),halbiere(b));
else return a + f(verdopple(a), halbiere(b));
}

für mich würde es eben so aussehen:

1) b==0 ,b
2) geradeb, b
3) x==0 , b
4) x-1 , b
5) !gerade(), b
6) a + ,a
7) verdopple(a), a
8) x==0, a
9) 2+ ,a
10) verdopple(), a
11) x-1, a
12) x==0, b
13) x==1, b
14) (x-2), b
15) +1, b
16) halbiere(), b

Das wären dann 10b's und 6a's

Würde aslso a+5/3*b ergeben, was abner nicht stimmt.

Kann mir da jemand weiterhelfen?

Lg
drpingoo

 

[procurve]

!gerade, b

Das ist meiner Meinung nach keine extra Anweisung, daher 9 B, 6 A = 9/6 = 3/2

 

[drpingoo]

Also Rekursionsaufrufe sollen hier sowieso vernachlässigt werden, aber die Funktionen verdopple() und halbiere() ruf ich ja auch nochmals auf, d.h. ich müsste !gerade() ebenso nochmals aufrufen, sonst ergibt es nicht so einen Sinn... Wobei ich es eh komisch finde, dass die Funktion gerade() aufgerufen wird, denn so wird es gerade gerade gemacht.

lg