Tris : complexité

Des séances difficiles aujourd’hui et mercredi, peut-être conceptuellement les plus difficiles de l’année.


Plan (début du cours à 10h) :

  • Question flash
  • Correction algorithmes
  • Complexité (temporelle)
  • Salon de discussion de 11h à 12h
    • Attentes et habitudes de travail pour cette période de confinement
    • Complexité
  • Preuves (pas abordé aujourd’hui)
  • Exercices donnés pour mercredi

Question flash :

  • Compléter le corps de la boucle « intérieure » en une instruction d’une ligne pour que ce programme affiche tous les nombres de 00 à 99
    for d in range(10):
        for u in range(10):
            ...

Plusieurs réponses proposées :

  • Attendue avec d comme chiffre des dizaines et u comme chiffre des unités
    for d in range(10):
        for u in range(10):
            print(d * 10 + u)
  • En concaténation pour l’affichage avec d comme chiffre des dizaines et u comme chiffre des unités
    for d in range(10):
        for u in range(10):
            print(str(d) + str(u))
  • En changeant les range 😉 pas imposés à l’origine avec d comme chiffre des dizaines et u comme chiffre des unités
    for d in range(0, 100, 10):
        for u in range(10):
            print(d + u)
  • D’autres…

Correction de l’implémentation des algorithmes demandée

Allez prendre connaissance des corrections des algorithmes pour aujourd’hui :

Préparez vos questions pour le salon de discussion à 11H.

Peu de questions. Il y avait ceux qui avaient bossé, et les autres !

Mais aussi des problèmes MBN. On a statué sur le fait qu’on pouvait m’envoyer des codes de plein de manières, discord, mail, etc.

ET aussi TAKE IT EASY 😉 IT’S GONNA BE ALRIGHT ! BUT WORK !


Complexité (temporelle)

a) Une intuition ?

J’ai fait quelques animations pour illustrer mon propos.

Une liste aléatoire de 16 chiffres et les deux tris en action :

0_animation_les_deux_en_meme_temps

  • En vert les cases déjà triées,
  • la flèche rouge pour le rang,
  • la case rouge pour la « boucle intérieure »,
  • les cases en bleu encore à trier,
  • en jaune la valeur correspondant temporairement à « i_min » pour le tri par sélection.

On compte le nombre de comparaisons en haut à droite.
Ce sera notre indicateur de complexité temporelle. Une intuition ?

-> Notre intuition c’est que le tri par insertion semble a priori plus rapide… c’est-à-dire moins de comparaisons et donc une plus faible complexité temporelle .

b) Plus dans le détail – tri par sélection

Avec nos cartes comme dans la vidéo de l’autre jour

cm 2020-03-23 cartes dessinees

Qu’est-ce que ça donne :

  • Combien de comparaisons ? -> 20
  • Ce nombre change-t-il suivant la valeur des six cartes ? -> non, on fait toujours les mêmes comparaisons :
(Notes de notre salon de discussion discord)
(Complexité temporelle : nombre de comparaisons)
Tri sélection pour 6 valeurs :
    Premier passage 
       -> 5 comparaisons (boucle intérieure) 
       -> + 1 comparaison de i_min et rand donc 
    Donc :
        1er passage 5 + 1 = 6 comparaisons
	2e passage  4 + 1 = 5 comparaisons
	3e passage  3 + 1 = 4 comparaisons
	4e passage  2 + 1 = 3 comparaisons
	5e passage  1 + 1 = 2 comparaisons
    Fin du programme :
        6 + 5 + 4 + 3 + 2 = 20 comparaisons

c) Plus dans le détail – tri par insertion

Toujours avec nos cartes, comme dans l’autre vidéo de l’autre … autre jour

cm 2020-03-23 cartes dessinees

Qu’est-ce que ça donne :

  • Combien de comparaisons ? -> 14
  • Ce nombre change-t-il suivant la valeur des six cartes ? -> Oui, on n’insère pas un 2 comme on insère un 8 par exemple !

c) Plus dans le détail – comparaison des tris par sélection et par insertion

Toujours avec nos cartes des autres jours :

Qu’est-ce que ça donne :

  • Qui est le plus rapide (moins de comparaisons) ?
    -> le tri par insertion
  • Est-ce toujours le cas ?
    -> On dirait ! (?)

On veut en avoir le cœur net :

d) Un exemple, le « pire des cas » pour le tri par insertion

Questions :

On cherche une conclusion : complexité temporelle de ces deux tris

  • Combien de comparaisons pour le tri par sélection de 6 valeurs ? -> 20
  • Combien de comparaisons au maximum (dans le pire des cas) pour le tri par insertion de 6 valeurs ? -> 20 aussi (au pire)
  • Combien de comparaisons pour le tri par sélection de 10 valeurs ? -> 54
  • Combien de comparaisons au maximum (dans le pire des cas) pour le tri par insertion de 10 valeurs ? -> 54 aussi (au pire)
  • Combien de comparaisons pour le tri par sélection de 7 valeurs ? -> 27
  • Combien de comparaisons au maximum (dans le pire des cas) pour le tri par insertion de 7 valeurs ? -> 27 aussi (au pire)
  • Combien de comparaisons pour le tri par sélection de 16 valeurs (premier gif animé) ? -> 135
  • Combien de comparaisons au maximum (dans le pire des cas) pour le tri par insertion de 16 valeurs ? -> 135 aussi (au pire)
  • On considère maintenant n un entier positif non nul.
  • Combien de comparaisons pour le tri par sélection de n valeurs ?
    De l'ordre du carré de n.
    On parle de complexité quadratique, voir ci-dessous.
  • Combien de comparaisons au maximum (dans le pire des cas) pour le tri par insertion de n valeurs ?
    Et bien la même chose : 
    si la liste est triée par valeurs décroissantes !

