Bonjour, comme il n'y a pas de rubrique "informatique théorique" je tente ma chance ici (...).
Voilà, au fait j'ai un algorithme dont la complexité est d'ordre
Donc dans quelle catégorie rangerait-t-on ce genre d'algorithme :
1. Polynomial
2. Exponentiel
3. NP
J'ai un sérieux doute. Merci d'avance pour vos propositions.
pardon ma question a été mal posée. Je reformule :
"Je cherche au fait un exemple (simple mais rigoureux) ou l'ordre de complexité d'un algorithme est ni exponentiel, ni polynomial"
Merci d'avance
Salut,
tu cherche juste un exemple ?
Dans ce cas tu peux toujours regarder comment est calculé la compléxité de la FFT (compléxité N^2*logN)
Salut,
Je pense que c'est adéquat.Envoyé par isozv
En n ou en p?Voilà, au fait j'ai un algorithme dont la complexité est d'ordre
D'une maniére générale, la complexité des algorithmes est classée selon l'échelle combinée des polynômes, logarithmes et exponentielles, soit en O(nalogbnecn).
Je crois qu'on peut en trouver en O(log(log n)) aussi. Mais c'est un peu loin tout ça pour moi. D'autres participants m'appuieront ou me réfuteront.
A+
Il me semble que N^2*logN peut s'exprimer sous forme polynomiale non en développement en série de taylor ? Donc c'est une complexité Polynomiale la FFT ? Non ???
Je pense pas que N^2logN puisse s'écrire sous forme polynomiale, ou alors en un dl autour d'une certaine valeur...
en développement de Taylor tu peux toujours exprimer logN sous forme de série de Taylor et donc N^2logN aussi.
En effet on peut faire comme ca, mais logN s'écrit dans ce cas en un polynome de degré infinie, ou alors finie si on considère qu'au-dela d'une certaine puissance les valeurs sont négligeables...
Mais la valeur de cette puissance est fonction de N (appelons la f(N)), donc du coup on se retrouve avec un ordre de compléxité O(x^(f(N)) ce qui ne t'avances pas a grand chose, peu parlant, beaucoup moins que O(N^2logN)...
PS: Dans ce cas toutes les compléxités sont polynomiales du moment qu'on peut éxprimer le dl des fonctions...
oui justement c'est ce que je trouve louche.
Mais d'après les définitions en complexité algorithmique, un algoritme dont l'ordre de complexité est logarithmique n'est pas un algorithme NP.
de mémoire, la recherche par dichotomie a une complexité en log(N).
(je sais pas si je suis hors sujet)
FFT c'est en O(n log n) :
Pour calculer une transformée de fourier sur n points, on calcule 2 transformées de fourier en n/2 points et on fait n additions et n multiplications.
Avec ça on peut faire un algorithme pour multiplier rapidement deux entiers à n bits: L'algo sera en O( n log n log log n)
Je savait pas qu'on faisait la FFT en TS à l'âge de 17 ans O_o !!!!!!!
Mais bon sinon j'ai trouvé un exemple avec les développements détaillés basé sur un graphe complet.
Merci quand même à tous
Lol non, on fait pas ça en TS
Chers amis, vous dîtes n'importe quoi! Un polynôme de degré infini?
Celà s'appelle dévelopement en série entiére, et le logarithme est effectivement développable en série entière autour de 1 (pour la détermination principale, bien sûr). Maintenant, je pense que vous avez vu que l'on classait beaucoup de fonctions selon qu'elles se comportent (en l'infini) comme un monôme (xn), un logarithme ou une exponentielle, et que ce sont des comportements très différents!
oui mais ce déveleoppement n'est valable que si |N-1|<1, donc on ne peut rien dire si N->oo.
Ah bon je dis vraiment n'importe quoi !!!
Eh bien dans ce cas je te recommande d'ouvrir un livre de math et de consulter la page des dl, tu y trouvera:
dl ln (a + x) = ln a + x/a -(1/2)(x/a)^2 + ... + ((-1)^(n-1) (x/a)^n) / n + ... jusqu'à l'infini...
avec -a<x<=a...
Il suffit donc de prendre a -> oo !!!
Il vaudrait peut etre mieux vérifier avant d'accuser
Salut,
du calme, je n'accuse personne!
Si je reprends ton développement limité, tu considére a come variable, n'est-ce pas? donc ln(a+x) est équivalent à ln(a), ce qui ne ressemble pas vraiment à un polynôme...
Cordialement.
non pas du tout, je considère a comme paramètre et x comme variable. Maintenant si on considère le dl de lnN, il suffit d'écrire N = x+a, et on obtient un polynome de x paramétré par a.
Le fait que a->oo est necessaire parce que -a<x<=a et N->oo
Mais alors, je fais tendre a -> oo et
ln (a + x) = ln a + x/a -(1/2)(x/a)^2 + ... + ((-1)^(n-1) (x/a)^n) / n + ...
devient ln(oo???+x)=ln(oo???).
Bon, tu l'auras compris, je ne te suis pas. On devrait plutôt parler en terme d'équivalents, ou d'estimations asymptotiques. En tout cas, je reste sur ma position (désolé)et je dis que ln(x) n'est équivalent à aucun polynôme.
Maintenant, si ça te plaît de parler de "polynômes infinis"...
Ce n'est plus un problème de maths là mais on joue sur les définitions. Faut pas trop qu'on se prenne le chou là-dessus.
PS: Pour moi c'est un polynôme car dans les définitions que je connais jamais il n'était dit que le degré était plus petit ou égal à une valeur limite entière finie.
Voila ce que j'ai dit !
J'ai pas dit qu'ils avaient le meme comportement a l'infini (i.e. meme complexité) mais juste qu'on pouvait faire un dl de ln autour d'un certain point (i.e. a)
Juste un détails et après j'arrête,Mais alors, je fais tendre a -> oo et
ln (a + x) = ln a + x/a -(1/2)(x/a)^2 + ... + ((-1)^(n-1) (x/a)^n) / n + ...
devient ln(oo???+x)=ln(oo???).
Bon, tu l'auras compris, je ne te suis pas. On devrait plutôt parler en terme d'équivalents, ou d'estimations asymptotiques. En tout cas, je reste sur ma position (désolé
Maintenant, si ça te plaît de parler de "polynômes infinis"...
évidemment si on cherche le dl autour de N=10^23 par exemple, c'est pas frocement très malin de prendre a=10^23 - 1 et x=1 pour faire apparaitre un polynome... Par contre si on prend a = x = N/2 là ca devient plus interessant...
Dans tout ce que j'ai dit avant, c'éait juste pour dire que le dl de lnx n'était pas seulement pour |x|<1 mais aussi pour d'autres forme, et qu'il est aussi interessant de pouvoir éxprimer ca:
ln (a+x) = ln a + P(x/a)
Ben si... sinon, ça s'appelle une série formelle, et les propriétés ne sont pas toujours les mêmes.
On est d'accord, j'avais cru comprendre le contraire. Mais alors, où est l'intérêt par rapport à la question initiale? :confused:
Et... :confused:
Ben rien... on est d'accord !
En tout cas de mon coté j'ai toujours vu les ordres de compléxités de la FFT étant données en fonction de logN, pas que d'un polynome...
Mais peut etre que pour simplifier (beaucoup simplifier) au lieu d'écrire O(N^2logN) on peut mettre O(N^3) et faire une grosse erreur volontaire par excès, comme ca on est toujours surpris par la fulgurence de l'algo
c'est une façon optimiste de voir les choses!Ben rien... on est d'accord !
En tout cas de mon coté j'ai toujours vu les ordres de compléxités de la FFT étant données en fonction de logN, pas que d'un polynome...
Mais peut etre que pour simplifier (beaucoup simplifier) au lieu d'écrire O(N^2logN) on peut mettre O(N^3) et faire une grosse erreur volontaire par excès, comme ca on est toujours surpris par la fulgurence de l'algo
Optimiste mais fausse. Qu'on reprenne la définition de la complexité algorithmique pour s'en convaincre.
C'est quand même pas pour rien qu'on a inventé (définit) ce concept.
Ne soldez pas grand mère, elle brosse encore.
On est d'accord.
