Ecriture en O(...)
Classification des algorithmes
Recherche dichotomique :

But : pouvoir comparer deux algorithmes

temps d'exécution
place occupé en mémoire (par le programme + les données)
performance garantie ou moyenne ?
dans quel cas ? (nombre de données, …)
complexité d'écriture de l'algorithme

Coût approximatif d'une opération :

i = 1;       // 1 opération (affectation)
i = j + 1;  // 2 opérations (addition+affectation)
k = t[ i ];  // 2 opérations (accès tableau+affectation)
a = 2*k + t[i+3]; // 5 opérations 

if (i<2)          // 2 opérations
{  i=i+3;   }    // 2 opérations
else
{   i=(2*i)-(7*j);   }    // 4 opérations
                 => meilleur cas : 4 opérations (i<2)
                 => pire cas : 6 opérations (i>2)
                 => cas moyen : (6+4)/2 = 5 opérations (dépend de i)

for (i=0; i<10; i++)   // 1 + 2 + 1
{
     s=s+1; // 2 opérations
}
     => initialisation 1 opération
     => 10 boucles : (test + incr + calcul) x 10
     => test de sortie 2 opérations
     => TOTAL : 53 opérations

for (i=0; i initialisation 1 opération
     => n boucles : (test + incr + calcul) x n
     => test de sortie 2 opérations
     => TOTAL : 5n + 3 opérations

Ecriture en O(...)

pour comparer 2 algorithmes, on ne comparera que les facteurs les plus significatifs (pour un n suffisamment grand)

⇒ n² plus significatif que n ou toute autre constante

O(5n²+3n+3) = O(n²)

Classification des algorithmes

O(1)
O(log(n))
O(n)
O(n.log2(n))
O(n²)
O(n^3)
.........
O(x^n)
O(n!) --> catastrophique

Quelques exemples simples :

chercher la plus grande valeur dans un tableau de n valeurs non trié : O(n)
chercher si une valeur est présente dans un tableau non trié
- meilleur cas : O(1)
- pire cas : O(n)
- cas moyen : O(n/2) = O(n)
chercher la moyenne des valeurs d'un tableau de n x m valeurs : O(n*m)

Recherche dichotomique :

Pb : cherche si une valeur est présente dans un tableau DEJA TRIE par ordre croissant Algorithme :

class TableauTrie
{
     int tab[];
     ...
     public int chercher(int valeur)
     {
          //recherche dichotomique retourne le n° de la case si trouvée -1 sinon
          int ig, id; // index gauche et droit
          ig = 0;
          id = tab.length - 1;
          while(ig!=id)
          {
               if (tab[(ig+id)/2]==valeur)
               {
                    return ((ig+id)/2); //trouvé
               }
               if (tab[(ig+id)/2] > valeur)
               {
                    id = (ig+id)/2;
               }
               else
               {
                    ig = (ig+id)/2;
               }
          }
          return (-1); // pas trouvé
     }
}

Complexité au pire des cas : O(log2(n))