任何已知的线性算法都能近似线段的函数？

Question

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

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

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

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

我可以使用这种已知算法吗？

Answer 1

我正在用智能手机书写，因此简短。如果两个连续值之间的difference近似相等，则基本上函数几乎是线性的，请参见http://psn.virtualnerd.com/viewtutorial/PreAlg_13_01_0006

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

由于评论而更新：

因此，通过滑动窗口，您可以实现注释中提到的值的模糊性或模糊性，这就是为什么几乎线性且近似，即

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图中定义为直线或线性函数的值（或该行的“抖动”）您允许）