N
[keinen plan ob ich hier richtig bin, ich versuchs einfach mal]
Wir hatten heute in ethik (sehr geiles fach, btw ) wieder mal viel spaß... Naja, es lief darauf hinaus, dass jeder irgendwelche persönlichen sachen aufn blatt malen sollte und danach versucht wird, ein blatt dem autor zuzordnen. Wie auch immer, am Ende meinten einige, man hätte gar nicht erkennen können was von wem ist und das wäre nur raterei gewesen. Da ich wie meist in ethik das dringende bedürfnis verspührte, mich anderweitig zu beschäftigen, hatte ich schon ein wenig über die komplexität von solchem zuorden nachgedacht (wohlgemerkt zuordnungen ohne anhaltspunkte), und ich habe das gefühl, dass wir viel zu schnell waren (18 personen, 3 "runden"), als dass wir ohne anhaltspunkte geraten habe könnten. So viel der vorrede.
Ein bischen formaler definiert:
Ich habe n eindeutig identifizierbare gegenstände, die ich n personen zuordnen will. Jeder person gehört genau ein gegenstand. Jeder weiß nur, was sein eigener gegenstand ist. In einer "runde" kann ich beliebig vielen der personen beliebig viele gegenstände in die hand drücken (natürlich können nicht personen den selben gegenstand halten). Am Ende der Runde behalten alle, die (unter anderen) den richtigen gegenstand hielten, diesen i.d. Hand und scheiden aus. Alle anderen gegenstände werden zurückgegeben.
Eine beobachtung ist, dass maximale effizienz nur erreicht werden kann, wenn in jeder Runde alle gegenstände vergeben werden. Außerdem ist eine zuordnung in linearer laufzeit leicht zu finden (wenn ich alle gegenstände einer person gebe ist seiner eindeutig darunter, ich kann also jede runde genau einen gegenstand zuordnen). Die Frage ist aber, geht es auch schneller (und wenn ja, wie schnell)? Dazu habe ich mir volgendes überlegt:
(M im folgenden die Menge der Personen, G die Menge der Gegenstände,mx ist eine person, gx ein gegenstand, n die ursprüngliche anzahl der personen. Ich gehe außerdem davon aus, dass jedes Element aus M einen Vorgänger hat)
Im ersten Schritt ordne ich jedem element aus M ein Element aus G zu. mx hat nun mit der wahrscheinlichkeit 1/n den richtigen gegenstand in der Hand. Bei n personen ordne ich also durchschnittlich einen gegenstand zu. In der nächsten runde wird jedem element aus M das Element aus G zugeordnet, das vorher der Vorgänger hielt. Die wahrscheinlichkeit, dass mx den richtigen gegenstand hält, ist 1/(n-2) (mx hat n-1 elemente aus G noch nicht gehabt, und ein gx ist schon raus). Das heißt, dass in dieser runde durchschnittlich (n-1)/(n-2) gegenstände zugeordnet werden.
Es sieht also so aus, als ob das schneller als O(n) wird, ich bin mir aber nicht sicher, weil hier haperts. Überhaupt bin ich mir nicht sicher, ob ich bis hier recht habe :). Was wenn der ausgeschiedene und bereits gehaltene gegenstand zusammenfallen? Und was, wenn das verfahren wirklich schneller ist (irgendwie hab ich das gefühl, das ist nicht der fall), wo liegt obere schranke?