| Die letzten 3 Beiträge |
| heikob2 |
RE: Pseudocode in 0(n)
Es ist möglich, da der Wertebereich 1 bis (2^n) - 1 beträgt. Der Algorithmus heißt Bucket-Sort:
- Du legst ein Array "L" von 1 bis( 2^n)-1 an und initialisierst jedes Feld mit null.
- Dann iterierst du durch A und inkrementierst L[A[i]].
- Für die Ergebnismenge iterierst du durch L und fügst falls L[i] > 0, das Element "i" L[i]-mal in diese ein.
=> O(n).
gruß Heiko |
| eulerscheZahl |
Ist das der originale Wortlaut der Aufgabe?
Es ist nicht möglich, n^2-1 Werte in O(n) zu sortieren, mit dem Mergesort erreichst du O((n^2-1) * log(n^2-1)). |
| 330677 |
Pseudocode in 0(n)
Meine Frage:
Ich soll einen Algorithmus in Pseudocode schreiben, welcher ein Feld A mit Wertebereich {1,..(n^2) - 1} in O(n) sortiert
Meine Ideen:
Habe leider keine Ahnung wie ich an die Sache rangehen soll. |
|
|
