[ALGO] Complexite des algorithmes (3)

// cours pdf

Complexites

= une fonction quadratique
= une fonction lineaire

Exemple

:





: Une fonction qui domine une fonction lineaire

Exemple :

Combinaisons

Ex:




Definitions

Definition

Exemple :
Montrer que
, avec et


Definition

Exemple : Montrer que
Car avec et

Montrer que
Car avec et

Montrer que
Car avec et


Definition

Exemple :
Montrer que
avec

Notations

On note au lieu de par abus de notation.

De meme, signifie tel que


Ces equations se lisent de gauche a droite

On a mais pas


Algorithmes de tri

SelectionSort

SelectionSort(A, n) : 
    for i <- 0 to n - 2
        posmin <- i
        for j <- i + 1 to n - 1
            if A[j] < A[posmin]
                posmin <- j
        A[posmin] <-> A[i]
Ligne de code Ordre de grandeur
for i <- 0 to n - 2
posmin <- i
for j <- i + 1 to n - 1
if A[j] < A[posmin]
posmin <- j (borne sup)
A[posmin] <-> A[i]
Total

InsertionSort

InsertionSort(A, n):
    for i <- 1 to n - 1
        key <- A[i]
        j <- i - 1
        while j >= 0 and A[j] > key 
            A[j+1] <- A[j]
            j <- j - 1
        A[j + 1] <- key
Ligne de code Ordre de grandeur
for i <- 1 to n - 1
key <- A[i]
j <- i - 1
best | worst | any
while j >= 0 and A[j] > key
A[j+1] <- A[j]
j <- j - 1
A[j + 1] <- key
Total

En general on peut dire


Cette notation ne garantit pas qu’un cas est quadratique !!

MergeSort

MergeSort(A, b, e):
    if e - b > 1:
        m <- b + (e - b) / 2
        MergeSort(A, b, m)
        MergeSort(A, m, e)
        Merge(A, b, m, e)
Merge(A, b, m, e):
    i <- b; j <- m
    for k <- b to e - 1
        if j >= e or (i > m and A[i] <= A[j])
            B[k] <- B[i]; <ins>i
        else
            B[k] <- B[j]; <ins>j
    A[b...e-1] <- B[b...e-1]
            

Ou b = begin et e = end
On travaille sur la zone du tableau entre [b,e[

On pose n = e-b

Merge Ordre de grandeur
i <- b; j <- m
for k <- b to e - 1
if j >= e or (i > m and A[i] <= A[j])
B[k] <- B[i]; i
B[k] <- B[j]; j
A[b…e-1] <- B[b…e-1]
Total
MergeSort Ordre de grandeur
if e - b > 1
m <- b + (e - b) / 2
MergeSort(A, b, m)
MergeSort(A, m, e)
Merge(A, b, m, e)
Total

Pour simplifier, supposons
Alors pour n > 1

Arbre des appels recursifs (avec tableau de taille n)







hierarchy



cn

cn



cn/2

cn/2



cn->cn/2





cn/2 

cn/2 



cn->cn/2 





cn/4

cn/4



cn/2->cn/4





cn/4 

cn/4 



cn/2->cn/4 





 cn/4

 cn/4



cn/2 -> cn/4





 cn/4 

 cn/4 



cn/2 -> cn/4 





...

...



cn/4->...





Θ(1)

Θ(1)



...->Θ(1)





 Θ(1)

 Θ(1)



...-> Θ(1)





On a n feuilles

Chaque ligne a un cout de et la derniere

Hauteur de l’arbre :

Donc

? Yes