# Maximum Suche



## Guest (1. Mai 2005)

Hallo!

Folgendes Problem:

Ich brauche in Java einen Algorithmus, der mir aus einem unsortierten Array die log2(n) größten Werte absteigend sortiert ausgibt. Also z.B. bei 10 Werten die 3 Größten. Das ansich ist ja nicht so schwer.

Das Problem ist allerdings, dass der Algorithmus das in O(n) Zeit schaffen muss. Ich hab schon Tagelang darüber gegrübelt, aber egal was ich mache, ich kriegs nur in O(n*logn) Zeit hin.
So langsam denke ich, dass das gar nicht möglich ist.

Danke für die hilfe schon mal im Vorraus!


----------



## Beni (1. Mai 2005)

Sind das Integer oder was anderes? Falls es Integer sind: guck dir mal Radixsort an, damit kann man einen Array in O(n) sortieren (und danach ist es kein Problem mehr).


----------



## Guest (1. Mai 2005)

Es sind Integer Werte!
Hey der Tipp war gut.  Mit Radixsort klappts!
Vielen Dank


----------



## Guest (1. Mai 2005)

wobei......

mir ist grad aufgefallen, dass Radixsort nur für Werte mit begrenztem Wertebereich funktioniert bzw. so fix ist. 
bei meinem Array sind allerdings die Werte in ihrer Größe unbekannt, also beliebig groß.

das ist also doch noch nicht die Lösung. Trotzdem Danke.


----------



## Beni (1. Mai 2005)

Naja, Integer haben eine maximale Grösse, weil sie nur aus 32 Bits bestehen.

Aber falls du sonst eine Lösung findest, die nehme mich auch wunder.


----------



## Jemand, der bescheid weis (3. Mai 2005)

Hallo,

ich hatte ein ganzes Semester lang dieses Thema.
Es gibt keinen Sortier-Algorithmus, der immer
O(n) hat.

Der schnellste ist Quicksort, der hat (n log(n)) im Durchschnitt;
es geht nicht schneller.

Mehr Infos bei google, Suche nach:

"quicksort" oder "sortier-algorithmen"

Gruß


----------



## Wildcard (3. Mai 2005)

> Der schnellste ist Quicksort, der hat (n log(n)) im Durchschnitt;
> es geht nicht schneller.


Im durchschnitt sind Quick und MergeSort die Schnellsten, aber in Einzelfällen ist BogoSort einfach nicht zu schlagen  :wink:


----------



## mic_checker (3. Mai 2005)

Wobei man natürlich noch unterscheiden müsste. QuickSort bietet keine gesichtere Laufzeit, in Fällen wo das nötig ist greift man eher zu gesicherten Verfahren wie Merge Sort....


----------



## Guest (8. Mai 2005)

ich habs jetzt rausgefunden!
Es ist möglich. Man nimmt einfach eine abgespeckte version des Heapsort Algorithmus.
Man baut zuerst einen Heap auf (O(n) Zeit) und nimmt dann log n - mal das maximum daraus (O(log n) Zeit).
das ergibt F(n) = n + log n * log n und das ist bekanntlich aus O(n)!
n bissel tricky aber es geht.


----------



## Hansdampf (24. Mai 2005)

> ich hatte ein ganzes Semester lang dieses Thema.
> Es gibt keinen Sortier-Algorithmus, der immer
> O(n) hat.


doch, mit n Prozessoren geht das ganz locker.  *klugscheissundduck*


----------



## Wildcard (24. Mai 2005)

Hansdampf hat gesagt.:
			
		

> > ich hatte ein ganzes Semester lang dieses Thema.
> > Es gibt keinen Sortier-Algorithmus, der immer
> > O(n) hat.
> 
> ...


Das o-Kalkül bezieht sich auf die Anzahl der notwendigen Operation. Mit n Prozessoren werden die Schritte nicht weniger, sondern nur die dafür benöigte Zeit nimmt ab.  :wink:


----------



## Hansdampf (24. Mai 2005)

> Das o-Kalkül bezieht sich auf die Anzahl der notwendigen Operation.


stand nicht explizit dabei. Hätte auch die Laufzeitkomplexität O(n) sein können. :wink:


----------



## Wildcard (24. Mai 2005)

Hansdampf hat gesagt.:
			
		

> > Das o-Kalkül bezieht sich auf die Anzahl der notwendigen Operation.
> 
> 
> stand nicht explizit dabei. Hätte auch die Laufzeitkomplexität O(n) sein können. :wink:


netter Versuch http://de.wikipedia.org/wiki/Laufzeitkomplexität


----------



## Hansdampf (24. Mai 2005)

mist


----------



## Hansdampf (24. Mai 2005)

doch nicht mist.


> Unter der Zeitkomplexität eines Problems versteht man die Anzahl der Rechenschritte, die ein optimaler Algorithmus zur Lösung dieses Problems benötigt


werden n Schritte parallel ausgeführt, zählt das als 1 Schritt.


----------



## Wildcard (24. Mai 2005)

Hansdampf hat gesagt.:
			
		

> werden n Schritte parallel ausgeführt, zählt das als 1 Schritt.


wo steht denn das??


----------



## Hansdampf (24. Mai 2005)

du sagst also, dass man mit n prozessoren nicht in der Zeitkomplexität O(n)  sortieren kann?
solln wir auf die Straße?


----------



## Wildcard (24. Mai 2005)

Hansdampf hat gesagt.:
			
		

> du sagst also, dass man mit n prozessoren nicht in der Zeitkomplexität O(n)  sortieren kann?
> solln wir auf die Straße?


Beim O-Kalkül geht es um die Komplexitätsklasse des Problems. Ein Sortieralgorithmus kann mit mehren oder schnelleren Prozessoren zwar schneller zu einem Ergebnis kommen, aber an der Kompexität des Problems ändert sich deshalb nichts.
Genau aus diesem Grund werden ja auch die benötigten Schritte und nicht die benötigte Zeit analysiert.


----------



## Hansdampf (24. Mai 2005)

> Satz 4 Der Algorithmus LSortieren kann auf einer PRAM mit O(n) Prozessoren, Zeitaufwand T (n) = O(n) und
> 
> Kosten W(n)=O(n2) implementiert werden.


 

oh mann, jetzt musste ich 5 min googlen nur weil du mir nicht glaubst.
okok, hab ich freiwillig gemacht

www.info.uni-karlsruhe.de/~glesner/proseminar/dennis_pros4.ps


----------



## Wildcard (24. Mai 2005)

*nachgeschauthat*


> Auf einer sequentiell arbeitenden Maschine mit nur einem Prozessor ist die Zeitkomplexität gleich der Aufwandskomplexität. Umgekehrt bezeichnet der Aufwand auf einer parallel arbeitenden Maschine gerade die Zeit, die eine sequentiell arbeitende Maschine für die Berechnung benötigt.



http://www.netzwelt.de/lexikon/NC_(Komplexitätsklasse).html

Die Kosten bleiben zwar gleich, aber der Begriff Zeitkomplexität bedeutet bei parellelen Systemen tatsächlich etwas anderes, insofern geb ich dir da recht.  :wink:


----------



## Hansdampf (24. Mai 2005)

:bae: 
wetten, es geht auch in  O(log n)?
war nurn Cherz


----------

