Maximum Suche

[Guest]

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]

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]

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

 

[Guest]

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]

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]

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]

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]

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]

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]

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]

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*

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]

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]

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]

mist

 

[Hansdampf]

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]

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

wo steht denn das??

 

[Hansdampf]

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

 

[Wildcard]

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]

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]

*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]

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