Algorithmes et Programmation 2, année 2023
Exemples de calcul de complexité
On reprend 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é
- Essayer d’estimer la croissance asymptotique de cette suite.
Dans les exemples 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\) tels que \(i+1\) est aussi dans \(L\).
Exemples sur les ensembles
- sous-ensembles
- Entrée: un ensemble d’éléments \(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 si \(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 si \(u\) est un sous-mot de \(v\).
Solution vue en cours
Compiled the: mar. 17 déc. 2024 14:03:22 CET