Beiträge von Roflkopf

Top, jetzt hab ich's verstanden!
Danke euch beiden für eure Antworten, hat mir sehr weitergeholfen!
Jetzt muss ich in der Klausur nur noch selbst drauf kommen

Danke nochmal und Mfg
Roflkopf

Ok, also das mit den n Schleifendurchläufen war ja genau mein Gedanke. Dass das Einfügen auch noch Laufzeit kostet, habe ich wohl irgendwie verdrängt.
Trotzdem bleibt es mir unklar, warum das Einfügen log(n) ist...

Hi zusammen,

bin gerade dabei für Programmiertechnik zu lernen und bin jetzt bei der Komplexitätsanalyse angelangt. Habe allerdings große Probleme damit, die Laufzeit von Funktionen richtig abzuschätzen.
Folgendes Beispiel:

Set<Integer> fun(List<Integer> 1) {
     Set<Integer> s = new TreeSet<Integer>();
     for (int x : 1)
          s.add(x);
     return s;
}

Die Funktion schreibt alle Elemente der Liste 1 in die neue Menge s und gibt diese zurück.
Nun soll die Laufzeit T(n) (worst case) abgeschätzt werden. n ist dabei die Größe der Liste 1.
Ich hätte jetzt die Laufzeit T(n) = O(n) abgeschätzt, aber laut Lösungen ist die Laufzeit T(n) = O(n*log(n)).
Kann mir jemand erklären, wie man auf diese Laufzeit kommt?

MfG
Roflkopf

Super, danke Lacuno, hat mir sehr geholfen. Ich habs jetzt endlich geschafft :thumb:

public int getSmallestElement(int[] array, int start, int ende){  
       if (start==ende)
           return array[start];

       int mittel = (start+ende)/2;
       return Math.min(getSmallestElement(array, start, mittel), getSmallestElement(array, mittel+1, ende)); 

   }

Danke nochmal an alle und LG

spinball
Ich hab nochmal nachgefragt und du hast Recht, start bzw. ende sollen verändert werden.
Habe jetzt nochmal neu angefangen und bin auf Folgendes gekommen:

public int getSmallestElement(int[] array, int start, int ende){         
if (start==ende)
       return array[start];

return Math.min(getSmallestElement(array, start, ende/2), getSmallestElement(array, (ende/2), ende)); 

   }

Da bekomme ich allerdings jetzt einen StackOverflowError, was start==ende betrifft
Irgendwelche weiteren Tipps? :p

Hallo zusammen,

ich habe eine Aufgabe bekommen, bei der ich eine Methode schreiben muss, die aus einem übergebenen int-Array das kleinste Element zurückgibt. Diese Methode soll ganz ohne Schleifen auskommen und rekursiv arbeiten. Als Hinweis ist gegeben, dass wir den übergebenen Array in 2 (möglichst) gleichgroße Teile aufteilen sollen. Das habe ich noch hinbekommen, allerdings weiß ich jetzt nicht wirklich wie es weitergehen soll.

Bis jetzt habe ich folgendes:

public int getSmallestElement(int[] array, int start, int ende){

       int smallest = 0;
       int[] hilf1;
       int[] hilf2;
       int length1 = array.length / 2;
       int length2 = (array.length / 2) + 1;

       if(array.length % 2 == 0)
       {
           hilf1 = new int[array.length / 2];
           System.arraycopy(array, start, hilf1, 0, array.length/2);
           hilf2 = new int[array.length / 2];
           System.arraycopy(array, array.length/2, hilf2, 0, array.length/2);
       }
       else
       {
           hilf1 = new int[length1];
           System.arraycopy(array, start, hilf1, 0, length1);
           hilf2 = new int[length2];
           System.arraycopy(array, length2-1, hilf2, 0, length2);
       }

       return smallest; //damit ist noch nichts passiert, ich weiß :P
   }

Der Array soll beliebig lang sein und, dass start bzw ende übergeben werden, war vorgegeben.

Ich bitte um Tipps, nicht um die Lösung.

Ach und wir benutzen BlueJ.

LG