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
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
Mit nlogn hab ich noch keine Idee
Danke
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
Java:
//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
Java:
//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
