"Optimierung" des Codes

[yeha]

hallo erneut
ich bearbeite grade Teile & Herrsche Algorithmen und bin grade bei der Aufgabe, den Index des größten Elements eines pyramidal sortierten Arrays zu bestimmen( bedeutet, die Elemente in dem Array werden streng aufsteigend bis zu einem Index k angeordnet, danach ist das Array streng abfallend ..:z.B. (10,12,15,9,8,0) )
mein Code funktioniert zwar, aber ich würde das Problem gerne in nur einer Methode lösen, bzw die Laufzeit verbessern

Hier mein Code:

public static int pyramide(int []array, int l, int r)
    {
        int q=(l+r)/2;
        if(array.length==0)
        {
            return 0;
        }
        if(array.length==1)
        {
            return array[0];
        }
        if(l==r)
        {
            return array[l];
        }
        else
        {
            if(array[l]<pyramide(array,q+1,r))
            {
                return pyramide(array,q+1,r) ;
          
            }
            else
            {
                return pyramide(array,l,q);
            }
          
        }
    }
  
public static int indexrek(int []arr,int l,int r)
    {
        if(arr.length==0)
        {
            return 0;
        }
        if(arr.length==1)
        {
            return 0;
        }
        if(arr[l]==pyramide(arr,l,r))
        {
            return l;
        }
        else
        {
            return indexrek(arr,l+1,r);
        }  
    }

 

[krgewb]

mein Code funktioniert zwar, aber ich würde das Problem gerne in nur einer Methode lösen, bzw die Laufzeit verbessern

Rekursion führt zu exponentiellem Laufzeitverhalten.
Du rufst die Methode innerhalb der Methode auf. Das nennt man Rekursion.

 

[JCODA]

Also ich habe nicht wirklich alles nachvollzogen, das einzige, was mir sofort aufgefallen ist, ist folgendes:

if(array[l]<pyramide(array,q+1,r)){
   return pyramide(array,q+1,r) ;
 }

Hier rufst du einmal für den Vergleich die Rekursion auf und dann ERNEUT für die Rückgabe, falls der Vergleich true liefert.
Hier würde es sich anbieten nur einmal die Methode aufzurufen, sich in einer Variable den Rückgabewert merken, und dann diesen zurückgeben.

Rekursion führt zu exponentiellem Laufzeitverhalten.

Naja, nicht immer, kommt drauf an, in wie viele Portionen und wie große Portionen man die Arbeit verteilt. Siehe etwa: https://de.wikipedia.org/wiki/Master-Theorem

 

[Meniskusschaden]

mein Code funktioniert zwar, aber ich würde das Problem gerne in nur einer Methode lösen

Du könntest in der indexrek-Methode zuerst prüfen, ob du das Element bereits gefunden hast und den Index dann zurück liefern. Andernfalls vergleichst du das mittlere Element des Teil-Arrays mit seinem ersten Element und lieferst dann abhängig davon entweder das indexrek-Ergebnis der linken bzw. rechten Hälfte des Teil-Arrays zurück.

 

[Flown]

Ich darf darauf verweisen, dass dieser Thread am 6. September eröffnet wurde und schon 2 Wochen alt ist.

Aber wenn man schon dabei ist würde ich das alles für den Index programmieren und damit arbeiten. Man sollte auch die Monotonie Eigenschaft verwenden:

public static int maxIndexPyramid(int[] arr) {
  if (arr == null || arr.length == 0) {
    return -1;
  }
  return maxPyramidIndex(arr, 0, arr.length);
}

public static int maxPyramid(int[] arr) {
  int maxIndex = maxIndexPyramid(arr);
  if (maxIndex < 0) {
    throw new NoSuchElementException();
  }
  return arr[maxIndex];
}

