Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutSign UpSign In
| Download
Project: Public Code
Views: 852
1


2
def double(T):

3
    c = 0

4
    for i in xrange(1,len(T)):

5
        for j in xrange(i):

6
            c+=1

7
            if T[i] == T[j]:

8
                return c

9
    return c

10


11
def worst_case(n):

12
    L = range(n)

13
    return double(L)

14


15
def average(n,k,r):

16
    c = 0

17
    for i in xrange(r):

18
        L = [randint(1,k) for j in xrange(n)]

19
        c+= double(L)

20
    return int(c/r)

21


22
def esperance(n,k):

23
    p = lambda i: factorial(i-1) * binomial(k,i-1)*(i-1)/k**i

24
    return float(sum([p(i)*i for i in xrange(1,n+1)]) + binomial(k,n)*factorial(n)*(n+1)/k**n)

25


26
def complexity(n,k):

27
    p = lambda i: float(factorial(i-1) * binomial(k,i-1)*(i-1))/float(k**i)

28
    return float(sum([p(i)*i**2/2 for i in xrange(1,n+1)]) + float(binomial(k,n)*factorial(n)*n**2/2)/float(k**n))

29


30