泰勒级数的正弦函数的时间复杂度是多少？
what could be the time complexity of sine function by taylor's series?
我确实到处搜索，甚至在 SO 上。
google 上的学术文章远远超出了我的智力范围。
This 已经很接近了，但没有回答我的问题。
就我所寻找的而言，没有答案。相信我。
（但请随时证明我错了）
我有一个作业问题是使用 sine(x) 函数的泰勒展开来计算 sine 函数的时间复杂度。
我不是要泰勒级数或泰勒级数函数程序，而是它的时间复杂度。
我知道泰勒展开式的下一项是：
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 是所需的精度。
如果我的理解是正确的，当最后计算的项的值小于 than/equal 到精度浮点集时，代码将停止。
到目前为止我的推论是时间复杂度可能取决于 x^2/n^2 ？
或者它是不可推导的，因为我们不知道在哪个特定 index/number 燕鸥将小于精度浮点数？
我数学不强，幸好有像你这样的大师:)
终止条件似乎很简单
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 这意味着您丢失了总和的所有数字以进行取消。
what could be the time complexity of sine function by Taylor's series?
Math is not strong with me
作为 精细分析的辅助手段，有时完整性检查和 视觉 简单测试代码提供了对时间复杂度的洞察力。
#define N 1000000
clock_t test_sine(double x) {
clock_t c1 = clock();
for (int i = 0; i < N; i++) {
sine(x);
}
clock_t c2 = clock();
return c2 - c1;
}
void test_sines(void) {
double x0 = 0;
double x1 = 70;
double dx = 0.2;
for (double x = x0; x <= x1; x += dx) {
printf("%f \t %d\n", x, (int) test_sine(x));
fflush(stdout);
}
}
int main(void) {
test_sines();
}
示例输出
0 16
0.2 78
0.4 93
0.6 94
0.8 94
1 124
...
一旦 x > 3.
绘制它就相当线性了
仔细观察，我们会看到每个幂的时间步长，使用趋势看起来非常接近 t = pow(x,1/3.)
void test_sines(void) {
double x0 = 0.0000000001/2;
double x1 = 1;
double dx = pow(2, 1.0/5);
for (double x = x0; x <= x1; x *= dx) {
使用 clock() 相当粗糙，但提供了可视化的分析。
对于 x * x，我原以为 term 会影响每个 sqrt(x) 的 isgreater()，因为这将迫使另一个循环迭代。
结论：小值的时间复杂度约为 power(x,1.0/d) (2.0 <= d <= 3.1)，大值的时间复杂度为线性。
请注意，OP sine() 的质量存在许多问题，导致其结果对许多 x 来说很弱。对于许多 x > 900 的值，sine(x) 是一个无限循环。
在现实世界中，您将使用函数的周期性并保留有限数量的项，因此 O(1)。
在理论世界中，由于 x^n 的指数增长，您需要越来越大的数字，乘法的复杂性开始发挥作用。正如 LutzL 所解释的，项数必须超过 x，并且全局复杂度必须类似于 O(x M(log(x)))，其中 M(k) 表示 k 位数字相乘的成本。 （O(k²) 用于简单的实现，O(k Log k Log Log k) 用于更有效的实现）。
我确实到处搜索，甚至在 SO 上。 google 上的学术文章远远超出了我的智力范围。 This 已经很接近了，但没有回答我的问题。 就我所寻找的而言，没有答案。相信我。 （但请随时证明我错了）
我有一个作业问题是使用 sine(x) 函数的泰勒展开来计算 sine 函数的时间复杂度。 我不是要泰勒级数或泰勒级数函数程序，而是它的时间复杂度。 我知道泰勒展开式的下一项是：
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 是所需的精度。 如果我的理解是正确的，当最后计算的项的值小于 than/equal 到精度浮点集时，代码将停止。
到目前为止我的推论是时间复杂度可能取决于 x^2/n^2 ？ 或者它是不可推导的，因为我们不知道在哪个特定 index/number 燕鸥将小于精度浮点数？
我数学不强，幸好有像你这样的大师:)
终止条件似乎很简单
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 这意味着您丢失了总和的所有数字以进行取消。
what could be the time complexity of sine function by Taylor's series?
Math is not strong with me
作为
#define N 1000000
clock_t test_sine(double x) {
clock_t c1 = clock();
for (int i = 0; i < N; i++) {
sine(x);
}
clock_t c2 = clock();
return c2 - c1;
}
void test_sines(void) {
double x0 = 0;
double x1 = 70;
double dx = 0.2;
for (double x = x0; x <= x1; x += dx) {
printf("%f \t %d\n", x, (int) test_sine(x));
fflush(stdout);
}
}
int main(void) {
test_sines();
}
示例输出
0 16
0.2 78
0.4 93
0.6 94
0.8 94
1 124
...
一旦 x > 3.
仔细观察，我们会看到每个幂的时间步长，使用趋势看起来非常接近 t = pow(x,1/3.)
void test_sines(void) {
double x0 = 0.0000000001/2;
double x1 = 1;
double dx = pow(2, 1.0/5);
for (double x = x0; x <= x1; x *= dx) {
使用 clock() 相当粗糙，但提供了可视化的分析。
对于 x * x，我原以为 term 会影响每个 sqrt(x) 的 isgreater()，因为这将迫使另一个循环迭代。
结论：小值的时间复杂度约为 power(x,1.0/d) (2.0 <= d <= 3.1)，大值的时间复杂度为线性。
请注意，OP sine() 的质量存在许多问题，导致其结果对许多 x 来说很弱。对于许多 x > 900 的值，sine(x) 是一个无限循环。
在现实世界中，您将使用函数的周期性并保留有限数量的项，因此 O(1)。
在理论世界中，由于 x^n 的指数增长，您需要越来越大的数字，乘法的复杂性开始发挥作用。正如 LutzL 所解释的，项数必须超过 x，并且全局复杂度必须类似于 O(x M(log(x)))，其中 M(k) 表示 k 位数字相乘的成本。 （O(k²) 用于简单的实现，O(k Log k Log Log k) 用于更有效的实现）。