Ici à priori c'est plutot qu'on a un algorithme efficace sur des "petites" instances du problème, mais qui perd son avantage à partir d'une certaine taille de problème. Ce qui est souvent le cas quand on mets des trucs sioux dans un algo comme de l'apprentissage, qui bouffent du temps et de la mémoire pour en gagner plus tard. L'algo peut être moins efficace sur de tout petits problèmes qu'un algo naif dans ces cas là.
Du coup l'algo "intelligent" sera en moyenne bien meilleurs, il a une infinité de problème derrière le seuil pour rattraper son retard, mais moins performant jusqu'au seuil.
L'algo intelligent peut donc être meilleur à la fois en moyenne et au pire, mais pas sur des instances petites ou bornées.
[^] # Re: Plop !
Posté par thoasm . En réponse au journal "L'informatique Paradoxale". Évalué à 3.
Ici à priori c'est plutot qu'on a un algorithme efficace sur des "petites" instances du problème, mais qui perd son avantage à partir d'une certaine taille de problème. Ce qui est souvent le cas quand on mets des trucs sioux dans un algo comme de l'apprentissage, qui bouffent du temps et de la mémoire pour en gagner plus tard. L'algo peut être moins efficace sur de tout petits problèmes qu'un algo naif dans ces cas là.
Du coup l'algo "intelligent" sera en moyenne bien meilleurs, il a une infinité de problème derrière le seuil pour rattraper son retard, mais moins performant jusqu'au seuil.
L'algo intelligent peut donc être meilleur à la fois en moyenne et au pire, mais pas sur des instances petites ou bornées.