Aufwand für Algorithmen



  • Also ich habe 2 Teilfragen:

    1. Wenn ich einen Sortieralgorithmus gegeben habe aus was berechnet sich der Aufwand überhaupt... Anzahl der Vergleiche? oder Anzahl der Tauschoperationen oder die Summe aus beidem? irgendwie kommt es mir vor als wenn immer nur die Anzahl der Vergleiche gezählt wird.

    2. Ein Algorithmus habe den Aufwand O( n log n)
    ZU welcher Basis ist denn dieser Logarithmus? oder ist das nebensächlich da es eher um die Tendenz geht? Oder der 2-er Logarithmus...

    ich habe nämlich in einer Mitschrift eines Freundes gelesen dass der mittlere Aufwand von Qucicksort O(n ln n) sei ... ich lese aber sonst überall n log n ohne basisangebe



  • shisha schrieb:

    1. Wenn ich einen Sortieralgorithmus gegeben habe aus was berechnet sich der Aufwand überhaupt... Anzahl der Vergleiche? oder Anzahl der Tauschoperationen oder die Summe aus beidem? irgendwie kommt es mir vor als wenn immer nur die Anzahl der Vergleiche gezählt wird.

    Anzahl der Operationen insgesamt. Da aber bei Sortieralgorithmen immer Anzahl der Vergleiche > Anzahl der Tauschoperationen gilt, kann man letztere vernachlässigen.

    2. Ein Algorithmus habe den Aufwand O( n log n)
    ZU welcher Basis ist denn dieser Logarithmus? oder ist das nebensächlich da es eher um die Tendenz geht? Oder der 2-er Logarithmus...

    Ist nebensächlich, da es nur um die Tendenz geht.



  • shisha schrieb:

    Also ich habe 2 Teilfragen:
    2. Ein Algorithmus habe den Aufwand O( n log n)
    ZU welcher Basis ist denn dieser Logarithmus? oder ist das nebensächlich da es eher um die Tendenz geht? Oder der 2-er Logarithmus...

    ich habe nämlich in einer Mitschrift eines Freundes gelesen dass der mittlere Aufwand von Qucicksort O(n ln n) sei ... ich lese aber sonst überall n log n ohne basisangebe

    Wenn du einen beliebigen logunbekannte_basisx\log_{unbekannte\_basis}x hast, kannst du ihn in log2x\log_2x umwandeln, indem du durch logunbekannte_basis2\log_{unbekannte\_basis}2 teilst. Und wie du sicher weißt, fallen konstante Faktoren in der O-Notation weg, deshalb beschreiben beide logs die gleichen Mengen.
    Achtung: das geht nur zufällig bei log so: 4n4^n ist eine andere komplexitätsklasse als 2n2^n, genauso wie ja n2n^2 etwas anderes ist als n3n^3; nicht einfach stur zahlen durch andere ersetzen 😉


Log in to reply