[ALGO] Complexite des algorithmes (5)

Complexite de Heapify

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)

Mesurer la taille du sous-probleme considere

Ligne de code Cout
l <- LeftChild(i)
r <- RightChild(i)
if l < n and A[l] > A[i]
largest <- l
largest <- i
if r < n and A[r] > A[largest]
largest <- r
if largest != i
A[i] <-> A[largest]
Heapify(A, largest, n)

Au pire,

Le theoreme general fonctionne pour avec a=1 b=(3/2) et

Complexite de BuildHeap

BuildHeap(A, n):
    for i <- n/2 down to 0
        Heapify(A, i, n)
Ligne de code Cout
for i <- n/2 down to 0
Heapify(A, i, n)

avec a la louche

S(h, n) est le nombre de sous-arbres de hauteur h dans un arbre de n noeuds.

Donc Heapify(A, i, n) a un cout de

Complexite de HeapSort

HeapSort(A, n)
    BuildHeap(A, n)
    for i <- n - 1 down to 1
        A[i] <-> A[0]
        Heapify(A, 0, i)
Ligne de code Cout
BuildHeap(A, n)
for i <- 0 down to 1
A[i] <-> A[0]
Heapify(A, 0, i)


Formule de Stirling

Donc


QuickSort

QuickSort(A,b,e)
//trie A[b...e-1]
    if e - b > 1:
        m = Partition(A,b,e)
        QuickSort(A,b,m)
        QuickSort(A,m,e)
Partition(A,b,e):
    i <- b - 1; j <- e; p = A[b]
    for ever:
        do ++i until A[i] >= p
        do --j until A[j] <= p
        if i > j
            A[i] <-> A[j]
        else
            return i + (b == i)

Partition - fonctionnement

(2) 4 8 6 1 7 5 3
1 4 8 6 2 7 5 3
(4) 8 6 2 7 5 {3}
3 [8] 6 {2} 7 5 4
3 2 [6] {8} 7 5 4
etc

(x) : pivot [i] et {j}

Cout Partition

Ligne de code Cout ())
i <- b - 1; j <- e; p = A[b]
for ever:
do --j until A[j] <= p
if i > j
A[i] <-> A[j]
return i + (b == i)

Cout QuickSort

Ligne Cout ()
| n > 1
|
0 |
0 |
0 |

Tableau trie :

Cas favorable :
On suppose toutes les partitions de la forme |50%|50%|

Autre cas :
On supprime toutes les partitions de la forme |10%|90%|







hierarchy



cn

cn



cn/10

cn/10



cn->cn/10





9cn/10

9cn/10



cn->9cn/10





cn/100

cn/100



cn/10->cn/100





9cn/100

9cn/100



cn/10->9cn/100





9cn/100 

9cn/100 



9cn/10->9cn/100 





81cn/100

81cn/100



9cn/10->81cn/100





...

...



cn/100->...





... 

... 



81cn/100->... 





Θ(1)

Θ(1)



...->Θ(1)





 ...

 ...



... -> ...





Θ(1) 

Θ(1) 



 ...->Θ(1) 





Donc

Autre cas :
|20|n-20|