Complexité moyenne sur des listes ou des tableaux

In [19]:
import numpy.random as random
In [20]:
def random_array(n=10, M=10):
    return random.randint(1, high=M, size=n)
In [35]:
def naive_linear_search(array, x):
    found = False
    i = -1
    while not found:
        i += 1
        if i >= len(array):
            return -1
        if array[i] == x:
            found = True
    return i if found else -1
In [43]:
print("Pour une valeur x aléatoire dans [1,M], la liste L fixée :")
for n in [100, 1000, 10000, 100000]:
    for M in [20, 200, 2000, 20000]:
        L = random_array(n=n, M=M)
        print(f"  Pour n = {n} et M = {M}... ", end='')
        %timeit naive_linear_search(L, random.randint(M))
Pour une valeur x aléatoire dans [1,M], la liste L fixée :
  Pour n = 100 et M = 20... 16.3 µs ± 1.15 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)
  Pour n = 100 et M = 200... 38 µs ± 3.04 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
  Pour n = 100 et M = 2000... 49 µs ± 4.22 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
  Pour n = 100 et M = 20000... 54.9 µs ± 9.28 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
  Pour n = 1000 et M = 20... 34 µs ± 2.33 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
  Pour n = 1000 et M = 200... 90.5 µs ± 10.4 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
  Pour n = 1000 et M = 2000... 420 µs ± 82.9 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
  Pour n = 1000 et M = 20000... 488 µs ± 40.7 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
  Pour n = 10000 et M = 20... 290 µs ± 76.7 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
  Pour n = 10000 et M = 200... 118 µs ± 9.34 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
  Pour n = 10000 et M = 2000... 901 µs ± 40.7 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
  Pour n = 10000 et M = 20000... 3.49 ms ± 179 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
  Pour n = 100000 et M = 20... The slowest run took 4.94 times longer than the fastest. This could mean that an intermediate result is being cached.
2.47 ms ± 1.35 ms per loop (mean ± std. dev. of 7 runs, 100 loops each)
  Pour n = 100000 et M = 200... 298 µs ± 92.9 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
  Pour n = 100000 et M = 2000... 807 µs ± 35.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
  Pour n = 100000 et M = 20000... 8.76 ms ± 605 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
In [44]:
print("Pour une valeur x aléatoire dans L, la liste L fixée :")
for n in [100, 1000, 10000, 100000]:
    for M in [20, 200, 2000, 20000]:
        L = random_array(n=n, M=M)
        print(f"  Pour n = {n} et M = {M}... ", end='')
        %timeit naive_linear_search(L, random.choice(L))
Pour une valeur x aléatoire dans L, la liste L fixée :
  Pour n = 100 et M = 20... 11.9 µs ± 717 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
  Pour n = 100 et M = 200... 18 µs ± 918 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
  Pour n = 100 et M = 2000... 20.8 µs ± 2.08 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)
  Pour n = 100 et M = 20000... 18.7 µs ± 223 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
  Pour n = 1000 et M = 20... 11.9 µs ± 191 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
  Pour n = 1000 et M = 200... 50.4 µs ± 5.44 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
  Pour n = 1000 et M = 2000... 112 µs ± 3.83 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
  Pour n = 1000 et M = 20000... 136 µs ± 19.4 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
  Pour n = 10000 et M = 20... 11.3 µs ± 270 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
  Pour n = 10000 et M = 200... 53.9 µs ± 2.98 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
  Pour n = 10000 et M = 2000... 391 µs ± 14.9 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
  Pour n = 10000 et M = 20000... 1.05 ms ± 11.9 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
  Pour n = 100000 et M = 20... 11.6 µs ± 145 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
  Pour n = 100000 et M = 200... 55.7 µs ± 320 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
  Pour n = 100000 et M = 2000... 505 µs ± 25 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
  Pour n = 100000 et M = 20000... 4.03 ms ± 281 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
In [45]:
print("Pour une valeur x fixée, et une L aléatoire :")
for n in [100, 1000, 10000, 100000]:
    for M in [20, 200, 2000, 20000]:
        x = random.randint(M)
        print(f"  Pour n = {n} et M = {M}... ", end='')
        %timeit naive_linear_search(random_array(n=n, M=M), x)
