• Le plus souvent le temps de calcul est le plus important
• Dans le pire des cas; donc chercher un majorant
• Analyse souvent facile, souvent difficile
• Quelquefois impossible

• Le temps (ou espace) dépend des entrées; pas de majorant universel
• considérer le temps comme fonction de la taille n des entrées, en nombres, bits, caractères; chercher à majorer cette fonction
• souvent exprimé t(n)=O(f(n)) c'est-à-dire il existe N et c tels que si n > =N, alors t(n) < =cf(n)
• aussi o, ω, Ω, Θ

• Ici, nous considérons l'analyse du temps d'un algorithme donné
• La complexité d'un problème peut être défini (approximativement) comme la complexité du meilleur algorithme possible qui le résout
• l'analyse d'un algorithme fournit un majorant de la complexité du problème
• Trouver un minorant est, le plus souvent, beaucoup plus difficile ...

• Une boucle de 1 à n prend temps O(n)
• Deux boucles imbriquées de 1 à n prennent temps O(n²), etc.
• Recherche dichotomique sur n possibilités, temps O(logn)
• Algorithme d'Euclide pour pgcd(m,n) (supposons m > =n); m remplacé en 2 itérations par m mod n, soit dans le pire des cas [ (m-1)/2 ];
  donc O(logn); est-ce vraiment possible ?

• chercher quelque chose: s'il y a une borne évidente sur le nombre de cas à considérer, ça donne un majorant mais peut-être très grossier
• processus itératif qui converge, peut-être, très lentement
• boucles très simples mais où le calcul du nombre d'itérations semble trèèès difficile

  tantque (n>1)
     si (n~pair) alors n:=n/2;
                 sinon n:=3n+1
     finsi
  fintantque
  
  

  Personne ne sait si ça s'arrête pour tout n positif!

• Exemple le problème 3SAT:
  expression booléenne qui est la conjonction de clauses de la forme (u ou v ou w) où u etc. sont de variables ou négations de variables
• algorithme brut: considérer les 2ⁿ affectations possibles des n variables
• meilleur: trois sous-problèmes : u vrai, u faux mais v vrai, u et v faux mais w vrai
• taille des sous-problèmes n-1, n-2, n-3
• majorant donné par t(n)=t(n-1)+t(n-2)+t(n-3)
• t(n)=O(αⁿ) où α est la (plus grande des) racine(s) de xⁿ=x^n-1+x^n-2+x^n-3, ou 1=x^-1+x^-2+x^-3 ( < 2)
• (pas optimal)

• T(n)=Θ(n^log_b(a)) si f(n) (suffisamment) plus petit
• T(n)=Θ(n^log_b(a)log_b(a)) si f(n)=Θ(n^log_b(a))
• T(n)=Θ(f(n)) si f(n) (suffisamment) plus grand que n^log_b(a) et f(n) (suffisamment) plus grand que af(n/b).

``suffisamment'' défini exactement dans le livre
existence de cas qui ne sont pas couverts par ces 3 règles

• Souvent le meilleur algorithme connu est Θ(2ⁿ) (SAT)
• Rarement n! (isomorphisme de (sous-)graphes)
• Ou αⁿ avec α ≠ 2
• Ou 2^√n

• Pour un algorithme seul, l'analyse dans le pire des cas est (probablement) la plus importante
• pour une fonction qui va être appelée plusieurs fois par un algorithme plus grand, c'est peut-être la moyenne
• Mais ceci ne peut donner qu'un majorant probabiliste pour l'algorithme
• Si on peut démontrer que le pire comportement de la fonction ne se produit que rarement dans le fonctionnement du program, cela donne un majorant déterministe amorti
• par exemple, une fonction de mise à jour d'une structure de données