Sortieralgorithmus in O(log n)?

...komplette Frage anzeigen

5 Antworten

Um beliebige Zahlen zu sortieren ist O (n log n) absolutes Minimum.

Wenn du aber Zahlen zwischen 1 und 10 sortieren willst dann geht das in O(n).

Darunter kann logischerweise nicht gehen, da du bei O(log n) nicht mal jedes Element ansehen kannst, dann kannst du es auch nocht einsortieren.

ReginaSuperSofi 13.07.2017, 21:41

Nur wenn es schon sortiert ist, ist es O(n), naja wirklich "sortieren" ist dies nicht ;)

0
BrutalNormal 13.07.2017, 21:47
@ReginaSuperSofi

Best case geht natürlich mit O(n).

Der Algorithmus muss aber auch ab und zu die anderen n!-1 Permutationen ordnen können :)

Und dann gibt es auch sau ungünstige Konstellationen.

0
triopasi 13.07.2017, 21:49
@ReginaSuperSofi

Wenn es sortiiert ist musst du nicht sortieren. Wir reden hier immer Worst-Case ^^

0
Tuxgamer2 13.07.2017, 22:41
@ReginaSuperSofi

Ne, k kannst du in den Fällen als 1 annehmen - den Algorithmus ausführen gänge logischerweise auch nicht, hättest du alle Resourcen des Universums. Laufzeit ist trotzdem O(n).

0

Du solltest dir dringend noch einmal die O-Schreibweise anschauen - denn da fehlt noch ein bisschen grundlegendes Verständniss.

O(Konstante log n) wäre auch akzeptabel.

O(c * n) ist exakt das gleiche wie O(n).

Konstanten werden bei der O-Schreibweise schlicht und einfach weggelassen.

Bedeutet gleichzeitg, man durchläuft nicht einmal die gesamte Liste

Und spätestens da solltest du feststellen, dass Sortieren in log n absoluter Schwachsinn ist.

Okay, hast irgendeine Folge, die du sortieren musst. Es gibt ein Element x, dass beim Sortieren nicht angeschaut wird. Der Algorithmus verhällt sich also gleich, egal was das x ist.

Wohin sortierst du das x?

Sortierst du das x in die Mitte oder ans Ende, wähle ich das x kleiner als jede andere Zahl -> Algorithmus funktioniert nicht.

Sortierst du das x an den Anfang, wähle ich das x größer als jede andere Zahl -> Algorithmus funktioniert nicht.

=> Gezeigt: Sortieren in <O(n) kann nicht klappen.

ReginaSuperSofi 13.07.2017, 22:04

Es gibt einen Unterschied zwischen O(nahe Unendlich log n) und O(log n), nur weil man es kürzen kann, heißt es nicht das die Konstanten wertlos sind, frag dich sonst einmal wieso Quicksort schneller als Mergesort ist bei sehr großen n, obwohl beides O(n log n) hat bzw. Quicksort sogar O(n^2) im Worst-case

0
Tuxgamer2 13.07.2017, 22:40
@ReginaSuperSofi

Was ist denn nahe Unendlich?  Ne Millionen? Na, quadrieren wir mal. Sind wir der Unendlichkeit auch nur ein Stück näher gekommen? Wohl kaum.

Quicksort hat sich gezeigt, dass es in Realität realen Bedingungen häufig schneller ist. Dies ist aber unter anderem abhängig von:

* Optimiering

* Verwendete Hardware

* Qualität der Eingabe (z.B. Sortierungsgrad)

* ...

Das Quicksort bei großen Eingaben immer schneller ist, ist i.A. nicht richtig. Und unabhängig davon interessiert das bei O Betrachtungen nicht.

Und ja: Schreibst du O(log n) erlaubst du automatisch auch O(100000^100000 log n). So einfach.

0

Wenn du bestimmte Sachen über die Liste weißt, ist das denkbar, aber kein solcher Algorithmus wird für gewöhnliche Probleme praktikabel sein.

Hier kannst du einen Sortieralgormus wählen:

https://de.wikipedia.org/wiki/Kategorie:Sortieralgorithmus

...oder auf Englisch. Vorsicht, O(log n) Algorithmen benötigen viele Prozessoren.

Tuxgamer2 14.07.2017, 10:24

>> Vorsicht, O(log n) Algorithmen benötigen viele Prozessoren.

Das ist Blödsinn.

1. Laufzeit bei Algorithmen in 0- Schreibweise hat nichts, also absolut nichts, mit der Anzahl verwendeter Prozessoren bei einer Ausführung zutun.

2. Du kannst so viele Prozessoren hinstellen wie du willst. Von O(n) auf O(log n) kommst du deshalb trotzdem nicht.

0
ReginaSuperSofi 13.07.2017, 21:35

Ist aber die obere Schranke

0
ReginaSuperSofi 13.07.2017, 21:39
@ReginaSuperSofi

bzw. beweist dies es für vergleichsbasierte Sortierverfahren, vielleicht gibts auch andere?  (ich kann mir keins vorstellen, aber ich meine dafür fragt man ja .. :))

0
Roderic 13.07.2017, 21:40
@ReginaSuperSofi

Wenn gilt: O(n log(n)) ist untere Schranke, dann kann O(log(n)) nicht obere sein.

Das wollte dir BrutalNormal damit sagen.

Auf deutsch: Dein Suchen ist vergeblich.

0
Tuxgamer2 13.07.2017, 22:32
@ReginaSuperSofi

Was soll denn eigentlich obere Schranke bei Algorithmen sein? Kannst doch immer noch blödere Algorithmen mit noch schlechterer Laufzeit schreiben.

1
ReginaSuperSofi 13.07.2017, 22:59
@Tuxgamer2

beweist diese Frage nicht eigentlich schon, dass du eigentlich keine Ahnung von dem hast was du schreibst? ;)
alles mit einem O() ist die obere Schranke

0
Tuxgamer2 14.07.2017, 09:01
@ReginaSuperSofi

Dir ist schon klar, dass es einen Unterschied gibt zwischen:

Obere Laufzeitschranke im Mittel bei einem konkreten Algorithmus (ist offensichtlich)

Obere Laufzeitschranke bei dem Problem Sortieren (macht keinen Sinn).

0

Was möchtest Du wissen?