Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Glichverteilung beim Quicksort Algorithmus
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Informatik-Forum -> Glichverteilung beim Quicksort Algorithmus
 
Autor Nachricht
Klam187
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 26.04.2018
Beiträge: 2

BeitragVerfasst am: 14 Mai 2018 - 14:24:10    Titel: Glichverteilung beim Quicksort Algorithmus

Hi,

ich habe einen Beweis zu erbringen, der sich mit dem Quicksort Algorithmus befasst.

Sei n die Länge des Feldes und k der Rang unseres Pivotelements.

Zu zeigen ist die Behauptung, dass die entstandenen Teilfelder mit einer Wahrscheinlichkeit von 1/(k-1)! bzw. 1/(n-k)! gleichverteilt sind.

Mein Ansatz wäre jetzt, zu zeigen, dass ich durch die Addition der Wahrscheinlichkeiten der drei Teilfelder (inks, pivot, rechts) auf 1 komme und damit die Gleichverteilung beweise.

Leider komme ich da nicht richtig raus. Ist der Ansatz richtig und hat evtl. jemand eine Idee für einen möglichen Lösungsweg.

LG,
Nico
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Informatik-Forum -> Glichverteilung beim Quicksort Algorithmus
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum