Abschätzen von Laufzeiten

    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:

    Code
    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

    Auf den ersten Blick ist n mal richtig.
    Wieso? --> n schleifen durchläufe.
    Das ist aber nur ein Teil der Laufzeit.
    In jedem Schleifendurchlauf wird das jeweilige Element in das TreeSet eingefügt.
    Du hast also Teta(n) (es sind ja genau n Elemente) * O(einfügen in den Tree)
    das ergibt O(n*log n)
    ist das halbwegs verständlich?

    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...

    Weil es sich wahrscheinlich um einen binären Baum handelt. Du traversierst den Baum Ebene für Ebene und entscheidest, ob du nach links oder nach rechts gehst. Wenn der Baum noch kein Item enthält, ist die Laufzeit für das Einfügen gleich 0, bei einem Item 1, bei zwei Items 1 bis 2, bei drei Items 2, bei vier Items 2 bis 3 usw. (mach dir eine Skizze, um es zu veranschaulichen). Die Laufzeit ist immer ungefähr gleich dem dualen Logarithmus der bereits eingefügten Anzahl von Items. So kommt insgesamt n * log n zustande. Es ist eine sehr grobe Abschätzung, vergiss nicht, dass die Big-O-Notation ja bedeutet, dass die tatsächliche Laufzeit bis zu einem (konstanten) Vielfachen des in den Klammern angeführten Terms betragen kann!

Jetzt mitmachen!

Sie haben noch kein Benutzerkonto auf unserer Seite? Registrieren Sie sich kostenlos und nehmen Sie an unserer Community teil!

Benutzerkonto erstellen Anmelden