Pour une valeur x fixée, et une L aléatoire :
  Pour n = 100 et M = 20... 24.3 µs ± 1.38 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
  Pour n = 100 et M = 200... 45.1 µs ± 1.87 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
  Pour n = 100 et M = 2000... 56.1 µs ± 6.74 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
  Pour n = 100 et M = 20000... 60.3 µs ± 4.43 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
  Pour n = 1000 et M = 20... 42.1 µs ± 3.85 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
  Pour n = 1000 et M = 200... 107 µs ± 4.58 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
  Pour n = 1000 et M = 2000... 406 µs ± 60.3 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
  Pour n = 1000 et M = 20000... 496 µs ± 38.7 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
  Pour n = 10000 et M = 20... 191 µs ± 13.6 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
  Pour n = 10000 et M = 200... 200 µs ± 29.4 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
  Pour n = 10000 et M = 2000... 1.49 ms ± 254 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
  Pour n = 10000 et M = 20000... 3.67 ms ± 417 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
  Pour n = 100000 et M = 20... 1.62 ms ± 64.7 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
  Pour n = 100000 et M = 200... 984 µs ± 69 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
  Pour n = 100000 et M = 2000... 1.36 ms ± 73.4 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
  Pour n = 100000 et M = 20000... 10.1 ms ± 1.04 ms per loop (mean ± std. dev. of 7 runs, 100 loops each)

On observe les comportements prouvés en TD : l'opération de recherche a une complexité moyenne linéaire en $\mathcal{O}(n)$ dans chacune de ces situations (à $M$ fixé et $n$ variable).

Nombre de catalans

On va calculer les premiers nombres de Catalan, en utilisant la mémoïsation pour rendre efficace le calcul récursif simple.

In [3]:
from functools import lru_cache
In [4]:
@lru_cache(maxsize=None)
def catalan(n):
    if n <= 3:
        return {0: 1, 1: 1, 2: 2, 3: 5}[n]
    return sum(catalan(i) * catalan(n - 1 - i) for i in range(0, n))
In [5]:
for i in range(20):
    print(f"Catalan({i}) = {catalan(i)}")
Catalan(0) = 1
Catalan(1) = 1
Catalan(2) = 2
Catalan(3) = 5
Catalan(4) = 14
Catalan(5) = 42
Catalan(6) = 132
Catalan(7) = 429
Catalan(8) = 1430
Catalan(9) = 4862
Catalan(10) = 16796
Catalan(11) = 58786
Catalan(12) = 208012
Catalan(13) = 742900
Catalan(14) = 2674440
Catalan(15) = 9694845
Catalan(16) = 35357670
Catalan(17) = 129644790
Catalan(18) = 477638700
Catalan(19) = 1767263190
In [11]:
@lru_cache(maxsize=None)
def factorial(n):
    if n <= 1:
        return 1
    else:
        return n * factorial(n - 1)
In [14]:
def catalan_explicit(n):
    return int(factorial(2 * n) / ((factorial(n+1)) * (factorial(n))))
In [17]:
for i in range(30):
    print(f"Catalan({i}) = {catalan(i)} = {catalan_explicit(i)}")
Catalan(0) = 1 = 1
Catalan(1) = 1 = 1
Catalan(2) = 2 = 2
Catalan(3) = 5 = 5
Catalan(4) = 14 = 14
Catalan(5) = 42 = 42
Catalan(6) = 132 = 132
Catalan(7) = 429 = 429
Catalan(8) = 1430 = 1430
Catalan(9) = 4862 = 4862
Catalan(10) = 16796 = 16796
Catalan(11) = 58786 = 58786
Catalan(12) = 208012 = 208012
Catalan(13) = 742900 = 742900
Catalan(14) = 2674440 = 2674439
Catalan(15) = 9694845 = 9694844
Catalan(16) = 35357670 = 35357670
Catalan(17) = 129644790 = 129644790
Catalan(18) = 477638700 = 477638700
Catalan(19) = 1767263190 = 1767263189
Catalan(20) = 6564120420 = 6564120419
Catalan(21) = 24466267020 = 24466267020
Catalan(22) = 91482563640 = 91482563639
Catalan(23) = 343059613650 = 343059613650
Catalan(24) = 1289904147324 = 1289904147324
Catalan(25) = 4861946401452 = 4861946401451
Catalan(26) = 18367353072152 = 18367353072152
Catalan(27) = 69533550916004 = 69533550916004
Catalan(28) = 263747951750360 = 263747951750360
Catalan(29) = 1002242216651368 = 1002242216651368

Ca suffit pour aujourd'hui !