Complexité pratique contre complexité théorique

Principe de la complexité

La complexité en algorithmique sert à montrer l'efficacité d'un algorithme, en fonction de plusieurs facteurs comme son temps d'exécution, l'espace qu'il occupe dans la mémoire... (ces facteurs sont en générale induits par le nombre d'opérations qu'effectue l'algorithme).
Afin de mesurer et de représenter cette complexité, on représente l'évolution du temps d'exécution d'une même fonction en fonction de la taille de ses arguments.
On va donc, la plupart du temps utiliser des tableaux en entrée des fonctions, et faire évoluer leurs tailles afin d'obtenir la courbe de leur complexité.
Cette courbe va ainsi nous éclairer sur le comportement asymptotique de l'algorithme.
Ce comportement asymptotique représente le comportement général de la fonction de la complexité (souvent impossible à calculer de manière exacte).
Cette approximation est généralement représentée par $O(f(n))$, ou f(n) représente une fonction telle que pour n ->$+\infty$, ${\frac {c(n)}{f(n)}}=0$ (où c(x) représente la fonction de la complexité).
Ce comportement asymptotique peut être analysé sous deux différents point de vue:
Le point de vue théorique, qui va analyser le comportement générale de deux complexité et déduire laquelle des deux est la moins complexe en prenant la valeur vers laquelle tend O(f(n)) pour $+\infty$.
Le point de vue pratique, qui, quand à lui va analyser le comportement générale de deux complexité en fonction d'une taille de tableau limité par l'utilisation régulière de la fonction ou capacité à traiter les information de l'ordinateur.

Etudes d'algorithmes

Afin de mesurer la complexité avec le langage python, on utilise généralement une fonction essentielle, la bibliotheque "timeit".

import timeit

def chronoquick(tab,nessais):
    '''Entrées: un tableau et un entier, Sortie: un entier''' 
    res = timeit.timeit("quickselectmed("+ str (tab)+")","from __main__ import quickselectmed" , number= nessais)
    return res

La fonction timeit.timeit permet de mesurer le temps d'exécution de la fonction entrée (ici quickselectmed(tab)) en fonction d'un nombre d'essais défini. Plus ce nombre d'essais est grand, plus le taux d'erreur sur la forme générale de la courbe sera réduit.

dichotomie

def entiersdicho(tab, entier):
    '''Entrée: tab un tableau, entier un entier
    Sortie: res un entier (position de l'entier dans le tableau'''
    b_inf = 0
    b_sup = len(tab)
    while b_inf <= b_sup and b_inf < len(tab) :
        mil =(b_sup + b_inf)//2
        if tab[mil] > entier :
            b_sup = mil
        elif tab[mil] == entier:
            return mil
        else:
            b_inf = mil + 1
    return -1


def cherchetab(tab):
    entier = randint(0,len(tab))
    res = entiersdicho(tab, entier)
    return res

tri de tableau: main/python

def echange(tab, i , j):
    '''Entrée: tableau, deux entier i et j, Sortie: tableau '''
    val_i=tab[i]
    val_j=tab[j]
    tab[i] = val_j
    tab[j] = val_i
    return tab

def triabulle(tab):
    '''Entrée : un entier, Sortie: un tableau'''
    fini = False
    while fini == False:
        nbechanges = 0
        for i in range (0,len(tab)-1):
            if (tab[i]> tab[i+1]):
                echange (tab, i , i+1)
                nbechanges = nbechanges + 1
        if nbechanges == 0:
            fini = True
    return tab

def tripython(tab):
    '''Entrée : un entier, Sortie: un tableau'''
    res = sorted(tab)
    return res

mediane

def medianenaive(tab):
    '''Entrée: un tableau, Sortie: un entier'''
    tri = triabulle(tab)
    res= tri[len(tab)//2]
    return res

def medianepython(tab):
    '''Entrée: un tableau, Sortie: un entier'''
    return median(tab)

medianes des medianes, quickselect

quickselect :

def quickselectmed(tab):
    '''Entrée: un tableau, Sortie: un entier'''
    taille = len(tab)
    indicemed = taille//2
    valmed = cherchevalind(tab,indicemed)
    t = sorted(tab)
    return valmed, t[len(t)//2]

def cherchevalind(tab,indice):
    elmt = tab[randint(0,len(tab)-1)]
    inf = []
    sup = []
    for i in range(0, len(tab)):
        if tab[i] < elmt:
            inf.append(tab[i])
        elif tab[i]> elmt:
            sup.append(tab[i])
    if len(tab) - len(sup) > indice >= len(inf):
        return elmt
    elif len(inf) > indice:
        return cherchevalind(inf,indice)
    else:
        return cherchevalind(sup,indice - len(tab) + len(sup))

Medianes des medianes :

Multiplication naive / Karatsuba

Multiplication naive:

def multscalaireT(T,a):
    return [T[i] * a for i in range (len(T))]

def multnaive(T1,T2):
    res = []
    for i in range (len(T1)):
        addition =([0] * i) + multscalaireT(T2,T1[i])
        res = plus(addition,res)
    return res

def plus(T1,T2):
    m = min(len(T1),len(T2))
    res = [T1[i] + T2[i] for i in range(m)]
    res.extend(T1[m:]+T2[m:])
    return res