function - 任何已知的线性算法来近似具有线段的函数？

Question

我有一个由点列表给出的函数，例如：

f = [0.03, 0.05, 0.02, 1.3, 1.0, 5.6, ..., 13.4, 12.45]

我需要一种算法（具有线性复杂度）将此函数/列表“切割”成 K 个间隔/子列表，以便每个间隔/子列表包含“位于线段附近”的点（看一下图像）

数字K可以由算法本身决定，也可以是算法的参数。（最好由算法本身决定）

有没有我可以使用的已知算法？

score 0 · Accepted Answer

我正在用智能手机写作，所以这很短。基本上，如果两个连续值之间的差异大致相等，则函数几乎是线性的，请参见http://psn.virtualnerd.com/viewtutorial/PreAlg_13_01_0006

作为一种遍历未排序数组的算法，滑动窗口很好（https://www.geeksforgeeks.org/window-sliding-technique/）并且可以通过单遍实现（1遍解决方案）

更新因为评论：

因此，使用滑动窗口，您可以实现您在评论中提到的值的模糊性或模糊性，这就是为什么几乎是线性和近似的，即

if(abs(abs(x[i]-x[i+1]) - abs(x[i+1]-x[i+2])) < 0.5)
      {linearity_flag=1;} 
else 
      {linearity_flag=0;}

其中x[i]-x[i+1]和x[i+1]-x[i+2]是两个连续值的两个连续差，0.5 是一个特意选择的阈值，它修复了您在 xy 图中定义为直线或线性函数的内容（或您允许的直线的“抖动”）。所以你必须使用连续值的差异。除了 3 个点，您还可以使用这种方法包含更多点（滑动窗口）

如果你想要一个严格的数学分析，你可以使用其他曲线分析技术：https ://openstax.org/books/calculus-volume-1/pages/4-5-derivatives-and-the-shape-of-a-graph （实际上连续值的差异是二阶导数的离散实现）

1 回答 1