Discussion :

[nadia85]

Bonjour,

Je voudrais comprendre la complexité de:

Pour i = n à 1 pas i div 2
Pour j = 0 à i
x = x+1

et celle de:

Tant que (n<>0)
n=n div 10

Pourriez-vous me donner une explication.

Merci d'avance

[tbc92]

Tentons une explication. C'est un chapitre que je n'aime pas, je trouve qu'on donne trop d'importance à ce chapitre, qu'on l'aborde généralement en début de cursus, alors que c'est intéressant uniquement quand on devient vraiment un programmeur très avancé.
La complexité d'un algorithme, c'est un indicateur qui dit comment va se comporter un programme quand les tailles des données manipulées augmentent.
Commençons par le 2ème algorithme.
Combien d'étapes de calcul y-a-t-il quand n vaut 10 millions ? Combien y en a-t-il quand n est plus grand, et vaut 100 millions, puis 1 milliard ?
Jusque là, c'est facile.
Est-ce que tu vois une formule mathématique qui donne ce nombre d'étapes à partir de n ? (là, faut être un peu plus matheux)

Pour le 1er exercice, c'est le 1er calcul qui est un peu plus compliquée.
Quand n vaut 1 Million, combien y a-t-il d'étapes,
Pareil, quand n vaut 10 millions, ou 100 millions, combien y-a-t-il d'étapes ? (= combien de fois on passe par l'instruction qui est au coeur de la boucle )
Et ensuite, il nous faut une formule mathématique qui donne ce nombre d'étapes, en fonction de n.

On veut juste une formule approximative. Un ordre de grandeur. Quand n est grand, n² ou n²+5n par exemple, c'est pareil, on garde n² uniquement. 1000Milliards, ou 1000Milliards+5millions, on considère que c'est pareil, et on oublie les 5Millions.

[Guesset]

Bonjour,

En complément, il ne faut pas hésiter à prendre une feuille de papier et écrire les différentes étapes. L'alternative étant de faire tourner le programme chronomètre en main (dématérialisé bien sûr) sur des ordres de grandeurs élevés ce qui peut s'avérer assez trompeur ou long.

Prenons par exemple le premier exercice. On regarde la boucle la plus externe étape par étape sans trop s'intéresser aux précisions de calcul (comme si n div 2 <=> n / 2). A chaque étape i passe à i - i/2 (boucle décroissante) soit i/2 :

1: i = n, 2: i = n/2, 3: i = n/4,... t: i = n/2^t, ... tmax=log₂(n)]: n/2^tmax=1. Le nombre d'étapes est tmax.

Ensuite on regarde la boucle interne qui a i + 1 itérations pour chaque valeur de i. Le nombre total d'itérations est donc la somme des valeurs de i + tmax (on peut négliger ce dernier terme). En se rappelant que la série 1+1/2 + 1/4 + 1/8... converge vers 2 on trouve facilement la solution.

Bon, je ne vais pas faire tout l'exercice

Salutations