Rekursiver Algo Vollständige Induktion

Question

Ich habe Unten einen Algorithmus, der prüft ob der Integer h im Array enthalten ist und ansonsten -1 ausgibt(Klausuraufgabe).

Nun soll ich die Laufzeit des Algorithmus bestimmen und bin mir dort relativ unsicher, da man es mit Vollständiger Induktion beweisen soll. Es ist gegeben, dass die Laufzeit in der Komplexitätsklasse O(n) liegt.

Da der Algorithmus rekursiv ist müsste aufgrund der 2 Aufrufe und Teilung des Problems durch 2 für das Master Theorem folgendes gelten:

T(n)=2T(n/2), wobei ich mir für c bzw. f/n relativ unsicher bin.

Wie kann ich dieses Erkenntnis nun für die Vollständige Induktion umformen?

Code:

public class Mysteryclass {
    public static int MYSTERY(int h, int[] array, int start, int end) {
        if (start == end) {
            if (array[start] == h) {
                return start;
            } else {
                return -1;
            }
        }
        else {
            int x = (start + end + 1) / 2;
            int i = MYSTERY(h, array, start, x - 1);
            int j = MYSTERY(h, array, x, end);

            if (i != -1) {
                return i;
            }
            else {
                return j;
            }
        }
    }
}

Answer 1

Antwort mit KI erzeugt

Laufzeitbestimmung durch vollständige Induktion für einen rekursiven Algorithmus

Um die Laufzeit des rekursiven Algorithmus zu bestimmen, ist der Master Theorem eine effektive Methode. Zuerst analysieren wir den rekursiven Aufruf im Code.

Der Algorithmus MYSTERY sucht einen Integer \(h\) in einem Array. Der Algorithmus teilt das Problem in zwei Hälften, indem er das Array in der Mitte aufteilt und rekursiv nach \(h\) in beiden Hälften sucht:

java
public class Mysteryclass {
    public static int MYSTERY(int h, int[] array, int start, int end) {
        if (start == end) {
            if (array[start] == h) {
                return start;
            } else {
                return -1;
            }
        } else {
            int x = (start + end + 1) / 2;
            int i = MYSTERY(h, array, start, x - 1);
            int j = MYSTERY(h, array, x, end);

            if (i != -1) {
                return i;
            } else {
                return j;
            }
        }
    }
}

Rekursionsgleichung

Der Algorithmus teilt das Array in zwei Hälften und ruft sich selbst rekursiv auf jeder Hälfte auf. Die Rekursionsgleichung für die Laufzeit \(T(n)\) des Algorithmus ist:

\( T(n) = 2T\left(\frac{n}{2}\right) + O(1) \)

Hier ist \(T(n)\) die Laufzeit des Algorithmus für ein Array der Länge \(n\). Da jede Teilung \(O(1)\) Arbeit (konstant) erfordert, ergibt sich die Gleichung zu:

Anwendung des Master Theorems

Das Master Theorem für Rekursionsgleichungen der Form \(T(n) = aT\left(\frac{n}{b}\right) + f(n)\) ist nützlich für die Analyse asymptotischen Laufzeiten. Hier sind \(a = 2\), \(b = 2\) und \(f(n) = O(1)\).

Beim Master Theorem vergleichen wir \(f(n)\) mit \(n^{\log_b a}\):

\( n^{\log_b a} = n^{\log_2 2} = n^1 = n \)

Vergleich zwischen \(f(n) = O(1)\) und \(n\):

Da \(f(n) = O(1)\) kleiner als \(n\) ist (genauer: \(f(n) = O(n^c)\) für \(c = 0 < 1\)), verwenden wir den dritten Fall des Master Theorems:

- Wenn \(f(n) = O(n^c)\) für ein \(c < \log_b a\), dann \(T(n) = O(n^{\log_b a})\).

Daraus folgt \(T(n) = O(n)\).

Vollständiger Induktionsbeweis

Um zu zeigen, dass die Laufzeit \(T(n)\) tatsächlich \(O(n)\) ist, verwenden wir vollständige Induktion über \(n\).

1. Induktionsanfang: Prüfen für den Basisfall \(n = 1\):

\( T(1) = O(1) \)

2. Induktionsannahme: Angenommen, \(T(k) \leq ck\) für ein \(k \geq 1\) und eine Konstante \(c\).

3. Induktionsschritt: Beweis für \(n = k + 1\):

\( T(k+1) = 2T\left(\frac{k+1}{2}\right) + O(1) \)

Da \(T\) monoton ist, für zwei fast gleich große Teile:

\( T(k) \leq ck \)

Für \(n = \lceil \frac{k+1}{2} \rceil \) und \(n = \lfloor \frac{k+1}{2} \rfloor \):

\( T(k+1) \leq 2c \frac{k+1}{2} + O(1) = c(k+1) + O(1) \)

Somit wird:

\( T(k+1) \leq c(k+1) \)

Durch Induktion folgt, dass der Algorithmus \(O(n)\) Zeit benötigt.

Fazit
Die Laufzeit des rekursiven Suchalgorithmus \(MYSTERY\) ist in der Ordnung von \(O(n)\), was durch das Master Theorem und vollständige Induktion bestätigt wurde.