c - 泰勒级数的正弦函数的时间复杂度是多少？

Question

我确实到处搜索，甚至在 SO 上。和谷歌上的学术文章远远超出了我的智力范围。 This尽可能接近，但没有回答我的问题。就我所寻找的而言，没有答案。相信我。(但随时证明我错了)

我有一个家庭作业问题是使用 sine(x) 函数的泰勒展开来计算正弦函数的时间复杂度。我不是要泰勒级数或泰勒级数函数程序，而是它的时间复杂度。我知道泰勒展开中的下一项是:

Term in x^n = (Term in x^n-2) * x * x / n / (n-1)

函数片段是这样的:

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() 是求绝对值的函数0.0000000001 是所需的精度。如果我的理解是正确的，当最后计算的项的值小于/等于精度浮点集时，代码将停止。

到目前为止，我的推论是时间复杂度可能取决于 x^2/n^2 ？或者它是不可推断的，因为我们不知道燕鸥在哪个特定索引/数字处将小于精度 float ？

数学对我来说并不强，但幸好有像你这样的大师:)

Answer 1

终止条件似乎很简单

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

不那么直接的是为 n 解决这个问题。即使使用 Sterling 近似，您仍然需要求解

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

您可以做一些简化假设以获得上限，例如 n > 6*abs(x) 这样您就必须解决

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

但是，早在这个 n = O(abs(x)) 真正开始计算之前，您的计算就被取消错误所扼杀，因为 n=round(abs(x)) 的大小为 e^n 并且周围的项必须将其减少到小于 1 的绝对值。在 x=35 这意味着你丢失了所有数字取消的总和。