import numpy.random as random
def random_array(n=10, M=10):
return random.randint(1, high=M, size=n)
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
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))
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))
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)
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).
On va calculer les premiers nombres de Catalan, en utilisant la mémoïsation pour rendre efficace le calcul récursif simple.
from functools import lru_cache
@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))
for i in range(20):
print(f"Catalan({i}) = {catalan(i)}")
@lru_cache(maxsize=None)
def factorial(n):
if n <= 1:
return 1
else:
return n * factorial(n - 1)
def catalan_explicit(n):
return int(factorial(2 * n) / ((factorial(n+1)) * (factorial(n))))
for i in range(30):
print(f"Catalan({i}) = {catalan(i)} = {catalan_explicit(i)}")
Ca suffit pour aujourd'hui !