Абстрагируясь от алгоритмов и их сложности в Big-O-нотации, задача сводится к подсчёту различий значений данной функции и функций-кандидатов на каком-то множестве контрольных точек.
Взять какой-то набор значений
[x0, x1, ... xN].
Получить «правильные»
y_true = [f(x0), f(x1), ... f(xN)]
Для каждой функции-кандидата из этих же
x получить их «предсказания»
y_pred = [Fn(x0), Fn(x1), ... Fn(xN)]
Определить, какая из функций меньше всего «ошиблась». Для этого сложить квадраты разниц
y_true - y_pred выданных каждой из функций на наборе входных значений
x
Наименьшая сумма укажет наиболее вероятного кандидата.
Например,
x = [1, 2, 4, 8, 16, 32, 64]
f(x) = [y0, y1, y2, y3, y4, y5, y6]
// n
[1, 2, 4, 8, 16, 32, 64]
sum = (y0 - 1)^2 + (y1 - 2)^2 + (y2 - 4)^2 + ... + (y6 - 64)^2 = sum0
// n^2
[1, 4, 16, 64, 256, 1024, 4096]
sum = (y0 - 1)^2 + (y1 - 4)^2 + (y2 - 16)^2 + ... + (y6 - 4096)^2 = sum1
// так же посчитать суммы ошибок для остальных функций:
// n * log(n), n!
минимальное значение среди
sumN укажет функцию, наиболее близкую к искомой.
