0 Daumen
318 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.

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