Nutzung parametrischer Chernoff-Grenzen für vereinfachte Algorithmusanalyse

In diesem Papier leiten wir parametrische Chernoff-Grenzen ab und zeigen deren Anwendung zur Vereinfachung der Analyse einiger bekannter probabilistischer Algorithmen und Datenstrukturen. Die von uns bereitgestellten parametrischen Chernoff-Grenzen bieten Wahrscheinlichkeitsgrenzen, die Potenzen von zwei sind, mit einer klaren Formulierung der Beziehung zwischen der Konstante im Exponenten und der relativen Entfernung vom Mittelwert. Darüber hinaus bieten wir neue vereinfachte Analysen mit diesen Grenzen für Hashtabellen, randomisierte Routings und eine vereinfachte, nicht-rekursive Anpassung des Floyd-Rivest-Auswahlalgorithmus an.