Discussion :

[antodugers]

Bonjour, j'ai du mal à calculer la complexité algorithmique d'une fonction trapèze.
On donne l'algorithme suivant :

Entrée : f fonction, a,b réels , n entier
Sortie : res
Variables locales : res, pas, x1,x2 réels
Début :
res=0
pas=valeur absolue de (b-a)/n
Pour i allant de 0 à n-1:
x0=a+(pas*i)
x1=a+(pas*(i+1))
res=res+pas*0,5*(f(xo)+f(x1))
Fin

On me demande de la calculer en tenant compte seulement de l'appel à la fonction et de modifier l'algorithme pour réduire cette complexité en calcul.
Mais je ne vois vraiment pas comment procéder.
Merci d'avance

[Flodelarab]

Bonjour

Tu découpes ton intervalle en n parties et tu sommes sur la moyenne des extrémités des parties. Tu peux donc simplifier.

res=(f(x0)+f(x1))/2+(f(x1)+f(x2))/2+(f(x2)+f(x3))/2+...


Au final, tu fais la moyenne des extrémités et tu ajoutes toutes tes images intermédiaires.

[dourouc05]

On me demande de la calculer en tenant compte seulement de l'appel à la fonction

En d'autres termes : combien d'opérations (addition, soustraction, multiplication, division, affectation, etc.) effectues-tu au plus en fonction de n (qui limite le nombre d'itérations de ta boucle) ?

On te demande alors probablement une complexité asymptotique, c'est-à-dire la plus haute puissance de la fonction que tu as obtenue. Par exemple, si tu effectues opérations exactement, tu auras une complexité asymptotique de : en multipliant ce dernier polynôme par une constante, tu as une borne supérieure sur le nombre d'opérations à effectuer, ce qui se note souvent .

[antodugers]

Merci pour vos explications.
Mais du coup si on fait le somme on a : (n(f(b)+f(a))/2. Et du coup c'est une complexité linéaire (O(n)) ? J'ai un peu du mal à en déduire la complexité