Geben Sie einen Algorithmus mit der Laufzeit O(n) an, der bestimmt, ob es zwei Indizes 0 ≤ i < j < n gibt

Question

Ich habe mich in den letzten Tagen etwas mit Java beschäftigt und bin mittlerweile an dem Punkt angekommen, an dem ich mich mit Laufzeiten beschäftige. Auf einer Website habe ich dann leider eine Aufgabe gefunden, zu der ich keine Lösung weiß. Könnte mir evtl. jemand weiterhelfen oder mir zumindest einen kleinen Tipp geben?

Aufgabe:

Es existiert ein Feld \(A\), welches aufsteigend sortiert ist. \(A\) enthält zudem reelle Zahlen \(n > 0\). Des Weiteren sei eine reelle Zahl \(x\) gegeben.

Geben Sie einen Algorithmus mit der Laufzeit \(\mathcal{O}(n)\) an, der bestimmt, ob es zwei Indizes \(0 \leq i < j < n\) gibt, sodass \(x = A\{i\} + A\{j\}\) gilt.

Comments

\(A\) enthält zudem reelle Zahlen \(n > 0\).

Meinst du, dass \(A\) genau \(n\) reelle Zahlen hat? Weil du musst ja Indizes \(0 \leq i < j < n\) angeben können, falls eine Darstellung durch \(x = A\{i\} + A\{j\}\) möglich ist.

Answer 1

Wenn die Summe aus erstem und letzen Element zu groß ist, dann wird das letzte Element entfernt.

Wenn die Summe aus erstem und letzen Element zu klein ist, dann wird das erste Element entfernt.

Answer 2

Antwort mit KI erzeugt

Lösung:

Um diese Aufgabe zu lösen, stellen wir einen Algorithmus vor, der die gegebene Eigenschaft der Aufsteigenden Sortierung des Arrays \(A\) nutzt. Dies erlaubt es uns, ein Zwei-Zeiger-Verfahren (Two Pointer Technique) anzuwenden. Dieser Ansatz gewährleistet eine lineare Laufzeit \(\mathcal{O}(n)\), da jedes Element des Arrays höchstens einmal von jedem Zeiger besucht wird.

Algorithmus:

1. Initialisiere zwei Zeiger: einen am Anfang des Arrays \(left = 0\) und den anderen am Ende \(right = \(n-1\)\).

2. Führe eine Schleife aus, solange \(left < right\) ist:
a. Berechne die Summe \(s = A[left] + A[right]\).
b. Wenn \(s == x\), haben wir die gewünschten Indizes gefunden (\(i = left\), \(j = right\)). Beende die Schleife und gib \(true\), zurück, da ein passendes Paar gefunden wurde.
c. Wenn \(s < x\), erhöhe left um 1, um die Summe zu erhöhen \(left++\).
d. Wenn \(s > x\), verringere right um 1, um die Summe zu verkleinern \(right--\).

3. Wenn die Schleife endet, ohne dass ein paar gefunden wurde, das die Bedingung erfüllt, gibt den Wert \(false\) zurück.

Java Implementierung:

java
public class SumFinder {
    public static boolean findPairWithSum(int[] A, double x) {
        int left = 0; // Startpunkt
        int right = A.length - 1; // Endpunkt
        
        while (left < right) {
            double sum = A[left] + A[right];
            
            if (sum == x) {
                // Ein Paar wurde gefunden
                return true;
            } else if (sum < x) {
                // Erhöhe die Summe, indem `left` inkrementiert wird
                left++;
            } else {
                // Verringere die Summe, indem `right` dekrementiert wird
                right--;
            }
        }
        
        // Kein geeignetes Paar gefunden
        return false;
    }

    public static void main(String[] args) {
        int[] A = {1, 2, 4, 4}; // Beispiel Array
        double x = 8; // Beispiel Zielsumme
        
        System.out.println("Existiert ein Paar? " + findPairWithSum(A, x));
    }
}

Dieser Code durchläuft jedes Element im schlimmsten Fall einmal pro Zeiger, was zu einer Gesamtlaufzeit von \(\mathcal{O}(n)\) führt, wobei \(n\) die Länge des Arrays ist.