Scribd
Importer
44 vues6 pages

Évaluation et Complexité des Arbres Binaires

L'exercice contient 4 exercices sur les arbres binaires et l'analyse algorithmique. L'exercice 1 présente la structure d'un arbre binaire. L'exercice 2 décrit un algorithme pour créer l'arbre binaire miroir. L'exercice 3 analyse la complexité de quelques algorithmes. L'exercice 4 analyse la complexité de plusieurs séquences.

Transféré par

benyahia
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
44 vues6 pages

Évaluation et Complexité des Arbres Binaires

L'exercice contient 4 exercices sur les arbres binaires et l'analyse algorithmique. L'exercice 1 présente la structure d'un arbre binaire. L'exercice 2 décrit un algorithme pour créer l'arbre binaire miroir. L'exercice 3 analyse la complexité de quelques algorithmes. L'exercice 4 analyse la complexité de plusieurs séquences.

Transféré par

benyahia
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Exercice 1

1/

+
^ *
- 2 / 6
x 3
* 4
y cos(x)

2/ La déclaration

Type

Arbre=^noued

Nœud= structure

Info :chaine ;

Fd,fg :arbre ;

Fin ;

3/

Grd :
x-3^2+y*cos(x)/4*6
rgd :
+^-x32*/*ycos(x)46
Gdr
X3-2^ ycos(x)*4/6*+
4/

Function evaluer(a:arbre):réel

Debut

Si a^.info=’+’ alors retourner ( evaluer(a^.fg)+evaluer(a^.fd))

Sinon Si a^.info=’-’ alors retourner ( evaluer(a^.fg)-evaluer(a^.fd))

Sinon Si a^.info=’*’ alors retourner ( evaluer(a^.fg)*evaluer(a^.fd))

Sinon Si a^.info=’/’ alors retourner ( evaluer(a^.fg)/evaluer(a^.fd))

Sinon Si a^.info=’^’ alors retourner ( evaluer(a^.fg)^evaluer(a^.fd))

Sinon retourner(a^.info)

Fin ;

Exercice 2
20

15 25

14 18 22 26

16

1/Oui est un abr car pour chaque nœud , a^.fg.info < a^.info< a^.fd.info

2/

Déclaration en c :

typedef struct noeud

int info;

struct noeud *fg;

struct noeud *fd;

}
Le déroulement :

Quefait(20)

Echanger(^15 , ^25) X

Quefait(20.fg)

Quefat(20.fd)

20

25 15

22 26 14 18

16

Quefat25)

Echabge(^22,^26)

Quefait(25.fg)

Quefat(25.fd)

20

25 15

26 22 14 18

16

Quefait(15)

Echanger(^14 ;^18)X

Quefat(15.fg)) X

Quefat(15.fd)
20

25 15

26 22 18 14

16

Quefait(18)

Echanger(^16 ;Null) X

Quefait(18.fg) X

Quefaut(18.fd) X

20

25 15

26 22 18 14

16

2/Cette procédure crée l’arbre miroir d’un arbre binaire


Exercice 3 :
Nous savons que les grandes valeurs de n déterminent le temps d’exécution
asymptotique, nous pouvons négliger la partie test ( si - alors) ( n <20)

le temps d’exécution de cette séquence est T(n)= T1(n) + nT3(n)

1/

T(n)=n+n(logn) ; O(nlogn).

2/ T(n)=0.6n²+n(logn) ; O(n²)

3/ T(n)= nlogn+n(2√𝑛 )= nlogn + 2n1.5 O(n1.5)

4/T(n)=nlog2n+n(5n²+2n+1) = nlog2n+5n3+2n²+n O(n3)

Exercice 4 :
S1 :
Pour : n fois
Tq : log2(n) fois
Et donc O(nlogn)
S2 :
La boucle est de tète jusqu’au la fin de la liste donc
O(n) ou n est la taille de la liste
S3 :
i j Nb fois
1-n n
n
1-n-1 n-1
n-1

…..
…
2 1-2 2

1 1-1 1

= 1+2+..+n
N(n+1)/2 = n²/2+n/2
Et donc O(n²)

S4 :
T(n)= ti(n)+tj(n)*tk(n)
= n+n(1+n(1+1+1))= 2n+3n² donc O(n²)
S5 :
Le pire de cas est que a est un arbre binaire gauche : donc O(n)
Ou n est la taille de l’arbre

Vous aimerez peut-être aussi