Exercices corrigés - Algorithmique : listes, files,...

Dans la fonction, on commence par tester si la liste est vide. Si ce n'est pas le cas, on regarde si l'élément est plus grand que tous les éléments de la liste : si c'est le cas, on l'ajoute à la fin. Sinon, on parcourt tous les éléments de la liste jusqu'à trouver la bonne place. Remarquons que la boucle se termine car, si on exécute la boucle, on sait que elt est inférieur ou égal au dernier élément de la liste. On réalise au début de la fonction une copie de la liste l pour ne pas modifier celle-ci.

1. 
   def maxi(L):
       retour=L[0]
       for i in range(1,len(L)):
           if (L[i]>retour):
                retour=L[i]
       return retour;
   

   Cet algorithme parcourt une fois la liste, et à chaque étape, effectue une ou deux opérations élementaires. La complexité de cette fonction est donc en $O(n)$.

2. On commence par écrire une fonction intermédiaire $nb(L,i)$ qui donne le nombre de fois où $i$ apparait dans $L$ puis on crée $T$ en donnant à $T[i]$ la valeur de $nb(L,i)$ pour toute valeur de $i$ possible.
   
   def nb(L,i):
       retour=0
       for j in range(len(L)):
           if (L[j]==i):
               retour+=1
       return retour
   
   def nboc(L):
       T=[]
       for i in range(maxi(L)+1):
           T.append(nb(L,i))
       return T;
   

3. La fonction $nb(L,i)$ effectue $O(n)$ opérations élémentaires. La fonction $nboc(L)$ appelle $M+1$ fois la fonction $nb(L,i)$. La complexité de cette dernière fonction est donc en $O(M\times n)$. Remarquons que $M$ peut être beaucoup plus grand que $n$.
4. On va parcourir une seule fois la liste $L$ et modifier la liste $T$ au fur et à mesure de ce parcours.
   
   def nboc2(L):
       T=[0]*(maxi(L)+1)  # On crée une liste de longeur maxi(L)+1
       # où tous les éléments sont nuls
       for i in range(len(L)):
           T[L[i]]+=1
       return T
   

   La complexité de cette fonction est désormais en $O(n)$.

1. • D'abord $L[5]=8$ qui est plus grand que $x=6$. On entre dans la partie "else" de la fonction, avec $a=1$ et $b=5$, puis $c=3$. On a $L[3]=7$ qui est plus grand que $x$, donc on change $b$ en $3$. On a ensuite (deuxième exécution de la boucle while) $c=2$ et $L[2]=5<6$. Il vient $a=3$ et on sort de la boucle. La fonction retourne donc $3$.
   • Là encore, on va rentrer dans la boucle while. Comme $x$ est inférieur à tous les éléments de la liste, c'est toujours $b$ qu'on va changer. La fonction va donc retourner $0$.
2. Si $x>L[d]$, alors rech_dico retourne $d+1$. Sinon, rech_dico retourne un entier $k$ compris entre $g$ et $d$ tel que
   • tous les éléments $L[g],\dots,L[k-1]$ sont strictement inférieurs à $x$;
   • tous les élements $L[k],\dots,L[g]$ sont supérieurs ou égaux à $x$.
   Cette propriété se démontre par le fait que, à chaque itération de la boucle, les éléments $L[g],\dots,L[a-1]$ sont strictement inférieurs ou égaux à $x$, et les éléments $L[b],\dots,L[d]$ sont supérieurs ou égaux à $x$. Cette propriété est vraie en rentrant dans la boucle. Ensuite, si la propriété est vraie au début d'une itération de la boucle, elle l'est encore en sortant de la boucle. En effet, si $L[c]\geq x$, alors $b=c$ et les éléments $L[b],\dots,L[d]$ sont encore supérieurs ou égaux à $x$ en sortant de la boucle (et $a$ est inchangé). Sinon, $L[c]<x$, et puisque $a=c+1$, les éléments $L[g],\dots,L[a-1]=L[c]$ sont bien strictement inférieurs à $x$.
3. Le nombre de comparaisons effectué est proportionnel au nombre d'itérations de la boucle. Notons $a_n$ (resp. $b_n$) la valeur de $a$ (resp. $b$) au début de la $n$-ième itération de la boucle. Alors $a_1=g$ et $b_1=d$. De plus, on a $b_{n+1}-a_{n+1}\leq\frac{b_n-a_n}{2}$. C'est vrai si $b_{n+1}=c\leq \frac{a_n+b_n}2$. En effet, on a alors $$b_{n+1}-a_{n+1}\leq\frac{a_n+b_n}2-a_n=\frac{b_n-a_n}2.$$ C'est aussi vrai si $a_{n+1}=c+1\geq\frac{a_n+b_n}2$ comme le montre un calcul similaire.
   On a donc, tant qu'on n'est pas sorti de la boucle, $$b_n-a_n=\frac{g-d}{2^{n-1}}.$$ On sort pour le premier $n$ tel que $b_n-a_n<1$, et donc dès que $n$ vérifie l'inégalité $$1>\frac{g-d}{2^{n-1}}\iff n> 1+\log_2(g-d).$$ La complexité est donc $O\left(\log_2(g-d)\right)$.