Répondre à la discussion
Affichage des résultats 1 à 27 sur 27

Complexité




  1. #1
    isozv

    Complexité

    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.

    -----


  2. Publicité
  3. #2
    isozv

    Re : Complexité

    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

  4. #3
    Evil.Saien

    Re : Complexité

    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)


  5. #4
    martini_bird

    Re : Complexité

    Salut,
    Citation Envoyé par isozv
    Bonjour, comme il n'y a pas de rubrique "informatique théorique" je tente ma chance ici (...).
    Je pense que c'est adéquat.
    Citation Envoyé par isozv
    Voilà, au fait j'ai un algorithme dont la complexité est d'ordre
    En n ou en p?
    Citation Envoyé par isozv
    Je cherche au fait un exemple (simple mais rigoureux) ou l'ordre de complexité d'un algorithme est ni exponentiel, ni polynomial
    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+

  6. #5
    isozv

    Re : Complexité

    Citation Envoyé par Evil.Saien
    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)
    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 ???

  7. A voir en vidéo sur Futura
  8. #6
    Evil.Saien

    Re : Complexité

    Je pense pas que N^2logN puisse s'écrire sous forme polynomiale, ou alors en un dl autour d'une certaine valeur...

  9. #7
    isozv

    Re : Complexité

    en développement de Taylor tu peux toujours exprimer logN sous forme de série de Taylor et donc N^2logN aussi.

  10. Publicité
  11. #8
    Evil.Saien

    Re : Complexité

    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...

  12. #9
    isozv

    Re : Complexité

    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.

  13. #10
    olle

    Re : Complexité

    de mémoire, la recherche par dichotomie a une complexité en log(N).
    (je sais pas si je suis hors sujet )

  14. #11
    Lord

    Re : Complexité

    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)
    Suis-je Amour le Phébus, Lusignon ou Biron ?

  15. #12
    isozv

    Re : Complexité

    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

  16. #13
    Lord

    Re : Complexité

    Lol non, on fait pas ça en TS
    Suis-je Amour le Phébus, Lusignon ou Biron ?

  17. #14
    martini_bird

    Re : Complexité

    Citation Envoyé par Evil.Saien
    En effet on peut faire comme ca, mais logN s'écrit dans ce cas en un polynome de degré infinie
    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!

  18. #15
    martini_bird

    Re : Complexité

    Citation Envoyé par isozv
    en développement de Taylor tu peux toujours exprimer logN sous forme de série de Taylor et donc N^2logN aussi.
    oui mais ce déveleoppement n'est valable que si |N-1|<1, donc on ne peut rien dire si N->oo.

  19. #16
    Evil.Saien

    Re : Complexité

    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
    Dernière modification par Evil.Saien ; 08/12/2004 à 07h37.

  20. #17
    martini_bird

    Re : Complexité

    Citation Envoyé par Evil.Saien
    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.

  21. #18
    Evil.Saien

    Re : Complexité

    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

  22. #19
    martini_bird

    Re : Complexité

    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"...

  23. #20
    isozv

    Re : Complexité

    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.

  24. #21
    Evil.Saien

    Re : Complexité

    Citation Envoyé par Evil.Saien
    Je pense pas que N^2logN puisse s'écrire sous forme polynomiale, ou alors en un dl autour d'une certaine valeur...
    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)

  25. #22
    Evil.Saien

    Re : Complexité

    Citation Envoyé par martini_bird
    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"...
    Juste un détails et après j'arrête,
    é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...

    Citation Envoyé par martini_bird
    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!
    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)

  26. #23
    martini_bird

    Re : Complexité

    Citation Envoyé par isozv
    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.
    Ben si... sinon, ça s'appelle une série formelle, et les propriétés ne sont pas toujours les mêmes.

    Citation Envoyé par Evil.Saien
    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)
    On est d'accord, j'avais cru comprendre le contraire. Mais alors, où est l'intérêt par rapport à la question initiale? :confused:

    Citation Envoyé par Evil.Saien
    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)
    Et... :confused:

  27. #24
    Evil.Saien

    Re : Complexité

    Citation Envoyé par martini_bird
    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

  28. #25
    martini_bird

    Re : Complexité

    Citation Envoyé par Evil.Saien
    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!

  29. #26
    monnoliv

    Re : Complexité

    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.

  30. #27
    martini_bird

    Re : Complexité

    Citation Envoyé par monnoliv
    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.
    On est d'accord.

Sur le même thème :

Discussions similaires

  1. En parlant de complexité...
    Par The Nameless dans le forum Epistémologie et Logique
    Réponses: 4
    Dernier message: 28/08/2007, 17h37
  2. complexité algorithmique
    Par benoir126 dans le forum Mathématiques du supérieur
    Réponses: 4
    Dernier message: 18/03/2007, 10h31
  3. Question de complexité
    Par PopolAuQuébec dans le forum Discussions scientifiques
    Réponses: 148
    Dernier message: 15/12/2006, 15h29
  4. Théorie de la complexité
    Par CHUCKYCHUCK dans le forum TPE / TIPE et autres travaux
    Réponses: 0
    Dernier message: 19/11/2006, 14h21
  5. Le développement de la complexité
    Par Jacques Richard dans le forum Physique
    Réponses: 0
    Dernier message: 14/01/2006, 23h11