Cahier d'exercices : complexité des algorithmes
Compter des opérations est une habitude qui s'acquiert. Ces huit exercices vous font passer des boucles aux ordres de grandeur sans une ligne de code.
Par Jimenez Julien, éditeur de Calepin Binaire · mis à jour le
Aperçu
CAHIER D'EXERCICES : COMPLEXITÉ DES ALGORITHMES
………, le ………
1. Combien d'étapes au plus pour retrouver un élément par dichotomie dans 1 000 éléments triés ?
Réponse : ………
2. Deux boucles imbriquées font 20 tours et 30 tours. Combien d'exécutions du corps ?
Réponse : ………
3. Une boucle intérieure s'arrête à i, avec n = 10. Combien d'exécutions au total ?
Réponse : ………
4. Un traitement en n au carré dure 4 secondes pour n = 1 000. Combien pour n = 2 000 ?
Réponse : ………
5. Classez de la croissance la plus lente à la plus rapide : n au carré, log n, 2 puissance n, n, n log n.
Réponse : ………
6. Une variable démarre à 1 et double tant qu'elle est inférieure à 100. Combien de tours ?
Réponse : ………
7. Combien d'appels pour calculer fib(5) avec la version récursive naïve ?
Réponse : ………
8. En une phrase, pourquoi la mémorisation accélère-t-elle fib(40) ?
Réponse : ………
Score : ……… / 8
Conseils d'utilisation
- Dessinez les boucles en tableau si le total vous échappe.
- Vérifiez vos réponses avec les outils de la famille algorithmes.
- Pour la question ouverte, formulez la réponse comme si vous l'expliquiez à un ami.
Sans JavaScript, le modèle vierge ci-dessus peut être imprimé et rempli à la main.
Questions fréquentes
Ces fiches ont-elles une valeur officielle ?
Non. Ce sont des supports de travail personnels, à enrichir avec vos cours et vos lectures.
Mes réponses sont-elles envoyées quelque part ?
Non. Le texte est généré dans votre navigateur et ne quitte pas votre appareil.
Comment enregistrer le document ?
Utilisez les boutons de téléchargement (.txt ou .html) ou le bouton d'impression, qui permet aussi d'enregistrer en PDF avec la fonction d'impression de votre navigateur.