Réponses aux exercices

1.1 Supposons que vous ayez une liste triée de 128 noms et que vous la parcouriez à l’aide de la recherche binaire. Quel est le nombre maximum d’étapes qu’il faudrait ?Réponse : 7.1.2 Supposons que vous doubliez la taille de la liste. Quel est le nombre maximum d’étapes maintenant ?Réponse : 8.1.3 Vous avez un nom et vous voulez trouver le numéro de téléphone de la personne dans le répertoire téléphonique.Réponse : O(log n).1.4 Vous avez un numéro de téléphone et vous voulez trouver le nom de la personne dans le répertoire téléphonique. (Indice : vous devrez effectuer une recherche dans tout le répertoire !)Réponse : O(n).1.5 Vous voulez lire les numéros de chaque personne dans l’annuaire téléphonique.Réponse : O(n).1.6 Vous voulez lire les numéros des A uniquement. (C’est une question délicate ! Elle implique des concepts qui sont traités plus en détail au chapitre 4. Lisez la réponse, vous pourriez être surpris !)Réponse : O(n). Vous pensez peut-être : « Je ne fais cela que pour 1 caractère parmi 26 donc le temps d’exécution devrait être O(n/26). » Une règle simple à retenir est d’ignorer les nombres qui sont ajoutés, soustraits, multipliés ou divisés. Aucun des temps d’exécution suivants n’est correct pour Big O :
O(n + 26), O(n – 26), O(n * 26), O(n / 26). Ils sont tous les mêmes que O(n) ! Pourquoi ? Si vous êtes curieux, retournez à la section « Notation Big O revisitée » au chapitre 4, et relisez à propos des constantes en notation Big O (une constante n’est qu’un nombre ; 26 était la constante dans cette question)…