 Hirsch-Algorithmus mit div. Laufzeiten |
te one
Grünschnabel
Dabei seit: 22.10.2015
Beiträge: 6
 |
|
| Hirsch-Algorithmus mit div. Laufzeiten |
     |
Guten Abend,
ich suche 2 Algorithmen zur Berechnung des Hirsch-Index einer Person (z.B. mind. 4 Veröffentlichungen, die mind. 4mal zitiert wurden --> Index 4).
Eingabe ist ein Array von Integern, die jeweils für eine Zitierung stehen (zB. Array = 1,2,3,2,2 --> Artikel 1 wurde 1mal zitiert, Artikel 2 3mal zitiert, Artikel 3 1mal zitiert).
Nun brauche ich einen solchen Algorithmus mit Laufzeit O(n*log(n)) und einen mit O(n^2).
Meine bisherigen Anhaltspunkte:
Eine gute Beschreibung habe ich auf Wikipedia gefunden (h-Index: Definition) - jedoch m. E. mit Laufzeit O(n)
Damit sich eine Laufzeit von O(n*log(n)) ergibt muss es sich wahrscheinlich um einen rekursiven Ansatz handeln.
Damit die Laufzeit O(n^2) ist wird wohl innerhalb einer Iteration über das ganze Array nochmal iteriert.
Den Ansatz auf Wikipedia finde ich gut, ich komme auf nichts anderes 
Bitte gebt mir ein paar Tipps/Hinweise
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von te one: 28.10.2015 17:19.
|
|
28.10.2015 17:19 |
|
|
te one
Grünschnabel
Dabei seit: 22.10.2015
Beiträge: 6
|
|
In Wikipedia steht nichts von O(n), jedoch dachte ich mir das beim Betrachten der Beschreibung. Jedoch war hier der Sortieralgorithmus nicht berücksichtigt sondern das reine h-index finden danach...
Das heißt im Endeffekt, dass ich mir Sortieralgorithmen mit Laufzeit O(n*log(n)) bzw. O(n^2) suche und dann gemäß Wikipedia den h-Index erzeuge (ist ja quasi dann nur +n Laufzeit die man weglasssen kann).
Korrekt?
Dann muss ich jetzt noch einen Weg finden wie ich die Eingabe (Ist ja immer die Nummer eines Artikels, teils eben mehrfach) in die Form eines Arrays bringe, sodass im Array die Anzahl der Zitierungen steht.
Wie bestimme ich nun aber zu Beginn die Länge des Arrays, wenn ich zB 1,3,10,3 geliefert bekomme? Könnte das größte Element raussuchen (10) und dann ein Array [10] erzeugen und dann eben mit der Anzahl der Zitierungen eines Artikels i das Array [i-1] füllen. hier Array[0]=1, Array[2]=2, Array[10]=1, alle anderen Array[i]=0
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von te one: 28.10.2015 20:07.
|
|
|
28.10.2015 19:44 |
|
|
|
|
Für 4 Zahlen reicht ein Array mit 4 Einträgen: [10, 3, 3, 1].
Jetzt gehst du von vorne aus durch: ist der Index des Felds (bei 1 beginnend) < seinem Inhalt? Dann bist du fertig (Ergebnis = aktueller Index-1), ansonsten gehst du weiter im Array.
__________________
Syntax Highlighting fürs Board (Link)
|
|
|
29.10.2015 06:10 |
|
|
te one
Grünschnabel
Dabei seit: 22.10.2015
Beiträge: 6
|
|
Danke, hat soweit geklappt.
Leider musste ich bei der Implementierung ein Problem feststellen:
Die Eingabe ist ein Array wie z.B.: 1,1,1,2,4,1,5,2,6
D.h. es wurde zuerst Artikel 1 zitiert, dann wieder Art1, dann wieder 1, dann Artikel 2 usw...
Um das in die nötige Form für die spätere h-Index-Ermittlung zu bringen, erstelle ich erst ein Array mit der Länge des größten Elementes des Eingabearrays (hier also Länge 6). Nur so habe ich später sicher genug Felder die ich hochzählen kann.
Und dann Durchlaufe ich das Eingabearray und erhöhe die entsprechende Nr in meinem neuerzeugten Array (Zahl 1 erhöht im Array die Zahl bei index 1-1=0, Zahl 2 in der Eingabe erhöht bei Index 2-1=1...).
Problem: Hier an der Uni wird ein automatisches System zur Prüfung unseres Codes verwendet. Das meldet mir an der Stelle der Definition des neuen Arrays eine Exception java.lang.OutOfMemoryError: Java heap space ....
Denke mal in deren Eingabe ist irgendwo eine riesige Zahl weshalb ich ein riesiges Array erzeuge.
Mir fallen mögliche Lösungen über HashMaps oder so ein, aber das hier ist dritte Woche im ersten Semester - die Profs sind froh, wenn wir mit Arrays klarkommen. Eine einfache Lösung sehe ich nicht.
|
|
|
29.10.2015 15:23 |
|
|
|
|
Es besteht keine Notwendigkeit, ein neues Array zu erzeugen.
Du kannst das vorhandene in-place sortieren (Bibliotheksfunktionen, Bubblesort oder was auch immer).
Dann musst du nur den Arrayindex mit dessen Inhalt vergleichen, da der Index aussagt, wie viele Werke mindestens s oft zitiert wurden.
__________________
Syntax Highlighting fürs Board (Link)
|
|
|
29.10.2015 15:28 |
|
|
|
