Ordonner
Ordonner les expressions suivantes de manière à ce que chacune soit en O de la $val22.
Donner l'ordre
Asymtotiquement en
, l'expression
est en
Complexité d'un algorithme
Donner le coût du programme suivant $val9 :
Coût et relation de récurrence
On a démontré que la fonction coût d'un algorithme en fonction d'instances de taille inférieure à
vérifie
Alors, l'algorithme est en
.
Ordre de grandeur
Vous voulez évaluer le temps nécessaire pour $val25 sur un processeur à 1GHz. - La complexité est en
- Pour
, en quelle unité allez-vous exprimer le résultat $m_enonce ?
Taille mémoire
$m_reply1 On applique un pivot de Gauss à une matrice de flottants
ayant 4 coefficients par ligne. Quelle taille mémoire utilise-t-on au maximum avant et après le pivot de Gauss? Quelle est en gros la taille maximale d'une telle matrice de flottants que l'on peut stocker dans un ordinateur avec 1Go de mémoire, avant et après pivot de Gauss?
Notations asymptotiques
Mettre les notations de gauche en correspondance avec leurs définitions
Comparaisons asymptotiques
Donner la conclusion : $val16
Taille maximale
$val11
Vocabulaire asymptotique
Mettre les notations de Landau de gauche en correspondance avec leurs dénominations :