Durchschnittliche Anzahl der Inspektionen

Question

Betrachten Sie einen Satz von N-Elementen, deren Schlüsselwerte $$ 0, 1, ..., N-1-$$ $ p (i) (0 ≤ i ≤ n-1) $ Seien Sie die Wahrscheinlichkeit, dass das Element mit dem Schlüssel i gesucht wird. Angenommen, die folgende Verteilung von $ P (i) 's $ :

$$ p (i)= \ begin {cases} 1/2 ^ {n-1}, & \ Text {if i= 0} \\ 1/2 ^ i, & \ text {sonst} \ ENDE {Hüllen} $$

Nehmen Sie an, dass die lineare Suche verwendet wird, und jede Suche ist erfolgreich - jedes Element, das wir nach existieren sollen.

Wie hoch ist die durchschnittliche Anzahl von Knoten, die für eine Suche unter Zufall übereinstimmen (Elemente in der verknüpften Liste werden in einer zufälligen Reihenfolge gespeichert) Organisation und was ist die durchschnittliche Anzahl der Knoten, wenn sie auf der Grundlage ihrer abnehmenden Wahrscheinlichkeit sortiert werden (dh es beginnt) mit dem Element '1', gefolgt von Element '2', dann '3' usw. mit dem letzten Knoten, der Element '0' enthält.) Für große Werte von n?

Ich weiß, dass die Antwort für den ersten Teil sicherlich nicht $ n / 2 $ ist (da die Wahrscheinlichkeit nicht für alle Elemente gleich ist), aber ich tue Ich weiß nicht wirklich viel mehr als das ... aber wenn Sie sortiert sind, vermute ich, dass es etwas in der Nähe von $$ \ Sum_ {I= 1} ^ {n-1} i * { 1/2 ^ {i}} + N * 1/2 ^ {n-1} $$ Weil es einen Vergleich braucht, um zum ersten Element zu gelangen, zwei bis zum zweiten, usw. und der letzte nimmt n Vergleiche Zeiten der Wahrscheinlichkeit von 0. Ich fand auch den $$ \ sum_ {i= o} ^ {∞} a * b ^ a= b / (1-b) ^ 2 $ $ das in diesem Fall gleich 2 (B= 1/2) wäre, aber ich habe keine Ahnung, wie man den Randgehäuse angibt - '0'. : (

Ich bin auch bewusst von dieses Thread Aber dort hatte jede der Zahlen die gleiche Wahrscheinlichkeit und nicht genau das Gleiche.

Ich hoffe, dass ich eine Antwort darauf finden kann, da es mich schon eine Weile stört, und ich bin wirklich neugierig auf das Ergebnis.
Jeder Hinweis wird sehr geschätzt!

Answer 1

Nun, mal sehen. Bitte weisen Sie darauf hin, ob ich das Problemmodell falsch verstanden habe.

Angenommen, wir haben $ n= 5 $ Elemente. Angenommen, es ist im Wege sortiert $ s= [1, 3, 4, 0, 2] $ . Mit der linearen Suche werden wir mit der Wahrscheinlichkeit $ (1/2) ^ 3 $ 2 Schritte in unserer Suche und mit der Wahrscheinlichkeit $ (1/2) ^ 4 $ 4 Schritte in unserer Suche haben.

Also, wie ist die durchschnittliche Anzahl von Schritten, die wir benötigen, um ein Element zu finden, das eine beliebige Sortierung $ s $ gibt? Lassen Sie uns sagen $ x $ - Anzahl der in unserer Suche erforderlichen Schritte. Die Wahrscheinlichkeit, $ X= I $ Schritte zu erhalten ist, um eine Suche nach einem Element $ k \ in \ {0 anzufordern, 1,2, .., N-1 \} $ Geben, dass wir es in der $ I $ die Position haben. Das ist $$ P (x= i)=sum_ {k= 0} ^ {n-1} p (Suche \ für \ k \ | \ das \ element \ k \ ist \ \ \ ith \ position) p (das \ element \ k \ ist \ \ \ \ \ position) $$ dann merken wir, dass $ p (das \ element \ k \ ist \ \ \ ith \ position)=frac {(n-1)!} {n!}=frac {1} {n} $ , da wir ein Element in einer festen Position haben und $ (n-1)! $ Mögliche Permutationen für andere Elemente aus dem Gesamtbetrag $ N! $ möglich Permutationen unserer $ N $ Elemente. Dann bemerken wir, dass $ \ sum_ {k= 0} ^ {n-1} p (Suchen \ für \ k \ | \ das \ element \ k \ ist \ \ ith \ Position)= 1 $ . Es bedeutet, dass $ P (x= i)=frac {1} {n} $ . So ist die Erwartung nur $ \ sum_ {k= 1} ^ {n} \ frac {k} {n}=frac {n + 1} {2} $ .

Natürlich ist der zweite Teil viel einfacher zu leichter, es ist nur $$ E (x | sortiert \ in \ abnehmend \ Wahrscheinlichkeit)=sum_ {k= 1} ^ {n-1} \ frac {k} {2 ^ {k}} + \ frac {n} {2 ^ {n-1}} $$ (Beachten Sie einfach, dass die Elemente von < Span-Klasse="Math-Container"> $ 1 $ bis $ n-1 $ und dann das Element $ 0 $ , jedoch $ 0 $ könnte das vorletzte Element sein, da es eine gleiche Wahrscheinlichkeit hat, wie $ N-1 $ ). Also berechnen wir jedoch nur die Erwartung der Wahrscheinlichkeitsverteilung, obwohl diesmal jedoch nicht für die gemeinsame Wahrscheinlichkeit, aber bedingt.