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:
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!
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
Même chose pour celui-ci: (qui parait un peu plus simple):
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.
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
Merci d'avance pour votre temps et vos réponses! :)
Partager