rekursive Aufwandsfunktion bestimmen, Anzahl in O-Notation

Question

Hallo, ich verzweifle jetzt seit etwa einer Stunde an einer Aufgabe und würde mich freuen, wenn jemand mir dabei helfen kann. Wichtig ist, dass iich es gerne auch verstehen möchte, am liebsten die einzelnen Schritte, sodass ich es bei anderen Aufgaben selber hinbekomme.

Bestimme die rekursive Aufwandsfunktion für die Anzahl der erforderlichen Vergleiche und dann deren Anzahl in O-Notation.

static int indexVonRek(int[] a, int wert,
                                            int von, int bis) {

     int mitte;
     if (von <= bis) {
              mitte = (von + bis)/2;
              if (wert < a[mitte]){
                  return indexVonRek(a, wert, von, mitte-1);
              }

              else if (wert > a[mitte]) {
                      return indexVonRek(a, wert, mitte+1, bis);
              }
              else { return mitte; }
    }
    return -1;

}

Ich verstehe, was die einzelnen O Notationen bedeuten, aber ich verstehe nicht, wofür a,n oder t genau stehen. Wäre toll, wenn ihr das dabei schreiben könnt. Also am besten für gaaaaanz dumme :)

Answer 1

Hallo ia1322, gesucht ist die Anzahl der Aufrufe der Funktion indexVon in Abhängigkeit von der Länge der Liste a.

Beispiel:
i = 8 9 10 11 12
a[i] = 2 3 5 9 17

Die Funktion wird mit einem Wert Wert aufgerufen, z. B. Wert = 3.  Gesucht wird die Position von Wert in der Liste a.  Hier also i = 9.  Dazu wird das Intervall, hier 8 bis 12, fortlaufend halbiert.

Wenn a z. B. die Länge 8 hat, dann muss man 3 * halbieren, bis die Länge 1 ist.  Sei f die Zahl der Aufrufe von indexVon, dann ist f(n) = log₂ n = ln n / ln 2 = O(ln n).