Maximum Suche

Status
Nicht offen für weitere Antworten.
G

Guest

Gast
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!
 
B

Beni

Gast
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).
 
G

Guest

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

Guest

Gast
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.
 
B

Beni

Gast
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.
 
J

Jemand, der bescheid weis

Gast
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

Top Contributor
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

Top Contributor
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....
 
G

Guest

Gast
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.
 

Wildcard

Top Contributor
Hansdampf hat gesagt.:
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

Bekanntes Mitglied
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.
 

Hansdampf

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

Wildcard

Top Contributor
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.
 

Wildcard

Top Contributor
*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:
 
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen
  Titel Forum Antworten Datum
S Maximum Likelihood Methode in statistik Allgemeine Java-Themen 2
byte JVM Maximum Heap (Windows XP Prof. 32bit) Allgemeine Java-Themen 4
M Suche nach String mit unbekannten characters Allgemeine Java-Themen 53
M Binäre Suche Allgemeine Java-Themen 6
M geometrische Suche Allgemeine Java-Themen 8
J Programm schreiben, das mir aufgrund von Schlagwörtern, die ich im Internet suche, relevante Themen sofort anzeigt. Allgemeine Java-Themen 1
I HTML / XHTML Seite nach Excel exportieren. Suche Lib Allgemeine Java-Themen 12
W Suche Ursache für NPE - woher kommt sie? (Hilfe beim Debugging) Allgemeine Java-Themen 19
W Collections Suche Collection, um Strings mit Indizees versehen Allgemeine Java-Themen 47
O Suche Scripter für alt:V Project! Allgemeine Java-Themen 0
D Suche Quellcode! Allgemeine Java-Themen 8
O Suche Unterstützung für ein OpenSource-Projekt (grafischer Editor) Allgemeine Java-Themen 13
B Bei Email: FW / AW... - Hilfe bei String suche Allgemeine Java-Themen 21
J Suche Alternative zu Jasper Reports Allgemeine Java-Themen 4
W Collections Suche etwas Sorted-List-Artiges...hat jemand eine Idee? Allgemeine Java-Themen 13
M Suche Alternative zu JFreeChart Allgemeine Java-Themen 11
S Warmup für Lineare-Suche mit Zeitmessung Allgemeine Java-Themen 2
K OOP Suche Hilfe + Erklärung für eine Hausaufgabe Allgemeine Java-Themen 1
B Suche nach einem Testprogramm für meine BA Allgemeine Java-Themen 0
D Objekt-Suche mit mehreren optionalen Parametern Allgemeine Java-Themen 6
A NetBeans Suche Programmierer für eine Belegarbeit Allgemeine Java-Themen 11
O Suche größeres Beispiel für WebserverAnwendung mit Java Allgemeine Java-Themen 2
G Google-Suche ist nicht auslesbar?! Allgemeine Java-Themen 18
M Suche aktuelle Apache Poi Bibliothek zum Einbinden in mein Programm Allgemeine Java-Themen 2
L Suche nach CalDav Server API Allgemeine Java-Themen 0
HarleyDavidson Best Practice Suche "Container" für Modulapplikationen Allgemeine Java-Themen 0
S Suche Konzept: Korrektheit des Aufrufers feststellen Allgemeine Java-Themen 7
KaffeeFan Methoden Suche Methode um Programm kurz warten zu lassen Allgemeine Java-Themen 22
B Suche geeignete Datenstruktur Allgemeine Java-Themen 5
L Erste Schritte Suche Java Wiki System? Allgemeine Java-Themen 5
L Suche Geräte für Java SE Embedded Allgemeine Java-Themen 0
S Rekursive Suche in einem Netz Allgemeine Java-Themen 5
F Über Java Google Suche nutzen Allgemeine Java-Themen 11
A Suche Android Programmierer Allgemeine Java-Themen 0
W Suche Framework zur Prüfung von IPv4 und IPv6 Allgemeine Java-Themen 2
A Java - Suche nach Datensatz mit DateChooser Allgemeine Java-Themen 0
S Pattern.Match Suche: For Schleife einbinden und in Liste schreiben Allgemeine Java-Themen 3
M Suche Framework/API für Monitoring-Anwendung Allgemeine Java-Themen 3
F Suche kostenlose GUI für Eclipse Allgemeine Java-Themen 10
H Suche mit Wildcards und boolschen Operatoren Allgemeine Java-Themen 4
B Suche passende Datenstruktur für 2 Einträge Allgemeine Java-Themen 19
A Binäre Suche im Array mit StackOverflowError Allgemeine Java-Themen 3
T Verkettete Suche Allgemeine Java-Themen 6
S RxTx - langsame Port suche Allgemeine Java-Themen 3
D Suche Matrix Libraries Allgemeine Java-Themen 11
S Suche Dependency Injection Container Allgemeine Java-Themen 6
J Suche: Tool zum Auffinden gleichnamiger Klassen (Name und Package gleich) in unteschiedlichen JARs Allgemeine Java-Themen 5
BinaryLogic Input/Output Suche Wörterbuch-Datei Einzahl/Mehrzahl Allgemeine Java-Themen 2
A Suche Algorithmus zum Erstellen eines planaren Graphen Allgemeine Java-Themen 5
D Suche Librarys ähnlich datatables.net + Login Allgemeine Java-Themen 3
Gossi Threads Suche ein (einfaches) Beispiel Allgemeine Java-Themen 5
P Erste Schritte Suche in ArrayList mit Maps Allgemeine Java-Themen 4
F Suche Performanceoptimierung bei Stringsortierung Allgemeine Java-Themen 51
B Suche Datenquelle für lizenz-informationen Allgemeine Java-Themen 5
J Lucene suche in Json (CouchDB) Allgemeine Java-Themen 2
X Suche Softwareimplementierung von Cryptographischen Algorithmen Allgemeine Java-Themen 3
S Suche Tipps für Einstieg in JavaCC Allgemeine Java-Themen 2
R Suche in logfiles mit Lucene / Solr Allgemeine Java-Themen 2
P Suche Datenstruktur Allgemeine Java-Themen 2
M Suche Java-Projekt zum Thema Elektrotechnik Allgemeine Java-Themen 6
F Suche Begriff Allgemeine Java-Themen 2
hdi Suche Icon-Sammlung Allgemeine Java-Themen 7
G Suche "richtiges" Framework/Library Allgemeine Java-Themen 14
slawaweis Suche Klassen für Event Managment und Time Allgemeine Java-Themen 2
P Probleme mit wikipedia quellcode zur binären Suche Allgemeine Java-Themen 6
C Suche Permutationsalgo Allgemeine Java-Themen 6
E Suche nach Foto-Dummy Allgemeine Java-Themen 8
B Suche Paket zum auslesen von Metadaten von Bildern. Allgemeine Java-Themen 4
N suche globale Tastenabfrage Allgemeine Java-Themen 6
P SUCHE: gute Geo Library (freeware) Allgemeine Java-Themen 2
P Suche performante PDF Library Allgemeine Java-Themen 20
data89 Bilder mit Java prüfen - suche dringend Hilfe Allgemeine Java-Themen 8
faetzminator Regex zur Suche von "value-losen" Attributen in HTML Tags Allgemeine Java-Themen 7
S Suche im JTree nach Neuaufbau Allgemeine Java-Themen 4
W Problem bei der Suche (binarySearch) vom deutschen Sonderzeichen "ß" im einem Array Allgemeine Java-Themen 6
D Suche nach passender Datenstruktur Allgemeine Java-Themen 4
S suche library die diagramme darstellen kann Allgemeine Java-Themen 2
T Suche Anhaltspunkt für plattformübergreifende, "unique machine id" ... Allgemeine Java-Themen 12
P WebSerive Suche Allgemeine Java-Themen 15
hdi Suche nach Begriff aus der Programmierung Allgemeine Java-Themen 11
X Suche Java Klasse die Feiertage berechnen kann Allgemeine Java-Themen 2
B suche Deutsche Übersetzung für neuste Eclipse Version Allgemeine Java-Themen 6
Daniel_L Suche nach ganzen Wörtern (wholeword) in Strings? Allgemeine Java-Themen 4
G Regex-Suche nach Worten Allgemeine Java-Themen 3
Antoras Suche Projektarbeit für Gruppe mit 3 Leuten Allgemeine Java-Themen 5
G Perfomante Suche in grosser Datei Allgemeine Java-Themen 6
T Suche Tool Allgemeine Java-Themen 11
D Suche sowas wie Map nur für mehrere Werte Allgemeine Java-Themen 13
D Suche Hilfe zum Rechnerübergreifenden Dateizugriff. Allgemeine Java-Themen 3
M suche speziellen Sortieralgorithmus Allgemeine Java-Themen 3
E javax.comm: Suche eine open source Alternative zu rxtx Allgemeine Java-Themen 8
J Suche regex-Pattern fuer Liste von Zahlen zwischen 0-100 Allgemeine Java-Themen 6
T Suche den großen Calendar Thread ! Allgemeine Java-Themen 2
P Suche Benis IP/Netzwerkadresse JTExtField Allgemeine Java-Themen 2
J Suche Doku um generischen Code zu erstellen. Allgemeine Java-Themen 9
G suche Property alternative Allgemeine Java-Themen 4
C Fehler im Quellcode. Suche in einem Baum Allgemeine Java-Themen 3
S Suche Pendant zu einem VB Befehl Allgemeine Java-Themen 2
T Suche gute JAVA Steuerelemente Allgemeine Java-Themen 2
V Suche RegEx zu (gelöstem) Problem Allgemeine Java-Themen 3

Ähnliche Java Themen

Neue Themen


Oben