La partie théorique abordée aujourd’hui

Complexité du tri par sélection

(Notes de notre salon de discussion discord)
(Complexité temporelle : nombre de comparaisons)
Tri sélection pour n valeurs :
    Premier passage 
       -> (n - 1) comparaisons (boucle intérieure) 
       -> + 1 comparaison de i_min et rand donc 
    Donc :
        1er passage    n    comparaisons
	2e passage  (n - 1) comparaisons
	3e passage  (n - 2) comparaisons
                      ...
avant-dernier passage  3    comparaisons
      dernier passage  2    comparaisons
Fin du programme :
   n + (n - 1) + (n - 2) + ... + 3 + 2 comparaisons

Combien ça fait n +(n - 1) + (n - 2) + ... + 3 + 2 ?

Écrivons le deux fois, l’un au-dessous de l’autre :

cm 2020-03-23 calcul somme complexité

Les deux lignes font donc (n+2) \times (n -1)=n^2+2n-n-2=n^2+n-2.

Une seule ligne fait donc \boxed{n +(n - 1) + (n - 2) + ... + 3 + 2 = \dfrac{n^2+n-2}{2}}.

Les informaticiens estiment que, quand n devient grand, il devient négligeable devant le n^2, tout comme le -2. Ils estiment même que la division par deux n’est pas le cœur du problème.

En effet, pour n = 1 000 000, n^2 fait mille milliards, et même n = 1 000 000 est négligeable…

Pour simplifier, avec une notation de Landau utilisées en informatique, on retiendra que :

La complexité du tri par sélection est de l’ordre du carré de n : on parle de complexité quadratique, et on la note O(n^2) : « de l’ordre de n^2 au pire »

A titre de comparaison, la recherche du maximum ou du minimum dans une liste nécessite autant de comparaisons que le nombre d’éléments n de cette liste, on dit qu’elle est linéaire, et  on la note O(n).

Complexité du tri par insertion

Il nous semble meilleur, donc plus rapide, donc avec une complexité plus faible. EN MOYENNE, c’est certainement vrai.

Mais AU PIRE, quand la liste est à l’origine classée par valeurs décroissantes, la complexité est la même :

(Notes de notre salon de discussion discord)
(Complexité temporelle : nombre de comparaisons)
Tri insertion pour n valeurs triées dans l'ordre décroissant 
(comme 8 7 6 5 4 3 2) :
    Premier passage 
       -> 1 comparaisons (boucle intérieure) 
       -> + 1 comparaison de i avec zéro 
    Donc :
        1er passage      2    comparaisons
	2e passage       3    comparaisons
	3e passage       4    comparaisons
                        ...
avant-dernier passage (n - 1) comparaisons
      dernier passage    n    comparaisons
Fin du programme :
   2 + 3 + ...  + (n - 2) + (n - 1) + n comparaisons

Donc n +(n - 1) + (n - 2) + ... + 3 + 2 = 2 + 3 + ... + (n-2)+(n-1)+n

On a donc aussi, dans le pire des cas : \boxed{n +(n - 1) + (n - 2) + ... + 3 + 2 = \dfrac{n^2+n-2}{2}}.

La complexité AU PIRE du tri par insertion est aussi de l’ordre du carré de n : une complexité quadratique, notée aussi O(n^2) : « de l’ordre de n^2 au pire »

Conclusion à retenir :

  • Le tri par sélection est de complexité quadratique.
  • Le tri par insertion est de complexité quadratique, au pire.

Sinon, on abordera mercredi cette question :

  • Ces tris sont-ils toujours corrects ? Peut-on les PROUVER ?

Mercredi salon de discussion 13h27 – 15h17 😉

Pour mercredi 25 mars -> à rendre au plus tard dans la nuit de mardi à mercredi par le canal que vous voulez (discord, mail, MBN, etc.):

  1. Premier exercice : refaire la question flash pour que votre algorithme affiche toutes les couleurs (codes à six chiffres hexadécimaux) possibles … en théorie !
    Il y en a beaucoup trop… combien ?
  2. Deuxième exercice : combien de triplets (a, b, c) tels que a^2 + b^2 = c^2a, b, c sont des entiers non nuls, chacun au maximum égal à 100?
    Avec un algorithme bien entendu…
    Parmi ceux -ci, combien forment des triangles rectangles (c’est-à-dire : peut-on tous les construire) ?
  3. Retravailler sérieusement le cours d’aujourd’hui.

N'hésitez-pas à poser une question, ou faire avancer le schmilblick

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google

Vous commentez à l'aide de votre compte Google. Déconnexion /  Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion /  Changer )

Connexion à %s

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur la façon dont les données de vos commentaires sont traitées.