Einstellung einer Person aus N - Rang und Wahrscheinlichkeit

Question

Ich studiere Algorithmen aus CLRS -Buch. Ich versuche den Unterschied zwischen zu verstehen

• Wahrscheinlichkeit, die Person $ i $ th aus $ n $ und einzustellen und
• Wahrscheinlichkeit, die Person von $ i $ th von $ n $ personen zu mieten, basierend auf Rängen.

Mit der normalen Wahrscheinlichkeit wissen wir, dass die Antwort für die erste $ frac {1} {ni} $ ist und die Antwort für das zweite als $ frac {1} {i} $ im CLRS -Buch angegeben wird. Ich kann das Konzept hier nicht verstehen. Wie ist es $ frac {1} {i} $? Kann es auch $ frac {1} {ni} $ in Rängen aufnehmen?

Wir haben N -Kandidaten für eine Einstellung. Wenn ein Kandidat befragt wird

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

Wenn Menschen nach einem interviewt werden zufällig Ankunftsreihenfolge, die Wahrscheinlichkeit, dass der Kandidat $ i $ eingestellt wird, ist $ frac {1} {i} $. Dies ergibt sich aus der Tatsache, dass die Gruppe der anfänglichen $ i $ -Kandidaten für jede $ i $ -Kandidaten zufällig ist, so dass der Kandidat $ $ $ frac {1} {i} für jede $ i $ ist, so $ of to the gewählt zu werden, was passiert, wenn er/sie besser qualifiziert ist als die vorherigen Kandidaten von $ I-1 $.

Jetzt, anstatt eine zufällige Reihenfolge für die Ankünfte zu berücksichtigen, Sagen Sie Ihre eigene Bestellung auf, Basierend auf Rängen: Der erste Kandidat ist der weniger qualifizierte, und der letzte ist derjenige, der insgesamt am besten ist. In diesem Fall, wenn die Gruppe aus $ N $ -Kandidaten hergestellt wird und sie von 0 $ bis $ N-1 $ nummeriert, erhalten Sie für den $ i $ th Kandidaten eine Wahrscheinlichkeit, eingestellt zu werden, was $ frac {1} {ni ist } $, da die Kandidaten jetzt auf der Grundlage ihrer Reihen eintreffen und der Kandidat $ i $ immer besser qualifiziert ist als die vorherigen $ I-1 $.

Aus diesem Grund möchten Sie die Gruppe der Kandidaten durchdringen: so dass kein bestimmter Input das schlechteste Fallverhalten ausgelöst wird, das der Permutation verbunden ist, in der Kandidaten nach Rang sortiert werden.

CLRS erklärt, wie diese kleinen Änderungen Sie im Durchschnitt $ O ( lg n) $ Kandidaten anstelle von $ n $ im schlimmsten Fall einstellen können. Beachten Sie, dass dies nur eine probabilistische Garantie ist: Nichts verhindert den Pseudorandomgenerator, wenn Sie wirklich unglücklich sind, indem Sie die Permutation erzeugen, die den Kandidaten entspricht, die nach Rang sortiert sind. Wir erwarten jedoch nicht, dass dies häufig geschieht: Die Wahrscheinlichkeit, die schlechte Permutation zu generieren, beträgt nur $ frac {1} {n!} $, Was für große $ n $ sehr niedrig ist.