Discussion :

[natachaSt]

voila l'algo, ke peut bien etre ca complexité ???

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
type tab: tableau 1..1000 de entier;
/* la valeur de n doit être au maximum 1000 */
var i,j,k,n,p: entier;
var T: tab;
 
début
 
i:=n;
tantque i>0 faire
   si i mod 2 =1 alors
      i:=i-1
   sinon
      i:=i/2
   finsi
fin tantque
 
fin

[millie]

à toi et bienvenue sur le forum de developpez.com

voila l'algo, ke peut bien etre ca complexité ???

Prière de ne pas utiliser de langage SMS, c'est vraiment énervant !

type tab: tableau 1..1000 de entier;
/* la valeur de n doit être au maximum 1000 */
var i,j,k,n,p: entier;
var T: tab;

début

i:=n;
tantque i>0 faire
si i mod 2 =1 alors
i:=i-1
sinon
i:=i/2
finsi
fin tantque

fin

Merci d'utiliser la balise : CODE


La complexité de ton algorithme est compris entre : log_2 n et 2 log_n. C'est à dire en O(ln n). En considérant évidemment que la représentation machine d'un entier prend n bits pour l'entier n.

En effet, dans le meilleur des cas, l'entier est un puissance de 2. Dans le pire des cas, à chaque fois que l'on fait l'étape i<-i/2, l'entier est impair et donc il sera redivisé uniquement à l'étape suivante (=> 2 log_2 n).


A noter que l'algorithme n'a aucune utilité car il est équivalent à l'algorithme suivant (au passage, tu as également déclaré un tableau sans l'utiliser) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
fonction monalgo(n:Entier non signé)-> Entier
 Retourner 0

[PRomu@ld]

En considérant évidemment que la représentation machine d'un entier prend n bits pour l'entier n.

Donc 1000 est codé sur 1000 bits ? Pas très réaliste tout ça ...

En fait c'est en O (taille en bit de ton nombre). Ce qui revient à log( n ) car un nombre n est codé sur log2(n) bits.

Tout simplement lorsque tu divises ton nombre par 2, tu lui enlèves un bit.

[millie]

Si j'ai dit ça, car la complexité est une fonction de la taille en machine de l'instance d'entrée.

Si n prend log_2 n en machine (ce qui est normal), il faut fait 2^ (la complexité que j'ai dit) pour avoir la vrai au sens classique du terme.

Ce qui donnerait une complexité linéaire dans ce cas.


Mais souvent, pour des entiers en entrée de l'algorithme, on garde la définition classique de la complexité (donc celle que j'ai dit) mais en prenant : n comme taille en machine de l'instance d'entrée n. Ceci n'est par contre jamais considéré pour des algorithmes qui fonctionnent sur de grosses instances (par exemple en cryptologie) où l'on garde la vrai définition classique


Par exemple, l'algorithme suivant qui calcule la somme de 1 à n :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
fonction somme(Entier n)
  Entier compteur = 0
  Pour i=1 à n
   compteur <- compteur +i
 
 Retourner compteur

Il est souvent plus simple de considerer que cet algorithme est linéaire (car il y a n passe dans la boucle). Mais avec la définition classique en théorie de la complexité, la représentation machine de n est t=log_2 n. La complexité est une fonction de t, c'est à dire : complexité(t) = n(t) = 2^t

C'est à dire une complexité exponentielle

[natachaSt]

merci,
mais en essayant d'appliquer ce raisonnement sur un autre algorithme, je me trouve coincer. voici l'algorithme en question :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
pour i allant de 1 à n faire T[i]=0;
i:=1;
tantque i=1 faire
   tantque i<=n et T[i]=i faire
      T[i]=0;
      i:=i+1
   fin tantque
   si i<=n alors
      T[i]:=T[i]+1
      i:=1
   finsi
fin tantque

[natachaSt]

j'ai fait tourner cet algorithme, c'est un genre de conteur :
avec n=3,
T : 000
T : 100
T : 010
T : 020
T : 120
T : 001
T : 101
T : 011
T : 111
T : 021
T : 121
T : 002
...
T : 123

je trouve : O(n^n) ???