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