Heapsort Aufwand

    Bin auf der Suche nach dem Worst Case von Heepsort.
    Leider stoße ich im Netz auf Unterschiedliche Informationen

    O(log (n)) und O(n log(n))

    Ich glaube O(log (n)) ist richtig


    Wenn ich in eine Priority Queue mit einen Heap als Struktur mache dann sollte dabei
    der Aufwand dann gleich dem Heap sein oder ? ?


    Zitat von Christoph R.

    Theta(n log(n)) ist richtig. Das ist auch die Komplexität des Sortierproblems, der Algorithmus kann daher gar nicht schneller sein (und auch kein anderer).

    dem stimme ich (bzw mein algodat-skript) zu. vielleicht zusaetzlich noch interessant:
    C_max = C_avg = C_min = Theta (n log (n))
    M_max = M_avg = M_min = Theta (n log (n))

    Willfähriges Mitglied des Fefe-Zeitbinder-Botnets und der Open Source Tea Party.

Jetzt mitmachen!

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

Benutzerkonto erstellen Anmelden