Complexité et récursivité

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:

---

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)² 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:

---

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! :)

Le temps de complexité pour le premier est :

(n/2)*2 soit n

Tu ne parcours que la moitié de n vu que tu fais -2 à chaque fois mais tu le fais 2 fois.
A3(n)*A3(n) et A3(n)+A3(n) ont le même temps de complexité.


Et pour le deuxième le temps de complexité est :

n

Car tu appelles n fois ta fonction A2
Bien sûr les constante comme le -3 ne sont pas à prendre en compte car si n = 10 000 le -3 devient négligeable.

Bonjour,
C'est bizarre, pour la deuxième j'aurai dit n/3 pour la complexité.
Par exemple pour n = 15, on appelle A2(15), A2(12), A2(9), A2(6), A2(3).

C'est le même raisonnement qui donne le n/2 pour A3.
Ou alors je n'ai rien compris :aie:

Tatayo.

Bonjour,

Citation:

---

Envoyé par tatayo

C'est bizarre, pour la deuxième j'aurai dit n/3 pour la complexité.
Par exemple pour n = 15, on appelle A2(15), A2(12), A2(9), A2(6), A2(3).

C'est le même raisonnement qui donne le n/2 pour A3.
Ou alors je n'ai rien compris :aie:

---

Tu as raison, c'est le même raisonnement...
et ce raisonnement nous amène à dire que la complexité en opération est linéaire par rapport à n, c'est à dire de la forme T(n) = a.n+b... donc O(n).

Faut se rappeler qu'en complexité O(...) on ne cherche pas le nombre exacte d'opérations que l'algo va prendre, mais juste la "forme" de la courbe.
Dans les deux cas, la forme est une ligne (pas avec la même pente, mais ca reste une ligne).

Une manière de voir les choses (utile pour les partiels :D ):

Split & Merge O(1)
T(n) = T(n/2) + O(1)    ---> O(log n)
T(n) = T(n-1) + O(1)    ---> O(n)
T(n) = 2 T(n/2) + O(1)  ---> O(n)

Split & Merge O(n)
T(n) = T(n-1) + O(n)    ---> O(n^2)
T(n) = 2 T(n/2) + O(n)  ---> O(n log n)

Split: La récursion réduit la taille des données à traiter (soit en divisant la taille par une constante, soit en soustrayant une constante à la taille)
Merge O(1): A chaque étape de la récursion, on doit faire une opération qui ne dépend pas de taille des données (c'est le cas dans tes deux exemples).
Merge O(n): A chaque étape de la récursion, on doit faire une opération qui dépend linéairement de la taille des donnés (par exemple parcourir les données pour calculer la moyenne)

Ok avec Pseudocode, mais ok aussi avec Tatayo.

Quand on parle de complexité d'un algorithme, on s'intéresse uniquement à l'exposant qu'on va mettre au dessus de n. Est-ce que c'est n ou n/3, on s'en moque, ce qu'on veut savoir, c'est si c'est n^1, ou n^2 ou n^3, ou n log(n) qu'on retrouve assez souvent.

Mais dans le message de Matthieu76, mêm si au final, la réponse est juste, il y avait quelques maladresses de formulation.
Si on dit que le -2 est significatif dans le premie exercice, on ne peut pas dire que le -3 est négligeable dans le 2ème ....

En particulier, si au lieu de -3, on avait -0, ou +1, la réponse à l'exercice serait très différente !

Idem, si on avait cet exercice, la réponse serait encore différente.

Code:

---

1 2 3 4

function A2(n): if n > 2 return 1 + A2(n*0.97) return 1

---

Enfin, dans le premier exercice, je pense que la réponse est fausse.
Je verrais bien une complexité en n²

Citation:

---

Envoyé par tbc92

Enfin, dans le premier exercice, je pense que la réponse est fausse.
Je verrais bien une complexité en n²

---

C'est pire que cela... sur un ensemble de taille 8, par exemple {1,2,3,4,5,6,7,8}

T({1,2,3,4,5,6,7,8})
= 2*T({1,2,3,4,5,6})+1
= 2*(2*T({1,2,3,4})+1)+1
= 2*(2*(2*T({1,2})+1)+1)+1
= 2*(2*(2*(2*T({})+1))+1)+1)+1  // T({})=0 car on n'arien à faire.
= 8+4+2+1
= 15

Le terme général est T(n) = 2^(n/2) - 1

Oui, bien sûr ! 2x2x2x2 .. et non NxN !