Sciences appliquées
Exercices corrigés : Complexité
Dénombrement, preuves en O, dichotomie, hachage, 2-sum et coût énergétique.
12 exercices, corrigés dans la page, sans compte à créer.
- Compter les comparaisons d'une double boucleFacile
- Exhiber n₀ et kAccessible
- Meilleur cas, pire cas, cas moyenAccessible
- La recherche dichotomiqueAccessible
- Prédire l'effet d'un doublementAccessible
- Extrapoler une durée, lire une penteIntermédiaire
- Une table de hachage à la mainIntermédiaire
- Le facteur de charge et le coût amortiIntermédiaire
- Le 2-sum en temps linéaireExigeant
- Débogage : le 2-sum se marie avec lui-mêmeIntermédiaire
- Le 2-sum par tri et deux pointeursExigeant
- Ce que le bon algorithme économise vraimentExigeant
Cette notion fait partie du cours de Sciences appliquées, dont les autres notions sont dans les exercices corrigés de Sciences appliquées. Tous les parcours sont dans la bibliothèque.