Megnéztem az MIT előadását a Skip List témáról. Összességében értem az anyagot, de egyet. Mi az a “nagy valószínűséggel”? Igazából egyáltalán nem értem. Láttam a előadás jegyzeteket , de még mindig nem értem.
Csak azt mondta: “Az $ E $ esemény nagy valószínűséggel fordul elő (whp), ha bármely $ \ alpha \ geq1 $ esetében megfelelő választás van olyan állandókról, amelyeknél az $ E $ legalább $ 1 – O (1 / n ^ valószínűséggel) előfordul. \ alpha) $ “.
Valami a (z) algorithmist.com oldalról sem segített.
$ \ alpha $ és mi az a $ 1 – O (1 / n ^ \ alpha) $? Ha nem értem ezt a dolgot, megzavarodom annak elemzésében, hogy “Nagy valószínűséggel minden keresés egy $ n $ -elem ugrási listában $ O (\ lg n) $ -ba kerül”.
Megjegyzések
- Ne feledje, hogy a randomizált és valószínűségi algoritmusok nem azonosak .
Válasz
Egy esemény nagy valószínűséggel történik egy $ n $ paraméterhez képest, ha $ p_n $ valószínűséggel történik és $ \ lim_ {n \ to \ infty} p_n = 1 $. A $ n $ paraméter általában egyértelmű a kontextusból. Ebben az esetben például valószínűleg a listában szereplő elemek száma.
Az “előadás jegyzetében” a “nagy valószínűséggel” definíció még konkrétabb, meghatározva, hogy a $ p_n $ milyen gyorsan konvergáljon $ 1 $ -ig: egy esemény nagy valószínűséggel történik, ha valamilyen $ C esetén $ p_n \ geq C / n ^ \ alpha $ valószínűséggel, \ alpha > 0 $. Például, ha véletlenszerű számot választ $ $ {0, \ ldots, n \} $ közül, akkor nagy valószínűséggel nem nulla, mivel annak valószínűsége, hogy nem nulla, $ 1-1 / (n + 1) \ geq 1-1 / n $ (tehát ebben az esetben $ C = \ alpha = 1 $).
Megjegyzések
- A korlát kritérium: más néven " szinte biztosan ". Láttam " nagy valószínűségű " t használni, amikor az exponenciális sebességgel közelítő valószínűségekre utalok.
- Amikor én lásd " whp " általában szinonimája a " szinte biztosan ", és amikor használom (anélkül, hogy definiálnám), mindig erre az értelemre hivatkozom. De általánosabban " whp " jelentheti az 1 megközelítését, az 1 polinomiálisan gyors megközelítését vagy az 1 exponenciális gyorsulását. Ha az utóbbi értelemben használja, feltétlenül határozza meg kifejezetten.
- Tényleg, ' hívja a $ p_n = 1 – \ frac { 1} {\ log ^ * n} $ " nagy valószínűséggel "? 😉 De igen: a biztonság érdekében mindenképpen határozza meg, mit jelent a kontextusában.
- Mi az a szabványos referencia (pl. Tankönyvek), amely formálisan meghatározza a WHP-t? Megpróbáltam cikket írni a WHP-ről a wikipédiában hu.wikipedia.org/wiki/With_high_probability , de törlésre javasolták, mivel nincsenek források, ezért vagyok forrásokat keres ..
- Ellenőrizheti a standard bonyolultságot és algoritmusokat tartalmazó tankönyveket. De ha talál is referenciát, az ' csak a kifejezés adott tagkönyvét használja. ' Valószínűleg ' az a legjobb, ha csak kifejezetten közös definícióként definiálja, különösebb " igazolás nélkül ".