Assumere una persona su n - rango e probabilità

Question

sto studiando gli algoritmi da CLRS libro. Cerco di capire la differenza tra

• probabilità di assunzione del $ i $ esimo persona su $ n $ e
• probabilità di assunzione del $ i $ esimo persona su $ n $ persone basati su file.

Uso della probabilità normale, sappiamo che la risposta per il primo è $ \ frac {1} {ni} $ ed è dato la risposta per la seconda da $ \ frac {1} {i} $ nel libro CLRS . Non riesco a capire il concetto qui. Come è $ \ frac {1} {i} $? Può anche essere $ \ frac {1} {n-i} $ presa in ranghi, anche tu?

Abbiamo n candidati in fila per un intertiew.Once un candidato viene intervistato gli viene dato un rank.If il rango del prossimo candidato è maggiore è la corrente più grande rango viene assunto e il suo rango è ora l'attuale grande rango

HireAssistant(n)
   best=0
   for i=1 to n
       interview candidate i
       if candidate i better than candidate best
          best=i
          hire candidate i

Answer 1

Quando le persone vengono intervistati a seguito di una casuale ordine di arrivo, la probabilità di candidato $ i $ di essere assunto è di $ \ frac {1} {i} $. Ciò deriva dal fatto che, ipotizzando un ordine casuale di arrivi, per ogni $ i $ il gruppo di $ iniziale ho $ candidati è casuale, in modo che il $ i $ -esimo candidato ha probabilità $ \ frac {1} {i} $ di essere scelti, che succede se lui / lei è più qualificato rispetto al precedente $ I-1 $ candidati.

Ora, invece di considerare un ordine casuale sulle arrivi, imporre il proprio ordine , in base alla classifica: il primo candidato è il meno qualificati, e l'ultimo è quello che è il migliore in assoluto . In questo caso, se il gruppo è fatto di $ n $ candidati, numerandoli da $ 0 $ a $ n-1 $ si ottiene per il $ i $ esimo candidato una probabilità di essere assunto, che è $ \ frac {1} {ni } $, dal momento che i candidati ora stanno arrivando sulla base dei loro ranghi, e il $ i $ -esimo candidato è sempre più qualificato rispetto al precedente $ i-1 $.

Questo è il motivo per cui si vuole permutare il gruppo di candidati:. In modo che nessun ingresso particolare suscita il comportamento peggiore dei casi associato alla permutazione in cui i candidati sono ordinati per rango

CLRS spiega come questo piccole modifiche consente di assumere, in media, $ O (\ lg n) $ candidati al posto di $ n $ nel caso peggiore. Si noti che questa è solo una garanzia probabilistica: nulla impedisce il generatore pseudocasuale, se si è davvero sfortunato, di generare la permutazione corrispondente ai candidati allineati secondo rango. Ma non ci aspettiamo che questo accada di frequente: la probabilità di generare la cattiva permutazione è di soli $ \ frac {1} {! N} $, che, per grandi $ n $, è molto bassa

.