Ähnlichkeit von Listen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Eine Gruppe von Freunden redet darüber welche Kinofilme
gut sind, und welche nicht so gut. Dabei stellen die Freunde fest, dass sich einige von ihnen mehr im Geschmack gleichen als andere. Da alle der Freunde Informatiker
sind, wollen sie diese Ähnlichkeit nun genauer bestimmen.
Jeder von ihnen stellt eine Liste aller n diskutierten Filme auf, sortiert vom besten zum schlechtesten. Der Ähnlichkeitswert zweier Freunde ergibt sich jetzt als die Anzahl der Paare von Filmen, die in den Listen der beiden Freunde in der gleichen Ordnung vorkommen. Zwei Freunde mit den genau gleichen Vorlieben haben also einen Ähnlichkeitswert von [mm] \vektor{n \\ 2}
[/mm]
, zwei mit genau gegensätzlichen Vorlieben einen von 0. Wie können die Freunde nun Ähnlichkeitswerte aus den Listen in Zeit O(n log n) berechnen? Formalisiere das Problem und entwickle einen Algorithmus. |
Die Schwierigkeit liegt nun eben vor allem in der Zeitvorgabe von n log (n). Ich kann also nicht alle Paare bilden und dann abzugleichen, weil das viel zu aufwändig wäre. Die einzige Idee die mir einfällt ist es, die Position jedes Filmes in den beiden Listen zu suchen und aus diesen beiden Positionen irgendwas über die Anzahl der passenden Paare abzuleiten. So richtig hilft mir das aber auch nicht weiter.
Irgendwelche Ideen oder Hinweise?
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt: http://www.matheplanet.com/matheplanet/nuke/html/viewtopic.php?topic=204473
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:21 Fr 13.02.2015 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
