Bonjour!
A l'approche de mes partiels, je suis en train de travailler quelques exercices sur la complexité et je bloque sur quelques un où la complexité est une suite récursive, un peu comme cet exemple-ci:
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
function A3(n)
    if n > 1
        return 1 + A3(n-2)*A3(n-2)
    return 0
En notant T(n) la complexité, j'ai: T(n)=c+T(n-2)2 et ce n'est pas très évident pour moi de trouver un majorant!
Même chose pour celui-ci: (qui parait un peu plus simple):
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
function A2(n):
    if n > 2
        return 1 + A2(n-3)
    return 1
Je ne sais pas si je dois trouver une expression de la suite ou simplement essayer de la majorer brutalement, ce qui ne me parait pas très simple non plus.
Merci d'avance pour votre temps et vos réponses! :)