Betrag der erwarteten Schleifen-Iterationen beim Durchsuchen eines Arrays durch den zufälligen Index

Question

lassen Sie sagen, wir haben ein Array A der Größe n.Es hat 1 als erster Index und n als letzter Index.Es enthält einen Wert x, mit x auftretenden k-mal in einem, wobei 1 <= k <= n

Wenn wir einen Suchalgorithmus wie so haben:

generasacodicetagpre.

zufällig (a, b) wählt eine Zahl einheitlich von A bis B

Daraus wissen wir, dass die Chancen, X zu finden und das Programm zu beenden, mit jeder Iteration k / n ist.Was ich jedoch wissen möchte, ist das, was der erwartete Wert für die Anzahl der Iterationen wäre, oder in Bezug auf die Menge an Zeiten, auf die das Array in diesem Programm in diesem Programm aufgerufen wurde, wie oben beschrieben, wie oben beschrieben.

Answer 1

lass $ n $ Sei der geometrische R.V. Das gibt an, wie oft das Array zugegriffen wurde, um nach dem Element, $ A [x] $ zu suchen, bis wir es erfolgreich finden. Wir möchten wissen, $ \ mathbb {e} [n] $ .

Wir können die Iterationen der While-Schleife als Folge von IID-Bernoulli-Tests ansehen, die jeweils mit einer Wahrscheinlichkeit $ P $ von nachfolgender und $ q= 1 - P $ Versagen. Angesichts der Frage möchten wir wissen, wie viele Versuche benötigt werden, um einen "Erfolg" erhalten, der das Element $ A [x] $ somit erfinden würde, somit die generationstabelles terminiert .

seit der $ \ PR \ {n= k \}= q ^ {k-1} p $ , haben wir diese $ \ mathbb {E} [n]=sum \ limits_ {k= 1} ^ \ Infty K \: q ^ {k-1} P $ .

somit $ \ mathbb {e} [n]=dfrac 1p $ wo $ p=dFRAc kN $ SO $ \ MathBB {E} [N]=DFRAC NK $ .

Im Durchschnitt dauert es im Durchschnitt Zugriffe von $ \ DFRAC NK $ , bevor das Element gefunden wird, $ A [x] $ .