Calculs de complexité d'algorithmes

exécutée ?

; im++)

20

Règle 4

Boucle While (C) {I}

(cid:122)Évaluation de C en Θ(f(n))

(cid:122)I en Θ(f1(n))

(cid:122)Boucle while est exécutée Θ(g(n)) fois

while (C) {

I

}

est en Θ(g(n)*max(f(n),f1(n)))

21

Estimer les complexités des morceaux de codes suivants,

sachant que

l’instruction I1 est en Θ(1) et

I1 ne modifie pas les entiers i, j, k et n

for (int i=0 ; i < n ; i++) {

for (int j=i ; j < n ; j++) {

for (int k=0 ; k < j ;

k++) {

I1

}

}

}

22

Estimer les complexités des morceaux de codes suivants, sachant que et les

instructions I1, I2, I3 sont en Θ(1) et ne modifie pas les entiers i, j, k et n

int i=1 ;

int j=1 ;

while (i <n) {

i++ ;

I1 ;

while (( j < n) && Condition) {

j++ ;

I2

}

I3 ;

}

23

Règle 5

Composition de Méthodes

(cid:122)methode1(Classe1 o1) en

O(f1(taille1(o1))

(cid:122)methode2(Classe2 o2) en O(f2(taille2(o2))

(cid:122)methode2 renvoie un objet de Classe1

La complexité de methode1(methode2(o2))

est en

O(max(f2(taille2(o2)),f1(taille1(methode2(o2))))

24

On connaît l'écriture d'un nombre en base b, et l'on veut convertir ce nombre en base

usuelle (base dix).

1. On utilise la méthode "convertionDirecte". Quelle en est la complexité?

public int convertionDirecte(int[] a, int b) {

int résultat =a[0] ;

int auxiliaire ;

for (int rang =1 ; rang < a.length ; rang++) {

if (a[rang] != 0) {

auxiliaire = a[rang] ;

for (int indice =0 ; indice <rang ;

indice ++) {

auxiliaire = auxiliaire *b ;

}

résultat = résultat + auxiliaire;

}

}

return résultat ;

}

25

2. On utilise la méthode "convertionDirecteV2" dans laquelle on mémorise

dans une variable monome brang. Ecrire cette méthode

"convertionDirecteV2" et en donner la complexité ?

26

3. Prouvez que la méthode suivante dite de Horner,

effectue bien le même travail. Quelle en est la

complexité ?

public int horner(int[] a, int b) {

int n = a.length ;

int résultat =a[n-1] ;

for (int rang = n-2 ; rang >= 0 ;

rang--){

résultat = b* résultat +a[rang] ;

}

return résultat ;

}

27

On désire élever l'entier a à la puissance n.

Quelle est la complexité de la méthode suivante ?

public int puissance(int n, int a) {

int résultat = a ;

for(int i =1 ; i <n ;i++){

résultat=résultat*a ;

}

return résultat ;

}

28

Montrez que le code suivant est correct. Quel en est la complexité ?

public int puissance(int n, int a) {

int aux = n ;

int puissanceDea = a ;

int résultat=1 ;

while ( aux != 0 ) {

if (aux mod 2 == 1) {

résultat = résultat * puissanceDea ;

}

aux=aux/2 ;

puissanceDea = puissanceDea * puissanceDea ;

}

return résultat ;

}

29

Programmation récursive

(cid:122)Quelques exemples

(cid:122)Equations de récurrences

(cid:122)Quelques méthodes de résolution

30

Recherche dichotomique du plus grand

élément

(cid:122)L contient n éléments

(cid:122)Algorithme (récursif)

(cid:123)Si L contient un seul élément : c’est fini

(cid:123)Sinon :

(cid:122)Couper L en deux listes L1 et L2 de taille

"presque" identiques

(cid:122)Chercher m1 le max de L1

(cid:122)Chercher m2 le max de L1

(cid:122)Retourner le max de m1 et m2

31

Combien de comparaisons ?

On note c(n) le nombre de comparaisons

nécessaires pour la recherche

dichotomique du plus grand élément dans

une liste de taille n

(cid:122)c(1) = 0

(cid:122) c(n) = c(⎡n/2⎤)+c(⎣n/2⎦)+1

32

Déterminez la complexité de la méthode suivante

int factorial(int n) {

if (n == 0) {

return 1;

}

else {

return (n*factorial(n-1));

}

}

33

Méthode factorielle

(cid:122)Soit c(n) la nombre de multiplications

effectuées dans le calcul de factorial(n).

(cid:122)On a c(n)=c(n-1)+1, c(1)=0

34

Recherche du maximum dans une

table de n éléments

(cid:122)Si n=1, renvoyer l’unique élément

(cid:122)Sinon calculer récursivement le maximum

des n-1 premiers élements;

Le comparer avec le dernier élément;

renvoyer le plus grand des deux.

35

Analyse : nombre de comparaisons

effectuées

(cid:122)C(n)= complexité de la recherche du plus

grand parmi n

(cid:122)c(n)=c(n-1)+1

(cid:122)c(1)=0

36

Trier une table de n éléments

(cid:122)Si n=1 rien à faire

(cid:122)Sinon

(cid:123) rechercher le maximum de la table

(cid:123) échanger le maximum et le dernier élément

(cid:123) trier la sous-table constituée des n-1

premiers éléments

37

(cid:122)c(n)=c(n-1)+an+b

(cid:122)c(1)=1

38

Tours de Hanoi

(cid:122)Combien de mouvements au minimum

pour déplacer une tour de n disques

39

Tour de Hanoi

public class Towers {

static int nDisks=7;

public static void main(String[]

args){

moveTowers(nDisks,’A’,’B’,’C’);

}

}

40

// Pré-condition : n > 0

public static void moveTowers(int n, char

from, char inter, char to) {

if (n==1) {

moveDisk(1,from,to);

}

else {

moveTowers(n-1,from,to,inter);

moveDisk(n,from,to);

moveTowers(n-1,inter,from,to);

}

}

où moveDisk(n,from,to) peut être par exemple :

System.out.println(“Disk ” + n +” from ”+ from + ” to ” + to)

41

Complexité de moveTowers

(cid:122)c(n)=2c(n-1)+k

(ou c(n)=2c(n-1)+1)

(cid:122)Donc c(n)=a2n+b

(cid:122)C(n)=Θ(2n)

42

(cid:122) On considère deux versions modifiées des tours de Hanoi.

Dans chacun des cas, on demande quel est le nombre

minimum de déplacements de disques nécessaires.

(cid:122) La pile contient initialement 2n disques, de n tailles

différentes, il y a deux disques de chaque taille. Les

disques de même taille sont indistinguables.

(cid:122) La pile comporte n disques de taille différente, mais les 3

piquets sont sur un cercle et les mouvements élémentaires

de disques se font du piquet où est le disque à son suivant

dans le sens des aiguilles d'une montre.

43

Nombres De Fibonacci

La suite de Fibonacci

Leonardo de Pise, surnommé Fibonacci

est un mystère de l'histoire des

mathématiques. Il serait né vers 1175 et

mort en 1240 (?), et aurait vécu toute sa

vie à Pise. Il a publié un unique livre, Liber

Abaci (une œuvre collective ?).

44

Nombres De Fibonacci

Reproduction des lapins : «Possédant au départ un couple de

lapins , combien de couples de lapins obtient-on en douze mois si

chaque couple engendre tous les mois un nouveau couple à

compter du second mois de son existence ? »

(cid:122) Janvier : 1 couple

(cid:122) Février : 1 couple

(cid:122) Mars : 1 + 1 = 2 couples

(cid:122) Avril : 2 + 1 = 3 couples

(cid:122) Mai : 3 + 2 = 5 couples

(cid:122) Juin : 5 + 3 = 8 couples

(cid:122) Juillet : 8 + 5 = 13 couples

(cid:122) Août : 13 + 8 = 21 couples

(cid:122) Septembre : 21 + 13 = 34 couples

(cid:122) Octobre : 34 + 21 = 55 couples

(cid:122) Novembre : 55 + 34 = 89 couples

(cid:122) Décembre : 89 + 55 = 144 couples

(cid:122) Janvier : 144 + 89 = 233 couples

45

Nombres De Fibonacci

(cid:122) Janvier : 1 couple

(cid:122) Février : 1 couple

(cid:122) Mars : 1 + 1 = 2 couples

(cid:122) Avril : 2 + 1 = 3 couples

(cid:122) Mai : 3 + 2 = 5 couples

(cid:122) Juin : 5 + 3 = 8 couples

(cid:122) Juillet : 8 + 5 = 13 couples

(cid:122) Août : 13 + 8 = 21 couples

(cid:122) Septembre : 21 + 13 = 34 couples

(cid:122) Octobre : 34 + 21 = 55 couples

(cid:122) Novembre : 55 + 34 = 89 couples

(cid:122) Décembre : 89 + 55 = 144 couples

(cid:122) Janvier : 144 + 89 = 233 couples

Le tableau correspond à ce qu'on appelle la

suite des nombres de Fibonacci.

46

On note Fn le nombre de couples de lapins au

mois n.

F(n) = nombre de couples au mois (n-1)

+ nombre de couples nés au mois n

= nombre de couples au mois ( n-1)

+ nombre de couples productifs au mois (n-1)

= nombre de couples au mois ( n-1)

+ nombre de couples nés au mois (n-2)

F(n) = F(n-1) + F(n-2)

47

Nombres De Fibonacci

public int fibonacci (int n) {

if (n==0) return 0 ;

else {

if (n==1) return 1 ;

else

return fibonacci(n-1)+fibonacci(n-2);

}

}

48

Analyse de la complexité

(cid:122)c(n)=c(n-1)+c(n-2)+1

(cid:122)c(1)=c(0)=1

49

Complexité d’une méthode récursive

…...

…… résolution d’une équation de

récurrence

(cid:122)Avec un outil de calcul formel (type maple)

(cid:122)Avec des théorèmes de maths

50

Récurrences linéaires

(cid:122) Définition:

Une relation de récurrence linéaire homogène

d’ordre k , à coefficients constants est définie par

une équation de la forme

u

=

ua

1

n

K

Le polynôme caractéristique associé est

kn

−

1

−

n

+

ua

k

(

R

)

+

)(

rP

=

r

k

k

1

−

−

ra

1

−

K

−

ara

1

−

−

k

k

51

Solutions d’une équation de récurrence

linéaire d’ordre k

(cid:122)L’ensemble des solutions forme un espace

vectoriel de dimension k

(cid:122)Si r est racine du polynôme caractéristique

r

est solution de

α=

u

n

alors

n

l’équation.

(cid:122)Cas des racines multiples

52

Méthode du polynôme caractéristique

(cid:122)Soit E l’équation de récurrence.

(cid:122)Soient ri , les q racines du polynôme

caractéristique de (E), ri ayant multiplicité mi.

(cid:122)Les solutions de (E) s’écrivent sous la forme

(

rnP

)

n

q

i

i

∑

i

=

1

où les Pi(n)sont des polynômes en n de degré

mi-1.

53

Exemple

(cid:122)Déterminer en fonction de u0 et u1, la suite

telle que

(cid:122)un=un-1-2un-2

54

Réponse

un =

⎛

⎝

u0

2

− i(

2u1 − u0

2 7

)

⎞

n +

r1

⎠

u0

⎛

⎝

2

+ i(

2u1 − u0

2 7

)

⎞

n

r2

⎠

r1 =

1 + i 7

2

r2 =

1 − i 7

2

55

Exercice

(cid:122)Utilisez la méthode du polynôme

caractéristique pour résoudre l’équation de

récurrence

u

u

u

n

0

1

=

=

=

4

u

n

−

1

−

4

u

n

−

2

1

6

56

Exercice

(cid:122)Chaque jour, pour mon goûter , je m’achète

ou ou

2F 2F 4F

(cid:122) Soit gn le nombre de choix de goûters possibles si l’on a n

Francs

(cid:123)Déterminer g1, g2, g3 et g4

(cid:123)Déterminer et résoudre l’équation de récurrence liant les gn

57

(cid:122)Donnez l’ensemble des solutions des

équations de récurrences suivantes :

(cid:122)un=2un-1 - un-2

(cid:122)vn=vn-1 + 6vn-2

58

(cid:122)Déterminez la suite un , telle que :

(cid:122)un = 5un-1 - 8un-2 + 4un-3

(cid:122)u1 = 3, u2 = 11, u3 = 31

59

Equations non homogènes

(cid:122)Soit R’ l’équation non homogène

∀ n ≥ k, un = a1un−1 +…+akun− k + b(n)

(cid:122)On lui associe l’équation homogène R

∀ n ≥ k, un = a1un−1 +…+akun− k

(cid:122)La différence entre deux solutions de R’

est une solution de R

60

Espace affine/

Espace vectoriel

(cid:122)Soit sn une solution particulière de R’.

(cid:122)Toute solution de R’ est obtenue à partir

d’une solution de R en lui ajoutant sn

61

Une recette de cuisine

(cid:122)Si l’équation est de la forme

il existe une solution particulière de la forme

l

∀ n ≥ k, un = a1un− 1 +…+ akun− k +

∑ Qi(n)

n

bi

l

i = 1

∑ Pi(n)

n

bi

i = 1

où Qi(n) est un polynôme de degré d(Pi)+mi

avec mi=0 si bi n’est pas racine du polynôme

caractéristique, et mi = la multiplicité pour

une racine

62

Exercices

u

n

=

u

2

n

1

−

+

u

,1

0

=

0

u

n

=

u

2

n

1

−

n

++

n

u

,2

1

=

0

63

(cid:122)Donnez l’ensemble des solutions des

équations de récurrence suivantes :

(cid:122)un = 3un-1 - 2un-2 + n

(cid:122)vn = vn-1 + 6vn-2 + 5n

(cid:122)wn = wn-1 + 6wn-2 + 3n

64

(cid:122)Résoudre l'équation de récurrence

(cid:122)un = 3un-1 - 2un-2 + n, u0 = 0, u1 = 0

65

(cid:122)Soit sommeFactoriel, la fonction définie

par Evaluer la complexité en nombre de

multiplications des méthodes récursives

après

66

public int sommeFactoriel(int n) {

int factorieln ;

if (n<=1) {

return n+1;

}

else {

factorieln = n * ( sommeFactoriel (n-1)

– sommeFactoriel (n-2) ) ;

return sommeFactoriel (n-1) + factorieln ;

}

}

67

public int sommeFactoriel(int n){

int factorieln , somme ;

if (n<=1) {

return n+1;

}

else {

somme = sommeFactoriel (n-1) ;

factorieln= n*(somme–sommeFactoriel(n-2)) ;

return somme + factorieln ;

}

}

68

public class DeuxEntiers {

int somme ;

int factoriel;

DeuxEntiers factorieletSommeFactoriel (int n) {

DeuxEntiers resultat ;

if (n==0) {

resultat.somme = 1 ;

resultat.factoriel = 1 ;

return resultat ;

}

else {

resultat = factorieletSommeFactoriel(n-1);

resultat.factoriel = n*resultat.factoriel;

resultat.somme = resultat.somme +

resultat.factoriel ;

return resultat ;

69

}

}

}

public int sommeFactoriel (int n) {

DeuxEntiers resultat ;

resultat=factorieletSommeFactoriel(n) ;

return resultat.somme ;

}

70

Parmi les méthodes récursives vues en exemple

quelles sont celles dont on peut maintenant

calculer la complexité?

(cid:122)Factorielle

(cid:122)Tri

(cid:122)Tours de Hanoi

(cid:122)Les nombres de Fibonnacci

(cid:122)Mais pas la recherche dichotomique

71

Le cas de Fibonacci

(cid:122)On obtient une complexité exponentielle

pour la programmation récursive.

(cid:122)Il existe des programmations plus

efficaces du calcul du nième nombre de

Fibonacci.

72

Fibonacci V2

public int fibonacci(int n ){

int i =2;

int fiMoins2 = 0 ;

int fiMoins1 = 1 ;

int fi = 1 ;

// f(0) = 0

// f(1) = 1

// f(2) = 1

for (int i =3 ; i < n+1 ; i++) {

// mise à jour de fiMoins2 et de fiMoins1

fiMoins2= fiMoins1;

fiMoins1= fi;

fi= fiMoins2 + fiMoins1;

// calcul de fi

// fi est égal au ième terme de la suite

} ;

// fi est le nième terme de la suite pour tout n > 0

if (n==0) return 0 ;

else return fi ;

}

73

Complexité de la V2

(cid:122)Cette fois la complexité est linéaire

74

Méthode Rapide

(cid:122)On utilise une autre relation d’induction

+

F

F

F

=

2

2

2

k

F

k

2(

F

=

k

+

+

1

F

k

2

1

+

(cid:122)On décompose n en base 2

+

1

k

k

)

F

k

+

1

n

=

p

1

−

∑

i

=

0

décomposit

ion

2][

i

i

(cid:122)La suite d0=1, di=2di1+decomposition(p-i),

est telle que dp=n. On calcule les fdi.

75

Calcul des nombres de Fibonacci V3

public int[] decompose(int n) {

int p =⎡log2 n⎤ ;

int auxiliaire = n ;

int[p] decomposition ;

for (int indice = 0 ; indice < p,

indice ++) {

decomposition[indice] = auxiliaire

mod 2 ;

auxiliaire = auxiliaire / 2;

}

return decomposition ;

}

76

Calcul Des Nombres De Fibonacci V3

public int fibonacci (int n) {

int a =0 ;int b =1 ;

int p = ⎡log2 n⎤ ;

int auxiliaire ;

int [p] decomposition = decompose (n) ;

for (int indice =1 ; indice < = p ;

indice++){

auxiliaire = a ;

a = aa + bb;

b = (2auxiliaire+b)b;

if (decompose(p-indice)==1 ) {

b = a+b ; a = b-a ;

}

if (n== 1) return 1;

else return a ;

77

}

}

Analyse de la version 3

(cid:122)Cette fois la complexité est en log(n)

78

Et la recherche dichotomique ?

(cid:122)On va considérer un cas plus général

79

Solutions de type diviser pour régner

(cid:122)Pour résoudre un problème de taille n on

divise le problème en a problèmes de taille

n/b et chaque sous-problème est résolu

récursivement

(cid:122)La phase de division et combinaison des

résultats partiels a une complexité en f(n)

80

L ’équation de récurrence des

solutions diviser pour régner

(cid:122)T(1) = constante

(cid:122)T(n) = a T(n/b) + f(n)

81

Théorème

(cid:122)T(n) peut alors être borné asymptotiquement

comme suit :

(cid:122)Si f(n)= O(nlogba-e) pour une constante e>0,

alors T(n) = Θ(nlogba).

(cid:122)Si f(n)= Θ(nlogba) , alors T(n) = O(logn nlogba).

(cid:122)Si f(n)=Ω(nlogba+e )pour une constante e>0, et

si af(n/b) < cf(n) pour une constante c<1 alors

T(n) = Θ(f(n))

82

Lemme 1

(cid:122)T(n)=T(bk)=Θ(nlogba)+

j

bnfa∑

/

(

k

1

−

j

=

0

(cid:122)Posons g(n)=

j

bnfa∑

(

/

j

)

k

1

−

j

=

0

j

)

83

Lemme 2

(cid:122)Si f(n)= O(nlogba-e) pour une constante e>0,

alors g(n))= Ο(nlogba).

(cid:122)Si f(n)= Θ(nlogba) ,

alors g(n) =O(logn nlogba).

(cid:122)Si af(n/b) < cf(n) pour une constante c<1

alors g(n) = Θ(f(n))

84

Si f(n)= O(nlogba-e) pour une constante

e>0, alors g(n)= Ο(nlogba).

(cid:122) On a alors

(cid:122) Or

a

1

k

−

∑

0

j

=

log

n

=

⎛

⎜

)( O

ng

=

⎜

⎝

k

1

−

a

∑

j

0

=

j

⎛

⎜

⎝

n

j

b

⎞

⎟

⎠

(

log

)

eab

−

⎞

⎟

⎟

⎠

j

n

j

b

⎛

⎜

⎝

eab

−

j

a

eab

−

log

(

log

)

eab

−

⎞

⎟

⎠

log

eab

−

=

n

k

1

−

∑

j

0

=

b

log

eab

−

(

b

je

)

=

k

1

−

∑

j

0

=

n

e

e

n

b

1

−

1

−

85

Exemple d’application du cas 1

(cid:122)Recherche dichotomique du maximum

(cid:122)c(n)=2c(n/2)+1

86

Si f(n)= Θ(nlogba), alors

g(n) =O (logn nlogba).

On obtient cette fois

ng

)(

=

⎛

k

1

−

⎜

a

∑Θ

⎜

j

0

=

⎝

j

⎛

⎜

⎝

n

j

b

⎞

⎟

⎠

(

log

)

ab

⎞

⎟

⎟

⎠

Or

(

log

)

ab

⎞

⎟

⎠

log

ab

=

n

a

log

(

k

1

−

∑

j

0

=

b

j

)

ja

b

j

n

⎛

⎜

j

b

⎝

ab

a

1

k

−

∑

0

j

=

log

n

=

1

k

−

j

1

∑ =

j

0

=

log

ab

n

nk

=

log

ab

log

( )n

b

87

Exemple de ce cas

(cid:122)Le tri dichotomique

(cid:122)c(n)=2c(n/2)+n

88

Si af(n/b) < cf(n) pour une constante c<1

alors g(n) = Θ (f(n))

)(

ng

1

k

−

∑≤

0

j

=

j

fa

n

j

b

⎛

⎜

⎝

⎞

1

k

−

( )

j

nfc

∑≤⎟

⎠

0

j

=

≤

( )

nf

1

c

−

89

On se propose de multiplier entre eux des

grands nombres.

a) Si l’on utilise la méthode naïve, combien

de multiplications élémentaires sont

effectuées ?

90

Soient U et V deux nombres de 2n chiffres

en base B.

On peut donc écrire

U=U1Bn+U2 et

V=V1Bn+ V2 où

U1,U2 ,V1, V2 sont des nombres à n chiffres

en base B.

91

b) On utilise l’égalité :

