J'ai fait des recherches partout, même sur SO. et les articles scientifiques sur google dépassent de loin mes capacités mentales. Ceci est aussi proche que possible, mais ne répond pas à ma question. Il n'y a pas de réponse à cela autant que je l'ai recherché. Crois moi. (Mais n'hésitez pas à me prouver le contraire)

J'ai un problème de travail pour calculer la complexité temporelle de la fonction sinusoïdale en utilisant l'expansion de Taylor de la fonction sinus (x). Je ne demande pas la série Taylor ou le programme de fonction de la série Taylor, mais sa complexité temporelle . Je sais que le prochain terme de l'expansion de Taylor est donné comme suit:

Terme en x ^ n = (Terme en x ^ n-2) * x * x / n / (n-1)

L'extrait de fonction est le suivant:

double sine(double x) {
int n;
double sum, term;
n = 3;
sum = x;
term = x;
while(isgreater(fabs(term), 0.0000000001)) {
    term = (term * x * x) / ( n * (n -1));
        if(n % 4 == 3)
            sum -= term;
    else
            sum += term;
         n = n + 2;
}   
return sum;
}

Fabs () est la fonction de la valeur absolue et 0.0000000001 est la précision requise. Si ma compréhension est correcte, le code s'arrêtera lorsque la valeur du dernier terme calculé sera inférieure / égale à l'ensemble de flotteurs de précision.

Ma déduction jusqu'à présent est peut-être que la complexité temporelle dépendra de x ^ 2 / n ^ 2? ou il n'est pas déductible car nous ne savons pas à quel index / numéro spécifique la sterne sera inférieure à la précision float?

Les mathématiques ne sont pas fortes avec moi, mais heureusement, il y a des maîtres comme vous :)

2
DevX 31 août 2017 à 18:16

2 réponses

Dans le monde réel, vous utiliseriez la périodicité de la fonction et conserveriez un nombre borné de termes, d'où O (1).

Dans le monde théorique, vous avez besoin de nombres de plus en plus grands à cause de la croissance exponentielle de x ^ n, et la complexité de la multiplication entre en jeu. Comme expliqué par LutzL, le nombre de termes doit dépasser x, et la complexité globale doit être comme O (x M (log (x))) où M (k) désigne le coût d'une multiplication de nombres à k chiffres. (O (k²) pour l'implémentation naïve, O (k Log k Log Log k) pour les plus efficaces).

0
Yves Daoust 31 août 2017 à 17:54

Il semble assez simple que la condition de résiliation soit

abs(x^n/n!) < eps.

Ce n'est pas aussi simple que de résoudre ce problème pour n. Même en utilisant l'approximation de la livre sterling, vous devrez toujours résoudre

abs(e*x/n)^n < eps

Vous pourriez faire des hypothèses simplificatrices pour obtenir des limites supérieures, telles que n > 6*abs(x) de sorte que vous deviez alors résoudre

(e/6)^n < eps  =>  n > log(eps)/log(e/6).

Cependant, bien avant que ce n = O(abs(x)) ne démarre vraiment dans votre calcul, il sera assassiné par des erreurs d'annulation, car le terme où n=round(abs(x)) a la taille e^n et les termes environnants doivent le ramener à une valeur absolue moins que 1. À x=35, cela signifie que vous perdez tous les chiffres de la somme à l'annulation.

5
Lutz Lehmann 31 août 2017 à 15:41