Frage zu Zeitkomplexität von Sortieralgorithmen

[metalstore]

Frage zu Zeitkomplexität von Sortieralgorithmen

Hey, ich hab mal ne frage zu der Zeitkomplexität von 1)Bubble-, 2)Quick-, 3)Insertion- und 4)Selectionsort.
wenn ich das richtig verstanden habe, haben alle eine Zeitkomplexität von O(n²) (also worst case scenario),
allerdings gilt dies bei Quicksort nur, wenn das Pivotelement stehts das größte oder kleinste Element ist,
ist das Pivotelement nicht das größte oder kleinste Element (dann egal welches andere?),
so ist Quicksort's Zeitkomplexität im worst case O(n*log(n))?

mfg
metalstore

 

[Evandar]

AW: Frage zu Zeitkomplexität von Steueralgorithmen

ist das Pivotelement nicht das größte oder kleinste Element (dann egal welches andere?),
so ist Quicksort's Zeitkomplexität im worst case O(n*log(n))?

Ich denke du meinst best case für O(n*log(n)).

Technisch ist es, soweit ich mich erinnere, egal ob du das beste Pivotelement ermittelst. Es darf halt nur nicht das größte oder kleinste sein. Wenn du genau die Mitte triffst, dann sind beide Teilmengen halt genau gleich groß, wenn nicht verschiebt sich das leicht, was aber kein großer Nachteil ist. Das Sortieren der kleineren Menge ist dann halt entsprechend "günstiger".

 

[DarkMo]

AW: Frage zu Zeitkomplexität von Steueralgorithmen

(kann man den Titel nachträglich nicht mehr ändern?)

doch, musst auf bearbeiten und danach nochmal auf erweitert - da kannste auch den titel dann anpassen

 

[metalstore]

AW: Frage zu Zeitkomplexität von Steueralgorithmen

Ich denke du meinst best case für O(n*log(n)).

Technisch ist es, soweit ich mich erinnere, egal ob du das beste Pivotelement ermittelst. Es darf halt nur nicht das größte oder kleinste sein. Wenn du genau die Mitte triffst, dann sind beide Teilmengen halt genau gleich groß, wenn nicht verschiebt sich das leicht, was aber kein großer Nachteil ist. Das Sortieren der kleineren Menge ist dann halt entsprechend "günstiger".

hab heute nochmal mit unserem Infolehrer gesprochen, also worst case bei Quicksort wäre ebenfalls O(n²), das wäre halt nur, wenn man den Algorithmus "misshandelt", also wenn als Pivotelement stehts das größte oder kleinste genommen wird, in allen anderen Fällen liegt die Zeitkomplexität bei O(n*log(n)) liegen
[was meinst du mit "kein großer Nachteil", gibt es denn einen Nachteil, wenn man nicht die exakte Mitte als Pivot nimmt, die größere Menge und die kleinere Menge (entstehend durch das nicht exakt mittige Pivot) gleichen sich doch wieder vollkommen aus (also dass das Pivotelement egal ist, solange es nicht das größte oder kleinste ist?)]

 

[Evandar]

AW: Frage zu Zeitkomplexität von Steueralgorithmen

[was meinst du mit "kein großer Nachteil", gibt es denn einen Nachteil, wenn man nicht die exakte Mitte als Pivot nimmt, die größere Menge und die kleinere Menge (entstehend durch das nicht exakt mittige Pivot) gleichen sich doch wieder vollkommen aus (also dass das Pivotelement egal ist, solange es nicht das größte oder kleinste ist?)]

Das letzte mal das ich QS genau betrachten musste ist schon Jahre her, deswegen entschuldige bitte meine Ungenauigkeit. Aber soweit ich mich erinnern kann, gab es tatsächlich ein paar Fälle in der die nicht optimale Wahl des Pivot Elementes nicht mehr zur optimalen Leistung führte. Aber diese waren wenn dann nur minimal langsamer und sehr konstruiert (in der Praxis unwahrscheinlich). In der Regel aber hast du recht, es gleicht sich wieder aus.

 

[metalstore]

kein Thema
ja gut, die Arbeit ist geschrieben (heute 3.+4. Stunde)
bei allen anderen aus dem Kurs...eigentlich genauso wie bei mir, Themenbereich Sortieralgorithmen war ok/gut, ganz im Gegensatz zu SQL
dank unserem lieben Lehrer ^^

 

[Evandar]

AW: Frage zu Zeitkomplexität von Sortieralgorithmen

Hättest du dann wohl doch lieber SQL gefragt ^^

 

[metalstore]

nein, weil lieber eins richtig als zwei nur halb

und da es eigentlich bei jedem so is, können wir dem Lehrer noch eins zusätzlich auf den Deckel geben