Complexité en algorithmique

Bonjour,

J'ai deux questions d'un exercice que je n'arrive pas à résoudre.
On nous demande de trouver x en fonction de n et de trouver l'équivalent asymptotique. ( en grand théta)
J'ai passé beaucoup de temps mais je n'y arrive pas..

Code:

---

1 2 3 4 5

question 1: x=1; for(i=0;i<n;i++) for(j=i;j<n;j=j+2) x++;

---

j'ai essayé pour différente valeur de n mais je ne vois pas le lien avec x.

pour n=1 x=2
pour n=2 x=3
pour n=3 x=5
pour n=4 x=7

Code:

---

1 2 3 4 5 6

question 2:   x=1; for(i=0; i<n; i++) for(j=i;j<n;j++) x++;

---

pour n=1 x=2
pour n=2 x=4
pour n=3 x=7
pour n=4 x=11

Pouvez vous m'aider s'il vous plaît? je dois finir pour demain..
Merci.

On te demande l'équivalent asymptotique de quoi ? de x en fonction de n, ou de la complexité du calcul de x en fonction de n ?

EDIT : sous-entendu je ne suis pas convaincu que tu prennes le problème par le bon bout.

Je vais prendre la pari fou qu'on se fout royalement de x et qu'on recherche le theta en fonction de n.

Il faut que tu décomposes ton algorithme..

Une boucle for 0..N va est parcourue combien de fois?

Dans ce cas, qu'en est-il d'une boule imbriquée ?

Citation:

---

Envoyé par chaton18

question 1:
x=1;
for(i=0;i<n;i++)
for(j=i;j<n;j=j+2)
x++;

---

Etant donné qu'à chaque itération de l'algorithme, x est incrémenté, déterminer la valeur de x revient à déterminer le nombre exacte d'itérations de l'algorithme. De plus il me semble que la valeur de x dépend aussi de la parité de n.
Prenons l'exemple où n=4 :

• i=0 :
  
  • j=0
  • j=2
  
  Nombre d'itérations = 2
• i=1 :
  
  • j=1
  • j=3
  
  Nombre d'itérations = 2
  
• i=2
  
  • j=2
  
  Nombre d'itérations = 1 :
• i=3
  
  • j=3
  
  Nombre d'itérations = 1 :

Il est clair que la boucle externe (for i) est exécutée n fois (de 0 à n-1), Quant à la boucle imbriquée (for j) ce n'est pas aussi simple ,car d'une part j "démarre" à partir de la valeur de i, d'autre part, j est incrémenté par 2.

En considérant que n est pair, à chaque itération de la boucle externe, la boucle imbriquée est exécutée (n-i)/2 ou (n-i+1)/2 fois selon la parité de i (pair ou impair respectivement).
Et puisque i varie de 0 à (n-1) le nombre total d'itérations est donc :

Code:

---

1 2 3

nb = (n-0)/2 + (n-1+1)/2 + (n-1)/2 + (n-2+1)+ ...+(n-(n-1)+1)/2. nb= 1/2 ( n + n + (n-1) + (n-1) + ... + 2 + 2 ) nb = 2 + 4 + 6 + . . . + n

---

qui est une somme des termes d'une suite arithmétique.
nb = (n/4)*(2+n)

Dans le deuxième cas où n est impair c'est l'inverse :à chaque itération de la boucle externe, la boucle imbriquée est exécutée (n-i)/2 ou (n-i+1)/2 fois selon la parité de i (i impair ou i pair respectivement).

Code:

---

1 2 3

nb= (n-0+1)/2 + (n-1)/2 + (n-2+1)/2 + ...+ (n-(n-2))/2 + (n-(n-1)+1)/2 nb = 1/2*(n+1 + n-1 + n-1 + n-3 + n-3 + ...+ 2 + 2) nb = ...

---

...
nb = (n+1)²/4

Quant à la valeur de x,étant donné que x est initialisé à 1,nous avons alors
x=nb+1;

Merci beaucoup,

pour la premiere question, j'avais remarqué qu'on additionnait Deux, puis trois ect.. mais je n'arrivais pas à l'écrire..je ne trouvais pas la formule générale.

Pour une boucle, l'équivalent asymptotique est linéaire.
pour deux bloucles: n^2
pour 3boucles: n^3 ( nous avons vu en cours)

Je ne vois pas l'intérêt de fournir la réponse à un problème d'école mais bon..

Citation:

---

Envoyé par seeme

Je ne vois pas l'intérêt de fournir la réponse à un problème d'école mais bon..

---

Moi non plus, mais bon... comme chaton18 avait l'air un peu perdu, je n'ai fourni qu'une partie de réponse de la question 1.

Bonsoir,
Oui, j'étais perdue pr cet exercice et j'étais stressée parce que je devais finir vite cet exercice. Je venais juste de découvrir ce site. La prochaine fois, je poserai des questions plus précises.

Merci encore pour votre aide. J'ai pu faire les autres exercices du même genre.