Rappels

Soit T(n) le nombre d’instructions associe a un algorithme A. Soit f(n) une fonction qui admet en parametre n. T(n) est dite en O(f(n)) s’il existe deux constantes n₀ et k tel que:

Soit T(n) le nombre d’instructions associe a un algorithme A. Soit f(n) une fonction qui admet en parametre n. T(n) est dite en Ω(f(n)) s’il existe deux constantes n₀ et k tel que:

Soit T(n) le nombre d’instructions associe a un algorithme A. Soit f(n) une fonction qui admet en parametre n. T(n) est dite en Θ(f(n)) s’il existe trois constantes n₀ et k et c tel que:

Calculer le nombre d'opérations pour: unsigned int f(unsigned int N){ while(N>0){ N--; } return N; }

Calculer le nombre d'opérations pour: unsigned int f(unsigned int N){ return 0; }

Calculer le nombre d'opérations pour: unsigned int f(unsigned int N){ int c = 0; while(N>0){ if(N%2 == 0){ c++; } N = N/2; } }

Calculer le nombre d'opérations pour: unsigned int f(unsigned int N){ int c = 0; while(N-->0){ for(int i=1; i<N; i++){ c += 1; } } return c; }

Calculer le nombre d'opérations pour: unsigned int f(unsigned int N){ while(random()!=N){ N = N+1-1; } return N; }

Calculer le nombre d'opérations pour: unsigned int fibonacci(unsigned int N){ int i2 = 0; int i1 = 1; if(N<=1) return N; int j = 1; while(j<N){ int tmp = i2 + i1; i2 = i1; i1 = tmp; j++; } return i1; }

Calculer le nombre d'opérations pour le crible d'Ératosthène du TD1 ainsi que les valeurs correspondantes pour la O, Ω et Θ.

Calculer le nombre d'opérations pour l'exercice de calculatrice à notation polonaise inversée du TD2 ainsi que les valeurs correspondantes pour la O, Ω et Θ.

Calculer le nombre d'opérations pour l'exercice de recherche du plus grand carré du TD1 ainsi que les valeurs correspondantes pour la O, Ω et Θ.