Evaluating Complexity

Big Oh 1

Evaluer la complexité de chaque code suivant:

//a)
int sum = 0; 
for(int i=0; i<=N+2; i++)
    sum++;

for(int j=1; j<=N*2; j++)
    sum += 5;
cout << sum << endl;

//b)
int sum = 0;
for (int i = 1; i <= N - 5; i++)
    for(int j = 1; j<= N-5; j+=2)
        sum++;
cout<< sum <<endl;

//c)
int sum = N;
for(int i = 0; i < 100000; i++)
{
    for(int j = 0; j <= i; j++)
        sum += N;

    for(int j = 1; j <= i; j++)
        sum += N;

    for(int j = 1; j <= i; j++)
        sum += N;
}

cout<< sum << endl;

//d)
Vector<int> list;
for( int i = 1; i <= N * N; i++)
{
    for(int j = 1; j <= N; j++)
        list.add( i + j);
}

for( int i = 1; i <= 2 * N; i++)
    list.remove( liste.size() - 1);

cout << "done!" << endl;

//e
HashSet<int> set1;
for( int i = 1; i <= N; i++)
    set1.add(i);

Set<int> set2;
for(int i = 1; i <= N; i++)
{
    set1.remove(i);
    set2.add(i + N);
}
cout << "done!" << endl;

Big Oh 2

<a name’bigOh2’>

Même question, évaluer la complexité pour chaque code:

// a)
int sum = 0;
for (int i = 1; i <= N - 2; i++)
{
    for (int j = 1; j <= i + 4; j++)
        sum++;
    sum++;
}

for( int i = 1; i <= 100; i++)
    sum++;

cout << sum << endl;

// b)
int sum = 0; 
for (int i = 1; i <= N; i++)
{
    for(int j = 1; j <= N * N; j++)
        sum++;
    
    for(int j = 1; j <= 100; j++)
        sum++;
    
    for(int j = 1; j <= N; j++)
        sum++;

    sum++;
}
cout << sum << endl;

//c)
int sum = 0;

for( int i = 1; i <= N; i++)
{
    for( int j = 1; j <= 100; j++)
        sum++;

}

for( int k = 1; k <= 1000; k++)
    sum++;

cout << sum << endl;

// d)
Set<int> set;
for (int i = 1; i <= N * 2; i++)
    set.add(i);

for(int k : set)
    cout << k << endl;
cout << "done!" << endl;

// e)
Vector<int> vec;
for( int i = 1; i <= N + 100; i++)
    vec.add(i);

Stack<int> stack;
while( !vec.isEmpty() )
{
    stack.push(vec[vec.size() - 1]);
    vec.remove(vec.size() - 1);
}

while( !stack.isEmpty() ) 
    stack.pop();

cout << "done!" << endl;

Big Oh 3

Evaluer la complexité des codes suivants:

// a)
HashSet<int> set1
for( int i= 0; i < N; i++)
    set1.add(i);


Set<int> set2;
for( int n : set1)
    set2.add(n);

cout << "done!" << endl;

//b)

Vector<int> list;

for( int i = 0; i < N; i++)
    list.insert(k0, i*i);

Set<int< set;
for (int k : list)
    set.add(k);

cout << "done!" <<endl;

// C
Vector<int> list1;
for(int  i = 0; i < N; i++)
    list1.add(i);

Vector<int> list2;
for(int i = 0; i < N; i++)
{
    list2.insert(0, list1[0]);
    list1.remove(0);
}

cout << "done!" << endl;

// d)
int sum = 0;
for (int i = 0; i < N * 2; i++)
    for(int j = 0; j < 100; j++)
        for(int k = 0; k < j*j*j; j++)
            sum++;
cout<< sum << endl;

// e)
int sum = 0;
for(int i = 0; i < N * 2; i++)
    for(int j = 0; j < i/2; j++)
        for(int k = 0; k < N*N; k++)
            sum++;
cout << sum << endl;

Le but de cette section, est de coder et de visualiser le temps d’exécution des deux algorithmes de recheches dans un tableau trié.

Le code de départ est dans search_simulation.zip

Comme première tache on va mesurer le temps d’exécution de la recherche linéaire. Ainsi dans le fichier tests.h, completer l’implémentation de la fonction

int linear_search( vecI & nums)
{
  
}

Adding Tests

Avant de mesurer le temps d’exécution de votre fonction, on doit s’assurer qu’elle est correcte. On va en profiter pour la notion de tests déja utilisée dans le cours. On va se limiter à une fonction de test simple de c++ qui est l’instruction assert dans la bibliothèque assert.h, sa syntaxe est la suivante:

assert( boolean expression);

Par exemple, l’instruction assert( 1 == 1), ne va rien afficher et va continuer, cependant, l’instruction assert( 1 == 0 ) va générer une erreur d’exécution.

Dans le header tests.h, vous trouverez une fonction ` void tests`. Le rôle de cette fonction est de vérifier si votre fonction renvoie un résultat correcte.

void tests(int (*F)(vecI &, int) )
{

}

Par exemple on peut ajouter le code suivant pour tester notre fonction:

//Vecteur simple
vecI nums{1,2,7, 8, 9, 12};

//calculer la valeur de la fonction de recherche pour 8
auto index = F(nums, 8)

//S'assurer que index est 3
assert( index == 3);

//Afficher un message de success
cout << "Test 1 success" << endl;

Votre rôle est d’ajouter d’autres tests pour être rigoureux:

  • Ajouter un test qui ne trouve pas de valeur.
  • Ajouter un test où le tableau est vide.
  • Ajouter un test où la valeur est à la fin.
  • Ajouter un test conteant 10 valeurs.

Timing your function

Maintenant qu’on a assuré que notre fonction est correcte, on dois mesurer son temps d’exécution. On sait déja qu’elle est linéaire, cependant on va mesurer cet aspet.

Afin de mesurer le temps d’exécution en c++, on utilise la classe high_resolution_clock de la bibliothèque chrono. Cette d’obtenir l’heure du système avec une grande précision.

Chercher la documentation de cette fonction, pour obtenir le temps d’exécution d’une fonction.

Ainci dans le fichier simulation.cpp, compléter le code de cette fonction.

double timing(int(*F)(vecI &, int), vecI & nums, int target)
{
    //Mesurer le temps de la fonction F pour chercher target dans le vecteur
    // nums
}

Maintenant, on paut passer à l’implémentation de la fonction de recherche dichotomique. Ainsi, dans le fichier tests.h, implémenter cette recherche dans la fonction binary_search.

Pour tester votre function changer l’appel de test par

tests(&binary_search)

Side By Side simulation

finalement, vous avez deux versions de recherche qui sont correctes. Votre dernière question consiste à générer une table des temps d’exécution de chaque fonction.

Vous commencer de \(N=100\) et à chaque fois, vous doubler cette taille.

Size Time linear
 time binary
100
200
400
...
6400