Laufzeitbestimmung Java Algorithmen

[maumau306]

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.

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:

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

[anda_skoa]

Die zweite Variante ist nicht notwendigerweise in quadratisch Komplexität, sondern es hängt davon ab, wie die Datenbank organisiert ist.

Wenn du lineare Suche an nimmst und das auch so der Fall ist, dann ist jedes executeQuery linear und somit dein Code nicht mehr.

Der zweite Algorithmus ist vermutlich rein akademisch, oder?
Eine Liste aus einer Liste zu erzeugen ist nun mal am einfachsten mit einer simplen Schleife

Ciao,
_

[maumau306]

Hey,
danke für deine Antwort. Die Datenbanktabelle "classes" aus der die einzelnen Knoten ausgelesen werden, besteht nur aus den Feldern id, name und parent. Das Ganze is ne Weiterentwicklung meiner BA Thesis und soll flexibel in der Anzahl der Ebenen in einem Baum sein. Daher kommt die Lösung mit dem Vorgänger.

Ja die zweite Variante is nur für diesen Vergleich. Wird nicht genutzt.


So wie ich das mit dem Befehl executeQuery verstanden hab, wird der SQL String einmalig augeführt und das ResultSet Objekt ist dann ne Liste der Datensätze, die in der while Schleife abgearbeitet werden. Somit müsste diese doch n-Mal durchlaufen werden und der rekursive Aufruf ebenfalls n Mal.

[anda_skoa]

Ja, im einfachsten Falls wird die SQL Query so ausgeführt.

Die Sache ist, dass Datenbanken so optimiert werden können, dass sie einen index für bestimmte Felder haben, die dann eine optimierte Suche erlauben (quasi wie eine Suche in einem sortiertem Baum).

Das könnte sich dann auswirken wenn du keine Liste erstellen würdest sondern direkt den Baum.

Beide Varianten geben dir derzeit eine Gesamtkomplexität von n².

Ciao,
_