Informatique · Première · 1 exercice vérifié

S’entraîner : Coût d'un algorithme : ordre de grandeur du nombre d'opérations

Chapitre : Numérique et sciences informatiques (spécialité)

Ce que vous travaillez

Estimer comment le nombre d'opérations d'un algorithme varie avec la taille n des données : coût constant, logarithmique (la donnée est divisée par deux à chaque étape), linéaire (une boucle sur les n éléments), quadratique (deux boucles imbriquées) ; quand n double, un coût linéaire double, un coût quadratique est multiplié par quatre, un coût logarithmique augmente d'une étape ; intérêt de passer d'un coût quadratique en n² à n log₂ n, ou de n à log₂ n, sur des données nombreuses.

À maîtriser avant de commencer

Ces notions sont utilisées ici. Relisez-les si l’une d’elles vous échappe.

Boucles bornées et non bornées — Boucle bornée for, en particulier for i in range(a, b) qui fait prendre à i les valeurs a, a + 1, …, b − 1 ; boucle non bornée while, répétée tant que sa condition est vraie ; dérouler une boucle à la main dans un tableau de suivi des variables (traçage) ; accumulateur (somme, compteur) ; choix entre les deux boucles.

Comment se déroule la séance

Cette séance s’appuie sur 1 exercice vérifié. Chacun produit un nouvel énoncé à chaque ouverture, avec une solution calculée.

Formats de réponse : QCM (1). Difficulté 3 sur 5. Environ 3 minutes pour un premier passage.

Dans votre compte : aide graduée (indice, rappel de cours, aide au démarrage), corrigé pas à pas après chaque tentative, suivi de vos progrès.

Essayez un exercice, sans compte

Un exercice réel de cette séance, le même pour chaque visiteur. Répondez, puis vérifiez : la correction est calculée, et le corrigé s’affiche après votre tentative.

Difficulté 3 sur 5 · ≈ 3 minutes

Énoncé

On considère la fonction Python ci-dessous, appelée avec un entier n positif.

Tableau : n°, Instruction
n°	Instruction
1	def f(n):
2	····r = 0
3	····for i in range(n):
4	········r = r + i
5	····for j in range(2 * n):
6	········r = r - 1
7	····return r

Chaque groupe de quatre points « ···· » marque un niveau d'indentation (quatre espaces en Python).

Quand n devient grand, comment varie le nombre d'opérations effectuées par f(n) ?

Votre réponse

Continuez dans votre compte

Créez votre compte gratuit pour faire toute la séance avec l’aide graduée, ou connectez-vous pour revenir directement ici.

Créer mon compte gratuit Me connecter pour continuer

L’accès gratuit comprend les cours et exercices de votre niveau choisi.