> Mais ce que je dis, c'est que le fibo optimisé sur une entrée pas démesurément
> grande (genre 277887173) prend un temps aussi démesuré.
Quand je dis "les algos de verif sont exponentiels", c'est en fonction de la taille du code (nombre de variables par exemple). Des programmes avec 100 variables, tu en vois tous les jours, et tu aimerais bien les verifier pour qu'ils n'aient pas de bugs. Mais tu connais beaucoup de programmes avec 277887173 variables ? (encore une fois, si le chiffre n'est pas assez grand, prend fibo(200))
Pour n'importe quel algo en cst * taille de l'entrée, si cst n'est pas trop grande, je sais que ça va toujours marcher, quelle que soit l'entrée que je lui donne, simplement parce que ma machine n'est capable de stoquer que des entrées de taille "raisonnables". (cst * mon disque dur de 40 Go / le nombre d'instructions que mon proc peut executer en 1 sec = un nombre raisonnable de secondes)
Toi, tu triches, tu mesure la complexité en fonction de la valeur de l'entrée, non de sa taille (c'est vrai que mon exemple de fibbo est un peu pousse au crime :-)
(note : si tu parles en valeur de l'entrée, les algos de crypto, factorisation en facteurs premiers, ... sont en général linéaires. Ce n'est pas ce qui se dit dans la littérature)
[^] # Re: exponentiel => indecidable
Posté par Matthieu Moy (site web personnel) . En réponse au journal couverture de code. Évalué à 2.
> grande (genre 277887173) prend un temps aussi démesuré.
Quand je dis "les algos de verif sont exponentiels", c'est en fonction de la taille du code (nombre de variables par exemple). Des programmes avec 100 variables, tu en vois tous les jours, et tu aimerais bien les verifier pour qu'ils n'aient pas de bugs. Mais tu connais beaucoup de programmes avec 277887173 variables ? (encore une fois, si le chiffre n'est pas assez grand, prend fibo(200))
Pour n'importe quel algo en cst * taille de l'entrée, si cst n'est pas trop grande, je sais que ça va toujours marcher, quelle que soit l'entrée que je lui donne, simplement parce que ma machine n'est capable de stoquer que des entrées de taille "raisonnables". (cst * mon disque dur de 40 Go / le nombre d'instructions que mon proc peut executer en 1 sec = un nombre raisonnable de secondes)
Toi, tu triches, tu mesure la complexité en fonction de la valeur de l'entrée, non de sa taille (c'est vrai que mon exemple de fibbo est un peu pousse au crime :-)
(note : si tu parles en valeur de l'entrée, les algos de crypto, factorisation en facteurs premiers, ... sont en général linéaires. Ce n'est pas ce qui se dit dans la littérature)