Pseudocode in 0(n) |
| 12.11.2014, 16:56 | Auf diesen Beitrag antworten » |
| 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. |
|
|
|
| 12.11.2014, 18:32 | Auf diesen Beitrag antworten » |
| 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)). |
| 19.11.2014, 13:03 | Auf diesen Beitrag antworten » |
| 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 |
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
