Laufzeit von einfachem Programm

[DaSt]

Hallo,
wir sollen ein Algorithmus eintwickeln mit Laufzeit n^3, einen der schneller ist als n^3 und einen mit nlogn der folgende Aufgabe erfüllt.
Eingabe: int a[] = {a0; : : : ; an-1}; (Nur ganze positive Zahlen ohne 0)
Ausgabe: true, falls es zwei Elemente ai; aj gibt mit s = ai + aj ; i != j, false sonst

Ich verstehe es so, dass wenn es eine Zahl s im Array gibt die das Erg. der Addition zweier anderer Zahlen im Array ist, dann true sonst false

Mit Laufzeit n^3 habe ich folgendes implementiert

//Laufzeit n^3
    public static void LaufZeitNhochDrei(int arr[]){
       
        for(int i =0; i<arr.length; i++){
            for(int j=i+1; j<arr.length; j++){
                int erg =0;
                erg =arr[i]+arr[j];
                 //Jedes mögliche Additionsergebnis mit den Werten im Array vergleichen
                for(int y=0; y<arr.length;y++){
                    if(arr[y]==erg){
                        System.out.println("True: " +erg +" = " +arr[i]+" + "+arr[j]);
                    }
                }
            }   
        }
    }

Ist folgender Code schneller? Hat ja nur 2 verschachtelte For-Schleifen
Ist hier die Laufzeit n^2+n korrekt?(2 verschachtelte For-Schleifen + eine normale)
Aber ich weiss halt nicht wie list.add() bzw. list.contains() implementiert sind

//Laufzeit n^2+n
    public static void LaufZeitNhochzwei(int arr[]){
        //In diese Liste werden alle einzelnen Ergebnisse der Additionen gespeichert
        ArrayList<Integer> list = new ArrayList<Integer>();
       
        //Berechnen aller möglichen Ergebnisse und speichern in die Liste
        for(int i=0; i<arr.length; i++){
            for(int j =i+1; j<arr.length; j++){
                int erg =0;
                erg=arr[i]+arr[j];
                list.add(erg);
            }
        }
       
        //Prüfen ob es ein Element gibt, dass sowohl in der Liste als auch im
        //ursprünglichen Array vorkommt
        for(int y =0; y<arr.length;y++){
            if(list.contains(arr[y])){
                System.out.println("True");
                break;
            }
        }
       
        System.out.println("In der Liste befinden sich folgende Elemente "+list.toString());
       
    }

Mit nlogn hab ich noch keine Idee

Danke

 

[mrBrown]

Was ist denn s?
Denkst du nur, das es aus dem Array stammt, oder ist es so vorgegeben?

Mit nlogn hab ich noch keine Idee

Mir würde da was mit binärer Suche einfallen, kommt aber auf das s an...

 

[DaSt]

Was ist denn s?
Denkst du nur, das es aus dem Array stammt, oder ist es so vorgegeben?

Es heisst ja in der Angabe "Ausgabe: true, falls es zwei Elemente ai; aj gibt mit s = ai + aj ; i != j, false sonst"
Ich habe es so verstanden, dass wenn es im Array eine Zahl S gibt die sich aus der Addition von zwei anderen Zahlen im Array bilden lässt, dann liefere True

 

[mrBrown]

Ich les daraus, das ein festes s gegeben ist, was nicht im Array liegt, sonst wäre es sicher als a_k oä gegeben...

 

[DaSt]

naja könnte auch sein...sehe den prof. erst wieder nächste Woche Do. um nachfragen zu können

 

[JStein52]

Trotz allem denke ich dass die Lösung mit list.contains(...) keine gültige Lösung ist. Ich denke mal ihr sollt hier einen Algorithmus angeben und nicht einen "anonymen" Methodenaufruf ...

 

[mrBrown]

Trotz allem denke ich dass die Lösung mit list.contains(...) keine gültige Lösung ist. Ich denke mal ihr sollt hier einen Algorithmus angeben und nicht einen "anonymen" Methodenaufruf ...

Ob man sich da jetzt selber was bastelt oder Listen benutzt ist doch ziemlich egal und ändert an der Laufzeit nichts...Datenstrukturen wie Listen werden meistens als gegeben vorausgesetzt wenns um Algorithmen geht

 

[DaSt]

Wenn ich keine Liste benutze,kann ich die Werte(der Additionen) ja auch einfach in ein hilfsarray schreiben und dann zum schluss dieses Hilfsarray wieder mit dem orginal Array mittels 2er verschachtelten for-schleifen vergleichen. Somit hätte ich dann doch eine Laufzeit von 2*n^2 und wäre immer noch schneller als n^3

 

[JStein52]

Ob man sich da jetzt selber was bastelt oder Listen benutzt ist doch ziemlich egal und ändert an der Laufzeit nichts

Es ändert nichts an der Laufzeit, ist aber transparent was geschieht. Und wir könnten noch diskutieren ob ArrayList, HashMap, Set oder sonst noch was.

Wenn ich keine Liste benutze,kann ich die Werte(der Additionen) ja auch einfach in ein hilfsarray schreiben und dann zum schluss dieses Hilfsarray wieder mit dem orginal Array mittels 2er verschachtelten for-schleifen vergleichen.

Genau. Könntest du

 

[stg]

Was ist denn s?
Denkst du nur, das es aus dem Array stammt, oder ist es so vorgegeben?

