Fonctions surface1 et surface2
Pour surface1: instruction à dénombrer (dans la boucle) : surface += longueur,
cette instruction est exécutée largeur fois.
Pour surface2: instruction à dénombrer (dans la boucle) : surface = longueur * largeur,
cette instruction est exécutée une seule fois.
Les deux fonctions fournissent le même résultat. La deuxième est beaucoup
plus efficace : en O(1).
Fonction somme
Instruction à dénombrer : total += v ; soit n la taille du tableau (n = len(tab)),
cette instructions est exécutée n fois. La complexité (en temps de calcul)
est en O(n).
Remarquer que l’ordinateur devine toujours en 7 essais au maximum.
L’instruction à dénombrer est nbessais += 1. A chaque itération, l’intervalle
[inf-sup] est divisé par 2. Cette instruction est donc exécutée log2(100) fois.
Ici 100 (l’intervalle de recherche) est la taille des données (n). L’algorithme
est en 0(log2(n)).
Pour une recherche entre 1 et 4000, log2(4000) = 12. Il faut donc modifier
le programme :
- la question : “entre 1 et 4000”,
- l’assertion au début :
assert nbmyst >= 1 and nbmyst <= 4000, - l’initialisation de sup :
sup = 4000, - et l’assertion finale
assert nbessais <= 12.