Как узнать приблизительную сложность алгоритма, зная время его выполнения?
============================================================================

 Есть функция f(x)=y, где x-кол-во элементов, которые принимает алгоритм, y- время выполнения алгоритма.  

Имея несколько таких точек (x,y) нужно приблизительно определить сложность алгоритма.  

Другими словами, имея эти точки на графике, нужно среди таких функций как {n,n^2,nlogn,n!,...} определить такую, которая будет наиболее приближенной к данным точкам. 

 Модульная разность отношений Y к известному перечню сложностей {n,n^2,nlogn,n!,...}.  

Ближайшая дробь, стремящаяся к единице, И одна из их взаимных разностей (расстояний) - стремящихся к нулю, и будет искомое значение. 

 Абстрагируясь от алгоритмов и их сложности в 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` укажет функцию, наиболее близкую к искомой. 

 ну блин..  

[Оценка сложности алгоритмов](https://www.google.com/search?client=firefox-b-d&ei=QQR1XvvSC_XhmwWK0YzYCA&q=%D0%9E%D1%86%D0%B5%D0%BD%D0%BA%D0%B0+%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8+%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2&oq=%D0%9E%D1%86%D0%B5%D0%BD%D0%BA%D0%B0+%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8+%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2&gs_l=psy-ab.3..0i67j0j0i7i30l2j0i30j0i5i30.18297.18297..18619...0.2..0.65.65.1......0....2j1..gws-wiz.......0i71..26%3A58.UXlLN3LvRXo&ved=0ahUKEwi7967B0KnoAhX18KYKHYooA4sQ4dUDCAo&uact=5)  

.. и вообще  

> Как узнать приблизительную сложность алгоритма, зная время его выполнения?

&&
> Есть функция f(x)=y, где x-кол-во элементов, которые принимает алгоритм, y- время выполнения алгоритма.  
> 
> Имея несколько таких точек (x,y) нужно приблизительно определить сложность алгоритма.  
> 
> Другими словами, имея эти точки на графике, нужно среди таких функций как {n,n^2,nlogn,n!,...} определить такую, которая будет наиболее приближенной к данным точкам.

вторая часть это вообще то *апроксимация*.. вы ее решили?  

это опорная точка. без нее - весь вопрос фуфло