Laufzeitbestimmung Java Algorithmen
Hallo liebe Mitglieder,
ich bin neu hier und möchte euch um Hilfe bitten. Ich schreibe zur Zeit meine Mastertesis und möchte einen Laufzeitvergleich von zwei Algorithmen durchführen und zwar mit Hilfe der O Notation. Es geht um das Befüllen eines JTrees. Die erste Methode implementiert das "Lazy Load" Verfahren, d.h. es werden nur die Daten aus der DB geladen, die beötigt werden. Die zweite Methode ließt alle Knoten rekursiv aus der Datenbank aus. Irgendwie blick ich aber nicht wirklich durch wie man die Schritte zählt und dann auf die Laufzeit schließen kann. Des weiteren möchte beweisen, dass die Laufzeiten stimmen. Anbei beide Methoden zur Bestimmung.
Code:
public ArrayList getTreeDataByID(String id) {
ArrayList list = new ArrayList();
DataStructure node = null;
String SQL = "select id, name, parent from classes where parent = "+id;
try {
Statement st = conn.createStatement();
ResultSet rs = st.executeQuery(SQL);
while (rs.next()) {
node = new DataStructure(rs.getString(1), rs.getString(2), rs.getString(3));
list.add(node);
}
rs.close();
st.close();
} catch (SQLException e) {
System.out.println("MODEL: fkn getTreeDataByID: "+e.toString());
}
return list;
}
Rekursiv:
Code:
public ArrayList getTreeDataByID2(String id, ArrayList list) {
DataStructure node = null;
String SQL = null;
if(id == null) {
SQL = " select id, name, parent "
+ " from classes "
+ " where parent is null";
} else {
SQL = " select id, name, parent "
+ " from classes "
+ " where parent = "+id;
}
String newID = "";
try {
Statement st = conn.createStatement();
ResultSet rs = st.executeQuery(SQL);
while (rs.next()) {
node = new DataStructure(rs.getString(1), rs.getString(2), rs.getString(3));
list.add(node);
newID = rs.getString(1);
getTreeDataByID2(newID, list);
}
rs.close();
st.close();
} catch (SQLException e) {
System.out.println("MODEL: fkn getTreeDataByID: "+e.toString());
}
return list;
}
Bei dem ersten Algorithmus hab ich ne Laufzeit von 2n+7 also O(n) raus.
Bei dem zweiten 9+3n², also 3(3+n²) -> O(n²).
Jetzt hab ich das Ganze auch versucht zu beweisen, komm aber nie auf die Laufzeit.
Vielleicht weiß jemand von euch wie das funktioniert und könnte mir dabei helfen.
Vielen Dank schonmal im Voraus,
Sarah