(U1 Bn +U2 )(V1 Bn+ V2 ) =

U1 V1 B2n + (U1V2 + U2 V1) Bn + U2 V2

pour calculer récursivement la multiplication.

C’est à dire que l’on ramène le problème

d’une multiplication de deux nombres de

2n chiffres à celui de 4 multiplications de

deux nombres de n chiffres, 4 décalages

et trois additions.

92

On suppose qu’additions et décalages

s’effectuent en Θ(n). Établir une relation

de récurrence permettant d’évaluer la

complexité de cet algorithme récursif de

multiplications et la résoudre.

93

c) On utilise maintenant l’égalité

(U1 Bn + U2 )(V1 Bn + V2 ) =

U1 V1 B2n +((U1 - U2 )(V2 - V1 ) + U2 V2 + U1 V1 Bn +

U2 V2

pour calculer récursivement la multiplication. C’est à

dire que l’on ramène le problème d’une multiplication

de deux nombres de 2n chiffres à celui de 3

multiplications de deux nombres de n chiffres, 5

décalages et 6 additions. On suppose qu’additions et

décalages s’effectuent en Θ(n). Établir une relation

de récurrence permettant d’évaluer la complexité de

cet algorithme récursif de multiplications et la

résoudre.

94

On se propose dans cet exercice de calculer

la complexité de plusieurs algorithmes

dont le but est de fusionner les p listes

triées de longueur n contenues dans un

tableau de listes en une seule liste triée de

longueur np.

95

On suppose définie une classe Liste

contenant entre autre une méthode

permettant de fusionner une liste l1 triée

de longueur n1 et un liste triée l2 de

longueur n2 dont la signature est

public static Liste fusion (Liste l1, Liste l2)

et la complexité est en Θ(n1+n2).

96

Déterminer la complexité de la méthode

suivante en fonction de n et de p.

public static Liste fusionMultiple(Liste[]

mesListes) {

Liste L=mesListes[1];

for (int i=2; i < mesListes.length; i++){

L= Liste.fusion(L,mesListes[i]);

}

return L;

}

97

On suppose maintenant que p est une puissance de 2 et l’on

propose maintenant d’utiliser l’algorithme de multifusion

récursif suivant :

Pour multifusionner p listes de taille n

Si p=2 utiliser fusion

Sinon

Multifusionner (récursivement) les p/2 première listes

Multifusionner (récursivement ) les p/2 dernières listes

Utiliser fusion pour fusionner le résultat des deux

premières étapes.

98

Soit c(n,p) = la complexité de la fusion de p

listes de taille n par cette méthode.

Déterminez la relation de récurrence suivie

par cette suite, ainsi que c(n,2).

99

(cid:122) Posez d(n,p)=c(n,p)/n.

(cid:122) Déterminez la relation de récurrence suivie par

cette suite.

(cid:122) Montrez que d(n,p) ne dépend pas de p. On

pourra montrer par induction sur p que pour tout

p >=2, d(n,p)=d(1,p) pour tout n >0.

(cid:122) Posez d(1,p)=f(p), et déterminez l’équation de

récurrence suivie par f(p). Résoudre cette

équation. En déduire c(n,p).

100

(cid:122)On considère le programme java récursif

suivant où b est une constante entière

(cid:122)On suppose défini un objet table à partir

d’une classe Table dérivée de la classe

Vector en y ajoutant la méthode

table.echanger (int i, int j)

qui échange table.elementAt(i) et

table.elementAt(j).

101

public void T(int debut, int fin){

// opère sur la Table table dans la tranche

table[debut..fin]

int n=fin-debut+1 ; // la dimension de la tranche

if (n>1) {

if (n=2) {

// tri par ordre croissant des deux éléments de la tranche

if (table.elementAt(debut) >

table.elementAt(fin)){

table.echanger(debut, fin) ;

}

}

else {

T( debut, debut+n/b) ;

T( fin-n/b, fin) ;

T(debut, debut+n/b) ;

}

}

}

102

(cid:122) Établir la relation de récurrence vérifiée

par la complexité de cet algorithme

(cid:122) Si b=3/2, (dans ce cas bien sûr

l’algorithme utilise la partie entière de

n/b) quelle en est la complexité ?

(cid:122) Question bonus : démontrer que si

b=3/2, T est un tri

103