Simpson 简单积分法则的时间复杂度
Time complexity of Simpson's rule for simple intergral calculus
我正在寻找辛普森积分法则的时间复杂度的参考和证明。
我不确定该规则的 class 复杂性是否属于 O(N)。
你能给我指出正确的方向吗？
谢谢
首先，辛普森法则需要三个输入：
- 函数
f(x)，假设它需要 O(1) 时间。
- 积分的界限
(a, b)
- 细分数，n。那么"bar"的宽度
d = (b - a) / n注意n必须是偶数正整数。
辛普森法则指出
∫ab f(x) ≈ (d/3)([f(x 0) + f(xn)] + [2f(x1) + 4f(x 2)] + [2f(x3) + 4f(x4)] + ... [2f(x n-2) + 4f(xn-1)])
∫ab f(x) ≈ (d/3)([f(x 0) + f(xn)] + ∑k=2(n-1)/ 2 f(xk)
其中 xk 等于 a + kd。注意 x0 = a, xn = a + nd = b.
从求和项∑k=2(n-1)/2，我们可以很容易地得出有[(n-1)/2 - 2 + 1]项，另外还有两项f(x0), f(xn)。用于给定 n 的辛普森规则的项数是 线性 到 n.
假设乘法为常数，函数复杂度为常数，我们记下求和公式，确定辛普森法则的时间复杂度为O(n)，线性时间运行。
我正在寻找辛普森积分法则的时间复杂度的参考和证明。
我不确定该规则的 class 复杂性是否属于 O(N)。
你能给我指出正确的方向吗？
谢谢
首先，辛普森法则需要三个输入：
- 函数
f(x)，假设它需要O(1)时间。 - 积分的界限
(a, b) - 细分数，n。那么"bar"的宽度
d = (b - a) / n注意n必须是偶数正整数。
辛普森法则指出
∫ab f(x) ≈ (d/3)([f(x 0) + f(xn)] + [2f(x1) + 4f(x 2)] + [2f(x3) + 4f(x4)] + ... [2f(x n-2) + 4f(xn-1)])
∫ab f(x) ≈ (d/3)([f(x 0) + f(xn)] + ∑k=2(n-1)/ 2 f(xk)
其中 xk 等于 a + kd。注意 x0 = a, xn = a + nd = b.
从求和项∑k=2(n-1)/2，我们可以很容易地得出有[(n-1)/2 - 2 + 1]项，另外还有两项f(x0), f(xn)。用于给定 n 的辛普森规则的项数是 线性 到 n.
假设乘法为常数，函数复杂度为常数，我们记下求和公式，确定辛普森法则的时间复杂度为O(n)，线性时间运行。