Gemiddeldecase

Gemiddeldecase, ook wel average-case genoemd, is in informatica en wiskunde de verwachte prestatie van een algoritme over een verdeling van invoeren. Het contrasteert met worst-case en best-case analyses en probeert aan te geven hoe het algoritme in de praktijk presteert onder aannames over hoe invoeren zich voordoen. De precieze uitkomst hangt af van de gekozen invoerverdeling.

Om de gemiddelde-case te bepalen, wordt de tijd of het verbruik berekend als een verwachte waarde over alle mogelijke invoeren: E[T(n)] = sum p(i) · T_i(n), waarbij p(i) de kans heeft dat invoer i voorkomt en T_i(n) de benodigde tijd geeft voor die invoer. Soms worden aannames zoals onafhankelijkheid en uniforme verdeling gemaakt; in andere gevallen worden empirische verdelingen gebruikt. De uitkomst is sterk afhankelijk van de veronderstelde verdeling en kan onduidelijk zijn wanneer die verdeling onbekend is.

Voorbeelden: bij snelle sorteeralgoritmen heeft Quicksort onder aanneming van willekeurige invoer en pivots gemiddeld Theta(n log n) tijd. Lineaire zoekalgoritmen hebben bij een uniforme verdeling van de positie van het gezochte element een gemiddelde tijd van Theta(n). Binair zoeken in een gesorteerde lijst heeft gemiddeld Theta(log n) voor een uniform gekozen doelelement.

Beperkingen en verwante concepten: gemiddelde analyse kan misleidend zijn als de aannamestatistieken niet overeenkomen met praktijk. Worst-case analyse blijft belangrijk voor garanties en worstcasescenario’s. Smoothed analysis biedt een tussenweg door kleine ruis op invoeren te modeleren en zo realistischere verwachtingen te geven.