L2 MIASHS, Algorithme et Programmation 2, année 2021

Exemples de calcul de complexité

On reprends des exemples de calculs de complexité pour des fonctions récursives.

La méthodologie est toujours la même:

  1. Obtenir la forme inductive de la suite représentant le calcul de complexité
  2. Essayez d’estimer la croissance asymptotique de cette suite.

Dans les exemple ci-dessous, on va proposer des solutions impératives et récursives et une analyse de complexité.

Exemples sur les listes

Exemples sur les ensembles

Exemples sur les mots

Un mot est un carré s’il s’écrit de la forme \(u\cdot u\). Par exemple, le mot \(abcabc\) est un carré car il s’écrit \((abc)\cdot(abc)\) mais le mot \(abccba\) ne l’est pas.

Pour \(u\) et \(v\) deux mots, on dit que:

\(u\) est un sous-mot de \(v\) si en effaçant des lettres de \(v\) on peut obtenir \(u\). Par exemple \(ab\) est un sous mot de \(acdb\) mais \(ab\) n’est pas un sous mot de \(bcda\).

Solution vue en cours

lien