[ALGO] Complexite des algorithmes (4)

Methode par substitution

Apres substitution :

La recursion s’arrete quand Alors

Theoreme general

Theoreme general pour resoudre les equations de complexite rescursive de la forme

Avec

(Pour )

Applications

Avec et

? Ici


Avec et

si


Avec et

si et de plus avec on a bien


Avec

>> d n’existe pas

Par substitution :

Apres substitutions :

quand

Donc

HeapSort

Arbre parfait

C’est un arbre binaire dont tous les niveaux sont pleins sauf le dernier ou toutes les feuilles sont a gauche.

Peuvent etre stockes dans un tableau sans pointeur

100 19 36 17 3 25 1 2 7
0 1 2 3 4 5 6 7 8
LeftChild(i) = 2i + 1
RightChild(i) = 2i + 2
Parent(i) = ⌊(i - 1) / 2⌋

Tas Max

C’est un arbre parfait ou chaque sommet est plus grand que ses fils Plusieurs Tas Max peuvent representer le meme ensemble de valeurs







hierarchy



9

9



8

8



9->8





7

7



9->7





3

3



8->3





4

4



8->4





6

6



7->6





5

5



7->5





1

1



3->1





0

0



3->0





2

2



4->2











hierarchy



9

9



8

8



9->8





7

7



9->7





3

3



8->3





4

4



8->4





6

6



7->6





5

5



7->5





1

1



3->1





0

0



3->0





2

2



4->2





Suppression du max

On supprime l’element max qu’on remplace par le dernier element du tableau, puis on permute avec son plus grand fils recursivement







hierarchy



1

1



7

7



1->7





8

8



1->8





5

5



7->5





6

6



7->6





4

4



8->4





2

2



8->2





3

3



5->3





0

0



5->0











hierarchy



8

8



7

7



8->7





4

4



8->4





5

5



7->5





6

6



7->6





1

1



4->1





2

2



4->2





3

3



5->3





0

0



5->0











hierarchy



0

0



7

7



0->7





4

4



0->4





5

5



7->5





6

6



7->6





1

1



4->1





2

2



4->2





3

3



5->3











hierarchy



7

7



6

6



7->6





4

4



7->4





5

5



6->5





0

0



6->0





1

1



4->1





2

2



4->2





3

3



5->3





L’idee du tri par tas :

  1. Construction du tas pour les valeurs a trier
  2. Retirer les max les uns apres les autres pour remplir le tableau par la droite

Construire un tas

Exemple : 2 3 1 4 5 7 0 9 6 8







hierarchy



2

2



3

3



2->3





1

1



2->1





4

4



3->4





5

5



3->5





7

7



1->7





0

0



1->0





9

9



4->9





6

6



4->6





8

8



5->8











hierarchy



2

2



3

3



2->3





1

1



2->1





4

4



3->4





8

8



3->8





7

7



1->7





0

0



1->0





9

9



4->9





6

6



4->6





5

5



8->5











hierarchy



2

2



3

3



2->3





1

1



2->1





9

9



3->9





8

8



3->8





7

7



1->7





0

0



1->0





4

4



9->4





6

6



9->6





5

5



8->5











hierarchy



2

2



3

3



2->3





7

7



2->7





9

9



3->9





8

8



3->8





1

1



7->1





0

0



7->0





4

4



9->4





6

6



9->6





5

5



8->5











hierarchy



2

2



9

9



2->9





7

7



2->7





6

6



9->6





8

8



9->8





1

1



7->1





0

0



7->0





4

4



6->4





3

3



6->3





5

5



8->5











hierarchy



9

9



8

8



9->8





7

7



9->7





6

6



8->6





5

5



8->5





1

1



7->1





0

0



7->0





4

4



6->4





3

3



6->3





2

2



5->2





Heapify

Sommet i tel que le FD et FG sont des fils >> Le sommet i est la racine d’un tas

Heapify(A, i, n):
    l <- LeftChild(i)
    r <- RightChild(i)
    if l < n and A[l] > A[i]
        largest <- l
    else
        largest <- i
    if r < n and A[r] > A[largest]
        largest <- r
    if largest != i
        A[i] <-> A[largest]
        Heapify(A, largest, n)
BuildHeap(A, n):
    for i <- n/2 down to 0
        Heapify(A, i, n)
HeapSort(A, n)
    BuildHeap(A, n)
    for i <- n - 1 down to 1
        A[i] <-> A[0]
        Heapify(A, 0, i)