Berechnen der Komplexität rekusiver Funktionen?

[Hilefoks]

Moin,

ich habe Probleme mit Teilen einer Aufgabe. Mein Problem liegt beim Berechnen der O-Notation folgendes Java-Programms:

static int bla(int[] a, int wert, int von, int bis) {
  int mitte;
  while(von<=bis) {
    mitte=(von+bis)/2;
    if(wert<a[mitte]) { return bla(a, wert, von, mitte+1); }
    else if(wert>a[mitte]) { return bla(a, wert, mitte+1, bis); }
    else { return mitte; }
  } 
}

Mein Problem ist, das ich nicht wirklich weiß wie ich den Sourcecode in eine Funktion bekomme, um dann die O-Notation zu errechnen.

Eine weitere Teilaufgabe die ich nicht Lösen kann ist:
Zeigen Sie das diese Aussage wahr ist oder widerlegen Sie sie: log n hat mindestens eine Komplexität von n.
Hier finde ich keinen Ansatz das mathematisch zu erläutern.

Ich weiß das Hausaufgaben unerwünscht sind. Allerdings suche ich nicht wirklich nach einer Lösung, sondern vielmehr nach einem Weg.

Vielen Dank,
MfG Hilefoks

 

[MPW]

Gibt es ein Pendon zu KSKG im Sinne von, zeig mal deinen jetzigen Loesungsansatz?

 

[Hilefoks]

Hallo,

mh - ich habe leider keine Ahnung was KSKG bedeutet. Was ich nur besitzte ist die Formel für rekusive Funktionen.

Seien a>=1, b>1, f:N->N und die Aufwandsfunktion t(n) sei von der Form:

t(n)=at(n/b) + f(n)

Leider hat mein Prof. aber rekusive Berechnungen nie an Hand eines gegebenen Codes erklärt, sondern immer nur an Hand von Formeln. Na ja - im Grunde hat er es gar nicht erklärt. ;-)

Meine Lösung für normale, nicht rekusive Funktionen sieht dabei recht simpel aus - ich zähle praktisch "nur" die Zuweisungen, Operationen und Schleifen. Z.b. so:

static int iVonIt(int[] a, int wert) {
  int von=0;
  int bis=a.length-1;
  int mitte;

  while(von<=bis) {
     mitte=(von+bis)/2;
     if(wert<a[mitte]) { bis=mitte-1; }
     else if(wert>a[mitte]) { von=mitte+1; }
     else { return mitte; }
  }
  return -1;
}

Meine Lösung dazu:
3 Zuweisungen + n Schleifendurchläufe * ( max 2 Zuweisungen + 2 Vergleiche) + einer Return-Anweisung = 3+4n+1=4+4n

Da 4+4n<=c*n gefunden werden kann ist das Ergebnis O(n).

100% - ich habe etwas sehr sehr Grundlegendes nicht verstanden - und zwar wie ich aus (rekusiven) Code eine mathematische Funktion baue. In dem Script zur Vorlesung, in Scripten anderer Fachhochschulen, in der Wikipedia und auch sonst im Internet habe ich nichts gefunden was darauf eingeht. Nur immer wieder die mir bereits bekannten mathematischen Formel. Aber ich muss den Code ja erst mal in die Form bringen um ihn berechnen zu können - und da liegt mein Problem.

Vielen Dank,
MfG Hilefoks

 

[Hilefoks]

Moin,

den einzigen Ansatz den ich finde ist der nach meiner "dummen" Methode: Die Schleife läuft max. n-mal, und durch den rekusiven Aufruf halbiert sich das Problem - so würde ich auf n+n/2+n/4... kommen. Ich denke - ich bin voll auf dem Holzweg!

MfG Hilefoks

 

[Beni]

Bei jedem Durchlauf wird die Anzahl noch verbleibender möglicher Resultate halbiert, hört sich für mich nach "log n" an.

 

[Leroy42]

Richtig @ beni. Es ist O(log n), genauer O(ld n) "ld = 2-er Logarithmus".

Die Funktion implementiert die typische Binärsuche in einem geordneten Array.

Um den Aufwand errechnen zu lassen braucht Hilefoks nur die elementaren
Schritte über alle Indizes von 1 bis n aufsummieren und durch n teilen.

 

[Hilefoks]

Danke für eure Antworten.

Mir ist allerdings klar das das Ergebnis O(ld(n)) ist, allerdings weiß ich immer noch nicht wie ich dahin komme, wobei ich nach meiner Methode dieses Ergebnis auch erhalte.

Im Script steht allerdings diese Formel: t(n)=a*t(a/b)+f(n) - und ich habe keine Ahnung was ich in diese Formel einsetzten soll.

Vielen Dank,
MfG Hilefoks

 

[Limit]

Den Aufwand rekursiver Funktionen zu berechnen ist nicht unbedingt trivial, außer die Funktionen sind recht simpel, dann gibt es simplere Verfahren.

Zuerst stellst du eine rekursive Aufwandfunktion für deine rekursive Funktion auf. Diese sog. Rekurenz kannst du dann auf unterschiedliche Arten lösen. Unter http://www.joachim-wilke.de/download.htm?dir=info2tut05&file=folien-12.pdf
sind sie am Beispiel von MergeSort vorgeführt.

Ich hoffe das hilft.