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:
- Obtenir la forme inductive de la suite représentant le calcul de complexité
- 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
- noyau
- Entrée: Une liste \(L\) d’ensembles
- Retourne: l’intersection de tous les ensembles de \(L\)
- successeurs
- Entrée: Une liste \(L\) d’entiers.
- Retourne: La liste des entiers \(i\) dans \(L\) tel que \(i+1\) est aussi dans \(L\).
- éléments répétés
- Entrée: une liste d’éléments \(L\) et un entier \(k\)
- Retourne: la liste des élément qui apparaissent au moins \(k\) fois.
Exemples sur les ensembles
- sous-ensembles
- Entrée: un ensemble d’élément \(S\)
- Retourne: la liste des sous ensembles de \(S\).
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.
- est_carré
- Entrée: un mot \(u\)
- Retourne: Vrai si et seulement \(u\) est un carré.
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\).
- sous-mot
- Entrée: deux mots \(u\) et \(v\)
- Retourne: Vrai si et seulement \(u\) est un sous-mot de \(v\).
Solution vue en cours
Compiled the: dim. 07 janv. 2024 23:19:17 CET