Un probléme à 1 million de dollards. - Page 2
Répondre à la discussion
Page 2 sur 2 PremièrePremière 2
Affichage des résultats 31 à 34 sur 34

Un probléme à 1 million de dollards.



  1. #31
    kwariz

    Re : Un probléme à 1 million de dollards.


    ------

    cela ne signifie pas grand chose, tu penses à O(1) ?
    Tu penses à l'ensemble des polynomes P dont l'évaluation en un point par l'application d'un certain algorithme prendra moins 10^6 additions/multiplications ?

    -----

  2. #32
    un_homme

    Re : Un probléme à 1 million de dollards.

    Je pense à O(ln(p)^3) par exemple.
    Je répéte raisonnable renvoie à la complexité de l'algo que je cherche en l'occurence ici O(Q(ln(p))).
    En effet quand on cherche un algo on veut qu'il ait une complexité raisonnable (non ?).

    En espérant être claire.

  3. #33
    kwariz

    Re : Un probléme à 1 million de dollards.

    Tu parles de polynomes dont on peut évaluer la valeur en temps raisonnable ... nous n'en sommes que là. Si les polynomes sont quelconques tu ne pourras trouver mieux que O(n) avec n le degré du polynome. Si tu restreins les polynomes en entrée, par exemple si tu ne prends en compte que les polynomes dont l'évaluation peut se faire en O(1) alors tu restreindras le degré des polynomes.

    Tu cherches à construire un problème de NP ?

  4. #34
    un_homme

    Re : Un probléme à 1 million de dollards.

    Oui, effectivement.

Page 2 sur 2 PremièrePremière 2

Discussions similaires

  1. Insecte : un million-de-pattes :)
    Par invitee9e9f984 dans le forum Identification des espèces animales ou végétales
    Réponses: 1
    Dernier message: 05/08/2009, 19h29
  2. Bientot 1 million de messages!
    Par Yoyo dans le forum Biologie
    Réponses: 10
    Dernier message: 02/04/2007, 20h03
  3. Un million de messages...
    Par jbfe dans le forum Matériel astronomique et photos d'amateurs
    Réponses: 0
    Dernier message: 20/03/2007, 13h22