Katselin MIT: n luentoa ohitusluettelosta. Kaiken kaikkiaan ymmärrän materiaalin, mutta yhden asian. Mikä on ”erittäin todennäköinen”? En todellakaan saa sitä lainkaan. Olen nähnyt luentomerkinnät , mutta en silti saanut sitä.
He vain sanoi: ”Tapahtuma $ E $ esiintyy suurella todennäköisyydellä (whp), jos jollekin $ \ alpha \ geq1 $: lle on sopiva valinta vakioista, joille $ E $ esiintyy todennäköisyydellä vähintään $ 1 – O (1 / n ^ \ alpha) $ ”.
Jotakin osoitteesta algorithmist.com ei myöskään auttanut.
Mikä on $ \ alpha $ ja mikä on $ 1 – O (1 / n ^ \ alpha) $? Jos en ymmärrä tätä asiaa, sekaannaan analyysiin siitä, miksi ”Suurella todennäköisyydellä jokainen haku $ n $ -elementin ohitusluettelossa maksaa $ O (\ lg n) $”.
Kommentit
- Huomaa, että satunnaistetut ja todennäköisyysalgoritmit eivät ole sama asia .
vastaus
Tapahtuma tapahtuu suurella todennäköisyydellä parametrin $ n $ suhteen, jos se tapahtuu todennäköisyydellä $ p_n $ ja $ \ lim_ {n \ – \ infty} p_n = 1 $. Yleensä parametri $ n $ on selkeä kontekstista. Esimerkiksi tässä tapauksessa se on luultavasti elementtien lukumäärä luettelossa.
Luennon muistiinpanojen määritelmä ”suurella todennäköisyydellä” on vielä täsmällisempi ja täsmentää, kuinka nopeasti $ p_n $: n tulisi lähentyä $ 1 $: tapahtuma tapahtuu suurella todennäköisyydellä, jos se tapahtuu todennäköisyydellä $ p_n \ geq C / n ^ \ alpha $ joillekin $ C: lle, \ alpha > 0 $. Jos esimerkiksi valitset satunnaisluvun joukosta $ \ {0, \ ldots, n \} $, se ei ole nolla suurella todennäköisyydellä, koska todennäköisyys, että se ei ole nolla, on $ 1-1 / (n + 1) \ geq 1-1 / n $ (eli tässä tapauksessa $ C = \ alpha = 1 $).
Kommentit
- Rajaehto on kutsutaan myös nimellä " melkein varmasti ". Olen nähnyt " suuren todennäköisyyden " käytetyn lähinnä viitattaessa todennäköisyyksiin, jotka lähestyvät eksponentiaalista nopeutta.
- Kun minä katso " whp " se on yleensä synonyymi " melkein varmasti ", ja kun käytän sitä (määrittelemättä sitä), tarkoitan tätä aina. Mutta yleisemmin " whp " voi tarkoittaa joko lähestymistä 1, lähestymistä 1 polynomisesti nopeasti tai lähestymistä 1 eksponentiaalisesti nopeasti. Jos käytät sitä jossakin jälkimmäisessä mielessä, muista määritellä se nimenomaisesti.
- Todellakin, ' soitat $ p_n = 1 – \ frac { 1} {\ log ^ * n} $ " suurella todennäköisyydellä "? 😉 Mutta kyllä: ollaksesi turvallinen, määritä, mitä tarkoitat kontekstissasi joka tapauksessa.
- Mikä on vakioviite (esim. Oppikirjat), joka määrittelee WHP: n virallisesti? Yritin kirjoittaa artikkelia WHP: stä wikipediassa fi.wikipedia.org/wiki/With_high_probability , mutta sitä ehdotettiin poistettavaksi, koska lähteitä ei ole, joten olen etsit lähteitä.
- Voit tarkistaa tavallisen monimutkaisuuden ja algoritmien oppikirjat. Mutta vaikka löydätkin viittauksen, ' käyttää vain kyseistä oppikirjaa ' termin käyttöä. ' on luultavasti parasta määritellä se nimenomaisesti yhteiseksi määritelmäksi ilman mitään erityistä " todistusta ".