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) ???

[millie]

Si on savait ce que faisait exactement ton algorithme, ce serait surement plus simple pour nous de te donner la complexité.

[PRomu@ld]

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

Tu peux me dire où tu apprends (ou alors enseigne) l'algorithmique ? Parce que là ça m'inquiète ... , la complexité est exponentielle en la taille en bits du nombre et 2^log_2(n) = n, ça fait bien une complexité linéaire en le nombre ...

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

Mais c'est bien ça, le tout est de savoir en quoi celà est linéaire. Pour moi, c'est linéaire en la taille en bits du nombre. De toute façon comme O(n) > O(ln n) il n'y a aucun soucis , la complexité est linéaire (désolé pour l'écriture abusive ...).

J'ai vraiment du mal à suivre ton raisonnement ...

[millie]

Dans tous les cours qui traite de la théorie de la complexité, il est stipulé que la complexité est une fonction dont le paramètre est la taille de l'instance d'entrée.

Tu peux regarder dans tous les cours qui formalisent la complexité (en utilisant par exemple des machines de Turing), c'est cette définition qui est choisie.

Si ce n'était pas le cas, alors tous les algorithmes de cryptage qui sont supposés être dans NP-P serait magiquement cassable en un temps polynomial...

Par exemple, dans Wikipedia :

On désigne par n la taille de la donnée.

Pour les machines déterministes, on définit la classe TIME(t(n)) des problèmes qui peuvent être résolus en temps t(n). C'est-à-dire pour lesquels il existe au moins un algorithme sur machine déterministe résolvant le problème en temps t(n) (le temps étant le nombre de transitions sur machine de Turing ou le nombre d’opérations sur machine RAM).

[Classe P]

Un problème de décision est dans P s'il peut être décidé par un algorithme déterministe en un temps polynomial par rapport à la taille de l'instance. On qualifie alors le problème de polynomial.

Donc c'est bien : par rapport à la taille de l'instance.
C'est à dire pour un entier, par rapport à t = log_2 n

Mais c'est bien ça, le tout est de savoir en quoi celà est linéaire.

Linéaire par rapport à la taille de l'instance comme j'ai dit

[natachaSt]

bon d'accord,
un peu plus dur,
soit l'algorithme suivant :

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
 
var j,n,p: entier;
var T: tab;
 
 
j:=1;
tantque j<n faire
   p:=1;
   tantque p<j faire  /* modifié */
      p:=p*2
   fin tantque
   si p=j /*j est une puissance de 2*/ alors
      j:=2*j+1
   sinon
      j:=j+1
   finsi
fin tantque

ca sré koi sa compléxité??

[millie]

ca sré koi sa compléxité??

Salut.

A quoi sert cet algorithme ?

Car tu viens de nous donner 3 algorithmes différents et je ne comprend pas vraiment ce que tu cherches ? Que l'on te résolve des exercices ???

[natachaSt]

je vois pas comment tu calcule la compléxité aussi facilement, quand je vois une correction je me dis que c'est evident, mais un fois que j'essaie sur un autre exemple, je n'arrive pas a trouver!! peut tu me passer un cours, ou un tutorial pour me facilité la vie avec la compléxité!!

[millie]

je vois pas comment tu calcule la compléxité aussi facilement, quand je vois une correction je me dis que c'est evident, mais un fois que j'essaie sur un autre exemple, je n'arrive pas a trouver!! peut tu me passer un cours, ou un tutorial pour me facilité la vie avec la compléxité!!

Il te faudrait essayer de travailler avec des algorithmes plus simples => Que l'on comprenne ce qu'il fait avec un coup d'oeil. Car ce que tu donnes sont assez... bizarre.

Il n'est pas forcement possible de déterminer correctement une complexité (mais seulement une borne) quand il y a plein de conditions comme ça qui peuvent modifier la vitesse d'exécution.

[natachaSt]

justement, si on trouve la borne, c une aproximation, la compléxité sera une aproximation parraport a cette borne??
comment trouve tu cette borne pour cet algo alors??

[PRomu@ld]

Si ce n'était pas le cas, alors tous les algorithmes de cryptage qui sont supposés être dans NP-P serait magiquement cassable en un temps polynomial...

