[ALGO] Complexite des Algorithmes (1)

// cours pdf

QCM

NOTE ATELIER ALGO


Problematique

Algorithme : sequence d’instruction qui resoud un probleme

Problemes :

Complexite temporelle d’un algorithme : = temps pour resoudre un probleme de taille

Faire des choix entre des algos, ou des predictions sur le comportement des algo avec un n donne

On a
Donc
Donc


Les sommes

Formule de la somme :


Avec




Les logarithmes

ou car



ou

car

(nb de chiffers devant la virgule - 1)
Donc


car

car et

-> decale la virgule de l’autre cote de l’equation


Exemples concrets

void fun(int n)
{
    for (int i = 5; i <= n; ++i)
    {
        puts("A");
        for (int j = 10; j < 20; ++j)
            puts("B")
        for (int j = 1; j < i; ++j)
            puts("C");
        for (int j = 10; j < i; ++j)
            puts("D");
    }
}

Calculer combien de fois chaque lettre est affichee ?

Avec 10


Avec n quelconque


for (int i = 1; i < n; ++i)
    for (int j = 1; j < i; j += 2)
        puts("E");

Comment calculer E(n) ici ?

On a j = 1, 3, 5, 7, 9… < i
Changement de variable avec :
(partie entiere sup)

-> On prend la partie entiere superieure de x
-> On prend la partie entiere inferieure de x

for (int i = 1; i < n; ++i)
    for (int k = 0; k < (i - 1) / 2; ++k)
        puts("E");

Si n est pair, tous les termes sont en double

Si n est impair