Diviser pour régner

Tri fusion

On va vérifier expérimentalement l'ordre de grandeur de la complexité du tri fusion

Après avoir défini les fonctions fusion(L1,L2) et tri_fusion(L), on va mesurer le temps d'exécution de la fonction tri_fusion(L) sur des listes de tailles 1000,100 000 et 1 000 000, dont les éléments sont des entiers 


NB_TERMES = 1000
L = [i for i in range(NB_TERMES)]
random.shuffle(L)
t1 = time()
tri_fusion(L)
t2 = time()
print(t2-t1)

Compléter le tableau suivant

$n$$10^3$$10^5$$10^6$
$T$

Exercice

  1. En admettant que $\ln_2(kn) = \ln_2(k)+\ln_2(n)$

    Justifier que $k \leqslant \dfrac{kn\ln_2(kn)}{n\ln_2(n)} \leqslant 2k$

  2. En déduire que si la taille $n$ de la liste est multipliée par un facteur $k$ alors le temps d'exécution est compris entre $kT(n)$ et $2kT(n)$
  3. Donner un encadrement du temps d'exécution pour une liste de $10^7$ termes

Comparaison Tri fusion Tri insertion

  1. Vérifier que si la taille d'une liste est de l'ordre quelques dizaines, le tri par insertion est plus rapide que le tri fusion
  2. Définir une nouvelle fonction récursive tri_fusion2(L) dont le cas de base est len(L) == 50 pour lequel on exécute le tri par insertion
  3. Comparer les deux fonctions de tri fusion

Quart de tour d'une image carré

On adapte le code vue en cours en tenant compte du repérage des pixels dans une image

Télécharger lena.png une image en couleurs au format png 


from PIL import Image
import time

def translation(im,x,y,t):
    """
    im est une image carré dont le côté est une puissance de 2
    x,y les indices du pixel du coin supérieur gauche de la zone à traiter
    Le repérage est celui habituel pour les images
    t le côté de la zone à traiter un multiple de 2 >= 2
    le carré défini par x,y et x+t,y+t est divisé en 4 carrés HG,HD,BG et BD
    On translate BG -> HG,  HG -> HD, HD -> BD et BD -> BG
    """

    for i in range(t//2):
        for j in range(t//2):
            temp = im.getpixel((x+i,y+j))
            im.putpixel((x+i,y+j),im.getpixel((x+i,y+j+t//2)))
            im.putpixel((x+i,y+j+t//2),im.getpixel((x+i+t//2,y+j+t//2)))
            im.putpixel((x+i+t//2,y+j+t//2),im.getpixel((x+i+t//2,y+j)))
            im.putpixel((x+i+t//2,y+j),temp)
            
def quart_tour(im,x,y,t):

    if t > 1:
        quart_tour(im,x,y,t//2)
        quart_tour(im,x,y+t//2,t//2)
        quart_tour(im,x+t//2,y+t//2,t//2)
        quart_tour(im,x+t//2,y,t//2)
        translation(im,x,y,t)
 
image = Image.open("lena.png")
t1 = time.time()
quart_tour2(image,0,0,512)
t2 = time.time()
print(t2-t1)
image.show()

Adapter l'autre fonction vue en cours