牛顿插值数值分析
如果有n个点插值,表会有(n*n)/2+n个表项,如果直接编程会有O(n*n)的空间复杂度,编程时做个简单的改进,不难发现在这个表中只有部分数据有用,对角线(斜行)它们是目标值,用来表示多项式的,左边的两纵行(实际上只需要x一行)以及最底下的一行,表示当前插值的状态。经过改进后只需要O(n)的空间复杂度。
如果有n个点插值,表会有(n*n)/2+n个表项,如果直接编程会有O(n*n)的空间复杂度,编程时做个简单的改进,不难发现在这个表中只有部分数据有用,对角线(斜行)它们是目标值,用来表示多项式的,左边的两纵行(实际上只需要x一行)以及最底下的一行,表示当前插值的状态。经过改进后只需要O(n)的空间复杂度。