Version imprimable
voila l'algo, ke peut bien etre ca complexité ???
Code:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
:salut: à toi et bienvenue sur le forum de developpez.com
Prière de ne pas utiliser de langage SMS, c'est vraiment énervant !Citation:
Envoyé par natachaSt
Merci d'utiliser la balise : CODE :tagcode: :mrgreen:Citation:
Envoyé par natachaSt
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. :mrgreen:
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:
2
Donc 1000 est codé sur 1000 bits ? Pas très réaliste tout ça ...:aie:Citation:
En considérant évidemment que la représentation machine d'un entier prend n bits pour l'entier n.
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.
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 :mrgreen:
Par exemple, l'algorithme suivant qui calcule la somme de 1 à n :
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^tCode:
2
3
4
5
6
7
C'est à dire une complexité exponentielle :mrgreen:
merci,
mais en essayant d'appliquer ce raisonnement sur un autre algorithme, je me trouve coincer. voici l'algorithme en question :
Code:
2
3
4
5
6
7
8
9
10
11
12
13
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) ???
Si on savait ce que faisait exactement ton algorithme, ce serait surement plus simple pour nous de te donner la complexité.
Tu peux me dire où tu apprends (ou alors enseigne) l'algorithmique ? Parce que là ça m'inquiète ... :aie:, 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 ...Citation:
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
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 :mrgreen: , la complexité est linéaire (désolé pour l'écriture abusive ...).Citation:
Ce qui donnerait une complexité linéaire dans ce cas.
J'ai vraiment du mal à suivre ton raisonnement ...
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...:aie:
Par exemple, dans Wikipedia :
Citation:
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).
Donc c'est bien : par rapport à la taille de l'instance.Citation:
[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.
C'est à dire pour un entier, par rapport à t = log_2 n
Linéaire par rapport à la taille de l'instance comme j'ai dit :mrgreen:Citation:
Mais c'est bien ça, le tout est de savoir en quoi celà est linéaire.
bon d'accord,
un peu plus dur,
soit l'algorithme suivant :
ca sré koi sa compléxité??Code:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Citation:
Envoyé par natachaSt
Salut. :nosms:
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 ???
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é!!
Citation:
Envoyé par natachaSt
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.
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??
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).Citation:
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...
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 ...).
Bon, ben je m'incline devant la référence ultime et universelle ...Citation:
Par exemple, dans Wikipedia :
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)Citation:
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??
Justement, en théorie de la complexité, ce n'est pas relatif. C'est clairement définie !Citation:
Envoyé par PRomu@ld
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.
Evite l'ironie sur ce point, je ne suis pas chez moi et je n'ai pas de lien gratuit à te donner.Citation:
Envoyé par PRomu@ld
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 :
Autres lien qui confirme mes dires :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
http://bigbozoid.free.fr/CoursMASTER...%20et%20NP.pdf
Bon, très bien, on ne vas pas s'énerver parce que je sens qu'on va arriver à un dialogue de sourd ...Citation:
Justement, en théorie de la complexité, ce n'est pas relatif. C'est clairement définie !
J'ai peur de ne pas comprendre, excuse moi mon ignorance mais pourquoi un algorithme linéaire ne serait-il pas polynomial ?Citation:
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.
Je ne fais pas d'ironie, mais tu sembles un peu trop rigide à mon goût.Citation:
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
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.
Oui, tu as raison, dernier post là dessus :mrgreen:Citation:
Envoyé par PRomu@ld
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).Citation:
J'ai peur de ne pas comprendre, excuse moi mon ignorance mais pourquoi un algorithme linéaire ne serait-il pas polynomial ?
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).Citation:
Je ne fais pas d'ironie, mais tu sembles un peu trop rigide à mon goût.
Enfin, j'arrête là... :mrgreen:
De toute manière, si on sait calculer la complexité avec une définition, on saura la calculer pour une autre.
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.Citation:
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).
Citation:
Envoyé par Introduction to Algorithms