private static int maxPyramidIndex(int[] arr, int l, int r) {
  int mid = (l + r) / 2;
  int midValue = arr[mid];
  // Wenn es ein linkes Element gibt und es ist gößer? Dann links weitersuchen
  if (mid > 0 && arr[mid - 1] > midValue) {
    return maxPyramidIndex(arr, l, mid);
  // Wenn es ein rechtes Element gibt und es ist gößer? Dann rechts weitersuchen
  } else if (mid < arr.length - 1 && midValue < arr[mid + 1]) {
    return maxPyramidIndex(arr, mid, r);
  // Gibt links und rechts kein größeres Element, darum mid ist das Maximum
  } else {
    return mid;
  }
}

 

[yeha]

Danke erstmal für die Antworten,aber wie bestimme ich denn überhaupt die Laufzeit des Codes?

 

[JStein52]

Willst du die Laufzeit deines Codes messen ? Dann gescheite Inputdaten herstellen, Zeitstempel nehmen, deine Methode 1 Mio. mal aufrufen, Zeitstempel nehmen und Differenz bilden.

 

[yeha]

nicht so richtig... wenn z.B. vorgegeben ist, dass der Code höchstens eine Laufzeit von O(n) haben soll... woher weiß ich das, bzw wie bestimme ich die Laufzeit?

 

[JStein52]

Rekursion führt zu exponentiellem Laufzeitverhalten.

Nein, oder hast du da eine Begründung dafür ? Rekursion ist auch nichts anderes als eine Ieration, mache etwas solange bis ein Abbruchkriterium erreicht ist. Rekursion kann zu einem StackOverflow führen aber das ist ein anderes Thema.

dass der Code höchstens eine Laufzeit von O(n) haben soll

Du willst also die Komplexität deines Algorithmus bestimmen ? Dann musst du dir überlegen wie ändert sich die Laufzeit meines Algo's in Abhängigkeit von n (hier der Länge deines Arrays). Wenn du das Array einmal in einer Schleife durchläufst ist die Komplexität O(n) ... wenn du z.B. das Array in einer Schleife durchläufst und dir für jedes Element noch einmal alle anderen Elemente anschaust (d.h. zwei ineinander geschachtelte Durchläufe hättest du O(n^2) ....

 

[yeha]

und wie gehe ich bei einem rekursiven Algorithmus vor? Vielleicht kannst du dir auch noch mein anderes Thema anschauen ? https://www.java-forum.org/thema/rekursionsgleichung-bestimmen.178801/

 

[JStein52]

Da gehst du ganz genau so vor. Ich habe meine Beschreibung ja bewusst allgemein formuliert. Ob du in einer Schleife dein Array schrittweise abarbeitest oder rekursiv ist egal. Siehe den oberen Teil im vorigen Post.

 

[yeha]

der Fibonacci-Algorithmus hat wohl eine Laufzeit von O(1,6..^n) http://www.inf.fu-berlin.de/lehre/SS12/ALP2/slides/V6_Rekursion_vs_Iteration_ALP2.pdf
(folie 31)
Das hätte ich so aber niemals bestimmen können, mittels deiner Erklärung wäre ich auf eine Laufzeit von O(n) gekommen, da bis n<=2 durchgelaufen wird

 

[JStein52]

mittels deiner Erklärung wäre ich auf eine Laufzeit von O(n) gekommen, da bis n<=2 durchgelaufen wird

Kommt auf den Algo an. Der erste hat ja in der einen Zeile "return fib(n-2) + fib(n-1)" Das ist natürlich nicht nur einfach eine "Schleife" aber weiter unten war ja eine endrekursive Version die dann wieder O(n) hat.
Also musst dir schon immer den Algorithmus genau angucken und abzählen

 

[yeha]

wie kam denn die Laufzeit O(1,6^n) zustande?

Also musst dir schon immer den Algorithmus genau angucken und abzählen

Ich habe mir den Algorithmus schon bestimmt gut 2 Stunden angeguckt und verstehe immer noch nicht, wie ich denn genau abzählen muss

 

[JStein52]

Ganz ehrlich: wie sie auf die Formel mit (1+sqrt(5))/2 kommt weiss ich auch nicht. Ich meinte auch mehr dass es die geforderten O(n) nicht sind lässt sich erkennen (durch abzählen der durchgeführten Schritte in der Tabelle weiter unten)