Любой известный линейный алгоритм для приближения функции с отрезками?

Question

У меня есть функция, заданная списком точек, например:

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

Мне нужен алгоритм (с линейной сложностью), чтобы «разрезать» эту функцию / список на K интервалов / подсписков так, чтобы каждый интервал / подсписок содержит точки, которые "l ie возле отрезка" (взгляните на изображение)

Число K может определяться либо самим алгоритмом или быть параметром алгоритма. (предпочтительнее решать самим алгоритмом)

Есть ли такой известный алгоритм, который я мог бы использовать?

Answer 1

Я пишу со смартфона, так что это коротко. По существу, функция является почти линейной, если разница между двумя последовательными значениями приблизительно равна см. 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] - это два последовательных различия двух последовательных values ​​and 0.5 - преднамеренно выбранный порог, который фиксирует то, что вы определяете как прямую линию или линейную функцию на графике xy (или какое «дрожание» линии вы допускаете). Таким образом, вы должны использовать разницу различий последовательных значений. Вместо 3 баллов вы также можете включить больше баллов с этим подходом (скользящее окно)

Если вы хотите строгий математический анзац, вы можете использовать другие анализ кривой метод: https://openstax.org/books/calculus-volume-1/pages/4-5-derivatives-and-the-shape-of-a-graph (фактически разница разностей последовательных значений является дискретной реализацией 2-й производной)