Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Cours : complexit´ e Christophe Ritzenthaler November 12, 2008 1 Quelques notio

Cours : complexit´ e Christophe Ritzenthaler November 12, 2008 1 Quelques notions g´ en´ erales 1.1 Principes Le temps d’ex´ ecution d’un programme d´ epend de plusieurs donn´ ees : 1. du type d’ordinateur utilis´ e; 2. du langage utilis´ e (repr´ esentation des donn´ ees); 3. de la complexit´ e abstraite de l’algorithme sous-jacent. Pour le mesurer en MAPLE, on peut utiliser les commandes suivantes (ici pour un programme g) : S := [seq([i, time(g(10i))], i = 1 . . . 10)]. En g´ en´ eral, on veut s’abstraire des deux premi` eres donn´ ees. Pour se faire, il faut ˆ etre en mesure de donner un cadre th´ eorique ` a l’algorithmique. Pour le premier point ceci se fait par la d´ eﬁnition d’un ordinateur ‘universel’ (une machine de Turing) qui bien qu’extrˆ emement simple peut reproduire le comportement de n’importe quel ordinateur existant. Pour s’abstraire du second point, on regardera des classes d’´ equivalence de complexit´ e (voir plus bas) plutˆ ot que la complexit´ e elle-mˆ eme, ce qui permettra de ne pas se pr´ eoccuper des constantes qui interviennent dans les changements de repr´ esentations ‘naturelles’ et dans la d´ eﬁnition des op´ erations ´ el´ ementaires. La mesure de la complexit´ e d’un algorithme c’est : 1. ´ evaluer les ressources (m´ emoire et CPU) utiles; 2. Comparer deux algorithmes pour le mˆ eme probl` eme; 3. donner une borne sur ce qui est eﬀectivement possible de r´ esoudre. On consid` ere aujourd’hui qu’on peut r´ ealiser en temps raisonnable 260 op´ erations. Quant ` a la m´ emoire elle est de l’ordre de 1010 octets. On peut donc s’int´ eresser ` a deux types de complexit´ e : en temps et en m´ emoire. Nous ne consid´ ererons que la premi` ere. La complexit´ e abstraite se mesure en fonction de la taille des entr´ ees. 1 Example 1. Pour un entier, il s’agit du nombres de chiﬀres n´ ecessaires ` a son ´ ecriture. On peut bien sˆ ur imaginer des circonstances o` u d’autres facteurs seraient plus impor- tants. Par exemple si un algorithme factorise un nombre al´ eatoire de plus en plus grand ` a chaque fois qu’il rencontre un 9 dans l’´ ecriture du nombre. On notera |a|b la taille de a en base b. On a bien sˆ ur |a|b = ⌊logb a⌋+ 1. Remarquons qu’un changement de base multiplie la taille par une constante. Pour une liste, le param` etre est le cardinal de la liste. On peut noter que ceci est coh´ erent avec la complexit´ e pour les entiers, car le tableau pourrait contenir les chiﬀres du nom- bre. Dans l’algorithme de la division euclidienne, on a deux entiers a, b en entr´ ee. On mesur- era la complexit´ e en fonction du sup(|a|, |b|). Pour une matrice carr´ ee de taille n c’est n le param` etre. Dans le cas d’op´ erations sur les matrices, la complexit´ e sera alors exprim´ ee comme une fonction de n des op´ erations concernant les coeﬃcients (qui n’auront pas le mˆ eme coˆ ut ´ el´ ementaire selon la nature des coeﬃcients -la complexit´ e en fonction des op´ erations ´ el´ ementaires pouvant ˆ etre alors calcul´ ee dans un deuxi` eme temps). Lorsqu’on manipule des r´ eels, la situation est ´ egalement compliqu´ ee : il faudra d´ eﬁnir une ´ ecriture tronqu´ ee pour pouvoir r´ ealiser les calculs. Mais attention alors aux erreurs d’arrondis ! Pour un polynˆ ome, c’est son degr´ e. Enﬁn dans certains cas, il n’est pas possible de ne faire intervenir qu’une donn´ ee. Par exemple pour un graphe, le nombre de sommets et d’arˆ etes peuvent ˆ etre tous les deux des facteurs importants et pourtant compl` etement ind´ ependants. Comme annoncer, aﬁn de simpliﬁer l’´ etude, on regarde uniquement des complexit´ es asymptotiques (c’est-` a-dire quand la taille de l’entr´ ee tend vers l’inﬁni) qui ne d´ ependent que de la derni` ere condition. Cette complexit´ e existe sous plusieurs formes : dans le meilleur des cas, dans le pire ou en moyenne. Ici encore, on regardera surtout la com- plexit´ e dans le pire des cas puisque c’est elle qui nous assure que l’algorithme se terminera toujours avec le temps au plus annonc´ e. Remarquons tout de mˆ eme que les autres com- plexit´ es peuvent aussi ˆ etre utiles : par exemple, en cryptographie, c’est le temps minimal dans le meilleur des cas qui permet de d´ ecider si aucun algorithme ne pourra casser le protocole en un temps raisonnable. Les tableaux ci-dessous donnent l’inﬂuence de la complexit´ e quand n devient 2n. 1 log2(n) n n log2(n) n2 n3 2n t t + 1 2t 2t + ϵ 4t 8t t2 1 log2(n) n n log2(n) n) n3 2n n = 102 1µs 6µs .1ms .6ms 10ms 1s 4 × 106a n = 103 1µs 10µs 1ms 10ms 1s 16.6mn ∞ n = 106 1µs 20µs 1s 20s 11j 103a ∞ 2 Il est parfois tr` es diﬃcile d’´ evaluer les constantes en jeux. C’est pourquoi on dis- tinguera plutˆ ot des classes de complexit´ e : si n est la taille de l’entr´ ee, on dira que l’algorithme est polynomial (resp. exponentiel) si son temps d’ex´ ecution est de l’ordre de Θ(nb) o` u b ≥1 (resp. Θ(exp(an)) avec a > 0). Rappelons que deux fonctions f, g ` a valeurs positives sont du mˆ eme ordre (f = Θ(g)) si pour x assez grand, il existe deux constantes a, b telles que af(x) ≤g(x) ≤bf(x). En pratique, on utilisera plutˆ ot la comparaison f = O(g) pour simplement donner une majoration. Attention toutefois aux limites d’un r´ esultat asymptotique : pour une plage de donn´ ees ﬁx´ ees (et ﬁnies) il se peut qu’un algorithme en O(Cn2) soit plus rapide qu’un algorithme en O(C′n) si la constante C est beaucoup plus petite que la constante C′. C’est par exemple le cas de la multiplication par l’algorithme FFT. Ces deux classes s´ eparent les algorithmes dits eﬃcaces (=polynomial) des autres (=exponentiel). En eﬀet supposons que pour un nombre entier de taille n le programme A soit de complexit´ e n3 et le programme B de complexit´ e 2n. Alors si la puissance de calcul est multipli´ ee par 1000, A pourra traiter des donn´ ees n′ = 10n fois plus grande alors que le programme B seulement n′ ≈n + 10. Enfon¸ cons le clou et r´ ep´ etons encore une fois le caract` ere invariant de ces notions : par exemple par un changement de base, un entier de taille n devient de taille αn avec α une constante. Ceci ne change donc pas les classes de complexit´ e et mˆ eme l’ordre dans le cas polynomial. 1.2 Mesure de la complexit´ e d’un algorithme R` egles g´ en´ erales : 1. Le temps d’´ ex´ ecution d’une aﬀectation ou d’un test est consid´ er´ e comme constant; 2. Le temps d’une s´ equence d’instruction est la somme des temps des instructions qui la composent; 3. le temps d’un branchement conditionel est ´ egal au temps des maximum des alter- natives 4. Le temps d’une boucle est ´ egal au produit du temps des instructions contenues dans la boucle par le nombre de passages dans celle-ci. Donnons quelques complexit´ es classiques : • Comparaison de deux entiers de taille n : O(n). • addition de deux entiers de taille n : O(n). • multiplication de deux entiers de taille n : O(n2). • division euclidienne de deux entiers de taille n : O(n). 3 • Algorithme d’Euclide pour des entiers de taille au plus n : O(n2). Remark 1. Ces complexit´ es sont basiques. Par exemple pour le produit de deux entiers de taille n on peut obtenir une complexit´ e de O(nlog2(3)) (Karatsuba) voire O(n(log n)3) en utilisant FFT. Cependant (surtout dans le dernier cas), ces am´ eliorations ne se font ressentir r´ eellement que pour des tr` es grandes tailles. Remarquons qu’on ne se ram` ene pas toujours ` a une complexit´ e en nombres d’op´ erations ´ el´ ementaires. Il est possible de s’arrˆ eter ` a mi-chemin et de donner les r´ esultats en fonctions par exemple du nombre d’additions, de multiplications,. . . Ceci permettra d’adapter le calcul ﬁnal de la complexit´ e en fonction de la plage de tailles des donn´ ees que l’on consid` erera. 1.3 Les algorithmes probabilistes Il est utile de consid´ erer une classe plus large d’algorithmes, dit probabilistes, car au- torisant le recours ` a des jets al´ eatoires. Notons qu’en pratique l’al´ eatoire est diﬃcile ` a obtenir. Il est soit obtenu par des moyens physiques (mesure de d´ eplacements de la souris, variations de la temp´ erature du processeur,. . . ), ce qui est diﬃcile et coˆ uteux, ou en utilisant des algorithmes qui sont dit pseudo-al´ eatoires mais qui reste relativement lent. La classe des algorithmes probabilistes uploads/Religion/ cours-complexite1-pdf.pdf