[Algorytmy] Złożoność średnia

midek · Post autor: **midek** » 16 lut 2013, o 16:54

WYSZ_SEKW(A[1..n],x)
i <-- 1
A[n+1] <-- x
while A[i] <> x
do i <-- i+1
if i <= n
   then return i
   else return 0

Przyjmijmy, że operacjami dominującymi są oba porównania w linijkach 4 i 6.

Mam obliczyć złożoność średnią. Zrobiłem tak:

\(\displaystyle{ \sum_{k=1}^{n}2k \cdot \frac{p}{n} + (n+2)(1-p) = \frac{p}{n} \cdot n(n+1) + (n+2)(1-p) = n+2-p}\)

\(\displaystyle{ p}\) - oznacza prawdopodobieństwo

Jest dobrze?