[Teoria złożności] Obliczenie oczekiwanej złożoności

[leihto]

Jak oblicza się oczekiwaną złożoność algorytmu? Zadanie na egzaminie brzmiało mniej więcej tak:
Jaka będzie pesymistyczna i oczekiwana złożoność algorytmu, który dla każdej z \(\displaystyle{ N}\) wprowadzonych liczb wykonuje:
a) \(\displaystyle{ N^9}\) operacji, jeśli pierwsza liczba jest podzielna przez \(\displaystyle{ N^2}\);
b) \(\displaystyle{ N^3}\) operacji, jeśli pierwsza liczba nie jest podzielna przez \(\displaystyle{ N^2}\)

Złożoność pesymistyczna była prosta do wyliczenia, bo \(\displaystyle{ n^9}\), natomiast oczekiwana przyniosła mi dużo problemów. Profesor w swoich wywodach po egzaminie wyliczył że będzie to \(\displaystyle{ n^5}\), lecz ja tego za nic nie mogłem zrozumieć, skąd.. Jest ktoś kto jest w stanie to mniej więcej wytłumaczyć?
Pozdrawiam

[liu]

Tutaj jest taki problem techniczny, że zbiory danych wejściowych są nieskończone, do tego nie istnieje rozsądny rozkład prawdopodobieństwa na całym \(\displaystyle{ \mathbb{N}}\).

Ale jestem ciekaw, jak profesorowi wyszło \(\displaystyle{ O(N^5)}\), bo tak na oko to: ułamek liczb naturalnych podzielnych przez \(\displaystyle{ N^2}\) w skończonym (i dostatecznie dużym) zbiorze \(\displaystyle{ \{1, 2, \ldots, m\}}\)) to coś koło \(\displaystyle{ \frac{1}{N^2}}\), zatem niepodzielnych jest \(\displaystyle{ 1 - \frac{1}{N^2}}\), czyli średnia liczba operacji to:
\(\displaystyle{ \frac{1}{N^2}N^9 + \left(1 - \frac{1}{N^2}\right)N^3 = N^7 + N^3 - N = \Theta(N^7)}\).