Wenn s kein Element des Arrays sein soll, sondern fest vorgegeben wird, dann würde mir nicht einfallen, wie man die Problemlösung (nicht künstlich) so aufblähen könnte, um auf kubische Laufzeit zu kommen. Ist s fest vorgeben, so ist das Problem zudem in linearer Zeit lösbar. Daher schließe ich einfach mal, dass s aus dem Array stammen soll. Die Frage lautet also vermutlich: Gibst es ein s \in {0,...,n-1} mit a_i + a_j = a_s (usw...)
(wobei ich mich da gerade frage, ob das tatsächlich in quasi-linearer Zeit lösbar ist. Mein erster Ansatz jedenfalls taugte nichts....)

 

[stg]

Vermutlich ist dann doch s fest vorgegeben und Lösungen mittels Hashing o.Ä. sind nicht angedacht.
Dann jedenfall erstmal sortieren. Anschließend von links nach rechts übers array laufen und für jedes Element mittels binärer Suche das "Komplement" suchen.

 

[mrBrown]

Dann jedenfall erstmal sortieren. Anschließend von links nach rechts übers array laufen und für jedes Element mittels binärer Suche das "Komplement" suchen.

Das wäre auch meine Lösung gewesen. Für s in a würde mir zumindest keine "einfache" Lösung in O(n logn) einfallen. Je nach Intervall der Zahlen könnte man was countingsort-ähnliches nehmen, dann wärs linear

 

[DaSt]

Ich habe heute nochmal den Prof. gefragt wie es genau gemeint war.
Man das s stammt nicht aus dem Array sondern wird per Hand eingegeben und dann soll überprüft werden ob sich diese Zahl s aus zwei Zahlen des Arrays darstellen lässt.
Als Tipp sagte er uns wir sollen die Zahlen zuerst mit einem sortieralgorithmus der die Laufzeit nlogn hat sortieren und dann werden wir schon sehen wie es weitergeht. Da kämpfe ich gerade noch etwas damit

 

[stg]

Wo dran genau? Dem Sortieren?

Für den Fall das s vorgegeben ist hast du hier ja schon Lösungvorschläge bekommen (siehe z.B. mein Beitrag #11) . Wenn da etwas unklar ist, dann musst du nochmal genauer nachfragen.

 

[DaSt]

nein das sortieren ist mir klar, aber wie ich das dann prüfen soll (in höchstens nlogn) verstehe ich nicht und an deiner Lösung ist das einzige was ich verstehe dass es da eine For-Schleife gibt. Wieso wird bei einem so rießigen long wert gestartet, was heisst

l >>=5

oder

(((l & 31 | 64) % 95) + 32))

und wie hilft das weiter um zu prüfen ob sich S aus zwei Zahlen Ai bzw. Aj aus dem Array darstellen lässt?

 

[mrBrown]

nein das sortieren ist mir klar, aber wie ich das dann prüfen soll (in höchstens nlogn) verstehe ich nicht und an deiner Lösung ist das einzige was ich verstehe dass es da eine For-Schleife gibt. Wieso wird bei einem so rießigen long wert gestartet, was heisst

Das ist keine Lösung, das ist seine Signatur

 

[DaSt]

ohh gott, ja klar
was die binäre suche ist weiss ich aber was ist mit dem kompliment gemeint?

 

[stg]

ohh gott, ja klar
was die binäre suche ist weiss ich aber was ist mit dem kompliment gemeint?

Beispiel s=10
Im sortierten Array ist das erste Element nun etwa 1. Nun musst du mit binärer Suche schauen, ob es eine 9 gibt. Falls ja, bist du fertig. Falls nein fahre mit dem zweiten Element fort. usw...

Allgemein für das Element an Stelle i schaust du, ob dein Array ein Element mit dem Wert s-arr[i] gibt. Der Wert s-arr[i] ist das, was ich mit Komplement zu arr[i] meinte.[/i][/i][/i]

 

[stg]

Und es heißt KomplEment, ein Kompliment ist was vollkommen anderes

https://de.wikipedia.org/wiki/Komplementär

 

[DaSt]

ok danke ich versuch es mal

 

[fhoffmann]

Wenn das Array sortiert ist, sollte es auch so gehen (ungetestet):

int unten = 0;
int oben = arr.length - 1;
while (unten <= oben) {
    int summe = arr[unten] + arr[oben];
    if (summe == s) {
        return true;
    }
    if (summe < s) {
        unten++;
    } else {
        oben--;
    }
}
return false;

 

[DaSt]

Ich habe es nun so probiert wie @stg es mir geraten hat und es funktioniert, soweit ich es getestet habe

public static boolean binaereSuche(int arr[], int suche){
        int rechts = arr.length-1;
        int links=0;
       
        while(links <= rechts){
           
            int mitte = (links +rechts)/2;
           
            if(arr[mitte] < suche){
                links = mitte +1;
            }
            else if(arr[mitte] > suche){
                rechts = mitte -1;
            }
            else{
                return true;
            }
           
        }
       
        return false;
    }
   
   
   
    public static boolean summeEnthalten(int arr[], int s){
       
        for(int i =0; i< arr.length; i++){
            if(binaereSuche(arr, s-arr[i])){
                return true;
            }
        }
       
        return false;
       
    }

Vielen Dank