我正在寻找一个参考和证明Simpson积分微积分规则的时间复杂性。我不确定该规则的类复杂性是否属于O(N)。
你能指出我正确的方向吗？
谢谢
首先，辛普森规则需要三个输入：
f(x)，假设它需要O(1)时间。(a, b)的界限d = (b - a) / n Note n的宽度必须是偶数正整数。辛普森的规则说明了这一点
∫abf（x）≈（d / 3）（[f（x0）+ f（xn）] + [2f（x1）+ 4f（x2）] + [2f（x3）+ 4f（x4）] +。 .. [2f（xn-2）+ 4f（xn-1）]）
∫abf（x）≈（d / 3）（[f（x0）+ 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的Simpson规则的项数与n呈线性关系。
假设乘法是常数并且函数复杂度是常数，我们注意求和公式以确定Simpson规则的时间复杂度是O(n)，它以线性时间运行。