Temps polynomial

[arsene]

Bonjour
J'aimerai savoir ce ke ve dire
calculs a temps polynomial et aussi a temps probabiliste
Je suppose que le deuxieme est un calcul hasardeux ou bien?
merci

[yos]

Quand un programme fait un calcul qui dépend d'une variable x, il met un certain temps qui dépend de la taille de x : T(x). Si T est un polynôme ou plutôt un on dit que le calcul ce fait en temps polynomial. A noter qu'une machine cent fois plus rapide qu'une autre ne change rien à cet aspect. C'est le programme qui est déterminant.
Exemple : décomposer un entier x en facteurs premiers. Je ne sais pas si ça se fait en temps polynomial.

[uztop]

Salut,

la décomposition en facteurs premiers ne peut pas se faire en temps polynomial (ça se fait en temps exponentiel c'est à dire . C'est justtement le principe de la cryptographie: la multiplication de deux nombres est un problème facile, mais leur factorisation est un problème difficile. Comme tu le dis, une machine plus puissante permet de gagner quelques ordres de grandeur, ce qui n'avance pas à grand chose pour un temps de calcul exponentiel.

[arsene]

bonjour et merci a vous

[arsene]

bonjour j ai bien compris vos explicationsde la derniere fois-merci
pour cette fois je lis O(B log(B)) dans un document et aimerai comprendre ce qu'ils veulent dire par la.
la determination de l'ensemble des nbres premiers plus petits que B se fait sur une durée O(B log(B)).
Une autre notation est poly(logN)
???
Merci

[SimonB]

Tu ne connais pas la fonction "logarithme" ? C'est l'inverse de la fonction exponentielle définie en terminale...
Ils disent juste que l'algorithme tourne en (c'est-à-dire un peu plus que O(B) mais un peu moins que O(B²)).

[arsene]

Si je connais la fonction logarithme.
Et quand j ai un algorithme comment je pourrais moi aussi plutard ecrire le temps de realisation ...
Je devrais tenir compte des formes de calculs que j y effectue?
par exemple dans la determination de l'ensemble des nbres premiers plus petits que B
je realise l'algo de Miller par exemple ou un autre algo et je borne lesnbres premiers par B
pourriez vous me dire comment je trouve le nbre qui se trouve dans 0(...)
pour un tel algorithme?
merci

[SimonB]

Il faut compter les opérations élémentaires. Généralement, une bonne chose à faire consiste à trouver une relation de récurrence qui te permet de déterminer soit explicitement ta complexité, soit un O(...).
Tu trouveras au chapitre 6 de ce cours une bonne introduction au sujet.

[arsene]

bsr simon
merci pour le lien
je lis