Aller au contenu

Algorithmique : recherche et complexité

Algorithmique · Intermédiaire · 10 questions. Une seule bonne réponse par question. Répondez puis consultez la correction expliquée.

  • 1. Une recherche linéaire inspecte au pire…
  • 2. La recherche dichotomique demande généralement…
  • 3. Diviser la zone de recherche par deux à chaque étape conduit à…
  • 4. Deux boucles successives de n itérations avec travail constant donnent…
  • 5. Deux boucles imbriquées de n itérations chacune donnent…
  • 6. Accéder à un indice valide dans un tableau classique est généralement…
  • 7. Une borne O(n) signifie…
  • 8. Pourquoi tester des cas limites ?
  • 9. Une pile retire d’abord…
  • 10. Une file FIFO retire d’abord…
Corrigé à lire, même sans JavaScript
  1. Tous les éléments. Si la valeur est absente, chaque position peut devoir être examinée.
  2. Des données triées avec accès adapté. L’ordre permet d’écarter une moitié de l’intervalle à chaque étape.
  3. Un nombre logarithmique d’étapes. La réduction répétée par deux donne une croissance en log de la taille initiale.
  4. Une croissance linéaire. Le travail total est proportionnel à n + n, donc à n.
  5. Une croissance quadratique. Le corps interne est exécuté n fois pour chacune des n itérations externes.
  6. En temps constant. L’adresse se calcule directement dans le modèle habituel du tableau.
  7. Une borne asymptotique supérieure linéaire. La notation décrit une croissance, pas une durée physique universelle.
  8. Pour exposer des erreurs aux frontières. Les collections vides, les bornes et les doublons révèlent des défauts fréquents.
  9. Le dernier élément ajouté. Le principe LIFO correspond au dernier entré, premier sorti.
  10. Le premier élément ajouté. L’ordre d’arrivée est conservé pour le service des éléments.

Pour approfondir : Les cours PandaCodeur.