Et bien oui, je ne vois pas ce qui te choque, c'est comme en physique : tout est relatif. C'est même en temps constant : le temps de factoriser les nombres (si c'est un problème de factorisation).

La complexité est donnée en fonction de ce qui t'intéresse et de ce qui sera utile pour la compréhension et tes applications.

Ce qui était intéressant dans le premier algorithme, c'était en fonction de la taille du nombre. Alors pourquoi j'ai utilisé la représentation du nombre ? Tout simplement parce que la complexité est facile à calculer et à démontrer. Et puis la plupart des humains non-informaticiens préfèrent la linéarité que la logarithmicité (désolé pour le néologisme ...).

Par exemple, dans Wikipedia :

Bon, ben je m'incline devant la référence ultime et universelle ...

[PRomu@ld]

justement, si on trouve la borne, c une aproximation, la compléxité sera une aproximation parraport a cette borne??
comment trouve tu cette borne pour cet algo alors??

Typiquement, il faut que tu étudie comment se comporte ton algo en fonction de l'entrée : est ce que ça diminue (ou augmente) tout le temps ? si oui, de quelle manière ? Si c'est non, ça devient un problème difficile (cf le problème de syracuse)

[millie]

Et bien oui, je ne vois pas ce qui te choque, c'est comme en physique : tout est relatif. C'est même en temps constant : le temps de factoriser les nombres (si c'est un problème de factorisation).

Justement, en théorie de la complexité, ce n'est pas relatif. C'est clairement définie !

L'algorithme que j'avais donné est bien en n, il est linéaire par rapport à n, mais il n'est pas dans la classe P dont il n'est pas polynomial.

Bon, ben je m'incline devant la référence ultime et universelle ...

Evite l'ironie sur ce point, je ne suis pas chez moi et je n'ai pas de lien gratuit à te donner.

Alors voilà des livres qui définissent de la même manière que moi :
http://www.dunod.com/pages/ouvrages/...e.asp?id=47281
Et celui-ci:
http://www.dunod.com/pages/ouvrages/...e.asp?id=49981


Autre citation :

Apprécier la complexité d'un fonction f est réalisé en observant l'évolution des ressources consommés par le calcul des valeurs f(x) en fonction de la complexité des entrées x. La complexité d'une entrée x est définie comme étant définie par la longueur même du mot x, noté |x|

Un choix cohérent pour définir la notion de facilité est celui des algorithmes polynomiaux, c'est à dire admettant une fonction polynomial p telle que pour tout entrée x, le nombre d'instructions élémentaires exécutées par l'algorithme sur l'entrée x est majorée par p(|x|)


Tiré d'un cours de cryptologie donné à l'ENSEIRB

Autres lien qui confirme mes dires :

http://bigbozoid.free.fr/CoursMASTER...%20et%20NP.pdf

[PRomu@ld]

Justement, en théorie de la complexité, ce n'est pas relatif. C'est clairement définie !

Bon, très bien, on ne vas pas s'énerver parce que je sens qu'on va arriver à un dialogue de sourd ...

L'algorithme que j'avais donné est bien en n, il est linéaire par rapport à n, mais il n'est pas dans la classe P dont il n'est pas polynomial.

J'ai peur de ne pas comprendre, excuse moi mon ignorance mais pourquoi un algorithme linéaire ne serait-il pas polynomial ?

Evite l'ironie sur ce point, je ne suis pas chez moi et je n'ai pas de lien gratuit à te donner.

Alors voilà des livres qui définissent de la même manière que moi :
http://www.dunod.com/pages/ouvrages/...e.asp?id=47281
Et celui-ci:
http://www.dunod.com/pages/ouvrages/...e.asp?id=49981


Autre citation :
Citation:
Apprécier la complexité d'un fonction f est réalisé en observant l'évolution des ressources consommés par le calcul des valeurs f(x) en fonction de la complexité des entrées x. La complexité d'une entrée x est définie comme étant définie par la longueur même du mot x, noté |x|

Un choix cohérent pour définir la notion de facilité est celui des algorithmes polynomiaux, c'est à dire admettant une fonction polynomial p telle que pour tout entrée x, le nombre d'instructions élémentaires exécutées par l'algorithme sur l'entrée x est majorée par p(|x|)


Tiré d'un cours de cryptologie donné à l'ENSEIRB

Je ne fais pas d'ironie, mais tu sembles un peu trop rigide à mon goût.
Comme je l'ai suggéré, la complexité doit être exprimée en fonction de ce qui nous intéresse. Pour la crypto ce qui est intéressant, c'est exprimer la complexité en fonction de la taille du nombre en bit (enfin je crois) et pas en fonction du nombre. Ce n'est qu'une question de représentation et de simplicté de l'expression. De toute façon que l'on parle du nombre en base 10 ou en binaire la complexité est exprimée en fonction des entrées, alors je ne vois pas pourquoi on s'énerverait ... . Ou alors j'ai tout faux.

[millie]

Bon, très bien, on ne vas pas s'énerver parce que je sens qu'on va arriver à un dialogue de sourd ...

Oui, tu as raison, dernier post là dessus

J'ai peur de ne pas comprendre, excuse moi mon ignorance mais pourquoi un algorithme linéaire ne serait-il pas polynomial ?

En fait, l'algorithme est linéaire par rapport à n, mais pas linéaire au sens classique de la théorie de la complexité (c'est à dire par rapport à la taille de l'instance).

Je ne fais pas d'ironie, mais tu sembles un peu trop rigide à mon goût.

Oui et non. La définition que j'ai donné, c'est celle qu'on trouve partout (j'ai ajouté deux liens si tu veux jetter un oeil).


Enfin, j'arrête là...

De toute manière, si on sait calculer la complexité avec une définition, on saura la calculer pour une autre.

[PRomu@ld]

Oui et non. La définition que j'ai donné, c'est celle qu'on trouve partout (j'ai ajouté deux liens si tu veux jetter un oeil).

Comme je l'ai dis, les définitions sont là pour être adaptée aux besoin. Ce que tu trouve, ce sont des définitions générales.

The best notion for input size depends on the problem being studied. For many problems,
such as sorting or computing discrete Fourier transforms, the most natural measure is the
number of items in the input-for example, the array size n for sorting. For many other
problems, such as multiplying two integers, the best measure of input size is the total number
of bits needed to represent the input in ordinary binary notation.