0 Daumen
496 Aufrufe

Frage:

Analyse von Algorithmen

Ternäre Suche

Wir übertragen die Idee der Binärsuche auf die Suche in einer von drei Teilen.

boolean ternarySearch(int[] a, int low, int high, int v) {
if (low > high) return false;
int mid1 = low + (high - low) / 3;
if (a[mid1] == v) return true;
if (v < a[mid1]) { return ternarySearch(a, low, mid1 - 1, v); }
int mid2 = low + 2 * (high - low) / 3;
if (a[mid2] == v) return true;
if (v < a[mid2]) { return ternarySearch(a, mid1 + 1, mid2 - 1, v);}
return ternarySearch(a, mid2 + 1, high, v);
}



Analysieren Sie die Komplexität (Anzahl an Vergleichen – worst-case!). Gehen Sie wie folgt vor:
• Erstellen Sie die Rekursionsgleichung (analog zur binären Suche)
• Versuchen Sie, eine Lösung zu „erraten“ – Denken Sie an Binärsuche


Code:

Die erste Frage habe ich beantwortet mit der Rekursionsgleichung T(n) = T (n/3) + 4

Ich weiß nicht genau was man bei der zweiten Frage tun soll? Mit der Rekursionsgleichung irgendwie eine Lösung erraten? Kann mir bitte jemand weiterhelfen?


Vielen Dank im Voraus.

Avatar von

Hallo :-)

Kennst du das Master Theorem?

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community