Itérations de boucles imbriquées

Deux boucles l'une dans l'autre font-elles toujours n × n tours ? Pas toujours. Choisissez un schéma de boucles, saisissez les tailles et lisez le nombre exact d'exécutions.

Jimenez JulienPar , éditeur de Calepin Binaire · mis à jour le

Nombre d'exécutions de action()
4 950
Ordre de grandeur
O(n²)
pour i de 0 à n-1
  pour j de 0 à i-1
    action()

Comment ça se calcule

Une boucle double exécute n × m fois son corps. Si la boucle intérieure s'arrête à i, on additionne 0 + 1 + ... + (n - 1) = n (n - 1) / 2. Une boucle dont la variable double à chaque tour s'exécute plafond(log2 n) fois. Le pseudo-code affiché correspond exactement au schéma choisi.

Questions fréquentes

Pourquoi la boucle triangulaire donne-t-elle n²/2 ?

Parce que la somme des entiers de 0 à n - 1 vaut n (n - 1) / 2, soit environ la moitié d'un carré.

Comment une boucle peut-elle être logarithmique ?

Quand sa variable est multipliée (et non incrémentée) à chaque tour : le nombre de tours est le nombre de fois qu'on peut doubler avant d'atteindre n.

Cas fréquents

Des exemples déjà remplis, avec leur explication :

Intégrer cet outil sur votre site

Copiez ce code pour afficher l'outil sur votre site ou votre blog. L'outil s'exécute dans le navigateur du visiteur, sans cookie ni suivi, et affiche un lien « Propulsé par Calepin Binaire » vers cette page.

Aperçu de la version intégrable : https://mircode.org/embed/iterations-de-boucles-imbriquees/

Les résultats sont fournis à titre indicatif. Pour aller plus loin, découvrez les sites de la catégorie Sandbox et casse-têtes de l'annuaire et lisez le guide de cette catégorie.

Autres outils

Voir les 35 outils