Lazi

Efficacité à calculer

Contexte

On a une étude sur la mesure de l'éfficacité en général. Mais un cas particuler important est l'efficacité à exécuter un calcul. Une méthode plus efficace pour calculer peut sauter des étapes (par exemple si on utilise la notation de fonction, on saute des étapes des duplicates). Pour réaliser des calculs plus efficaces, comme on utilise autre chose que le calcul de base réalisé par la fonction everything, il faut que la formule calculée soit une donnée. C'est à dire que l'on a un niveau supplémentaire de représentation.

Question

Peut-on comparer les efficacités à réaliser un certain calcul ?

Étude

On se place dans le contexte où l'on veut comparer le calcul réalisé par deux formules calculant une même formule représentée et calculée de deux manières différentes.

  • Si la formule de départ est identique pour les deux calculs (après traduction dans un langage plus simple)
  • si les deux méthodes de calculs peuvent se traduire l'une dans l'autre
Alors on peut comparer l'efficacité des calculs.

L'efficacité n'est pas forcément constante au cours du calcul, il faut donc une preuve mathématique pour calculer le ratio de calcul élémentaire nécéssaire et voir comment il évolue.

Réponse

Oui, voir l'étude.